#include #include #include #include #include using namespace std; typedef long long ll; const int TreeBase = 1<<21; const int inf = 1000000000; struct point_t { ll x, y; }; inline bool operator<(const point_t &a, const point_t &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline bool operator==(const point_t &a, const point_t &b) { return a.x == b.x && a.y == b.y; } pair combine(pair a, pair b) { if (a.first < b.first) { return make_pair(a.first, min(a.second, b.first)); } else { return make_pair(b.first, min(b.second, a.first)); } } struct line_t { point_t left, right; int id; bool horizontal; line_t() { } line_t(point_t left, point_t right, int id) { this->left = min(left, right); this->right = max(left, right); this->horizontal = (left.y == right.y); this->id = id; } }; const int dx[4] = { 0, 1, 0, -1 }; const int dy[4] = { 1, 0, -1, 0 }; const int P = 10; line_t lines[1000100]; ll cross(const point_t &a, const point_t &b, const point_t &c) { ll a1 = b.x-a.x, a2 = b.y-a.y; ll b1 = c.x-a.x, b2 = c.y-a.y; return a1*b2-b1*a2; } ll distance1(point_t a, point_t b) { return (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y); } bool intersect(line_t pa, line_t pb) { point_t a = pa.left, b = pa.right; point_t c = pb.left, d = pb.right; if (pa.horizontal && pb.horizontal) { return a.y == c.y && ((a.x <= c.x && c.x <= b.x) || (a.x <= d.x && d.x <= b.x)); } if (!pa.horizontal && !pb.horizontal) { return a.x == c.x && ((a.y <= c.y && c.y <= b.y) || (a.y <= d.y && d.y <= b.y)); } if (pa.horizontal && !pb.horizontal) { return intersect(pb, pa); } return c.x <= a.x && d.x >= a.x && a.y <= c.y && b.y >= c.y; /* ll acb = cross(a,c,b); ll adb = cross(a,d,b); ll cad = cross(c,a,d); ll cbd = cross(c,b,d); if (((acb > 0 && adb < 0) || (acb < 0 && adb > 0)) && ((cad > 0 && cbd < 0) || (cad < 0 && cbd > 0))) { //printf("%d %d %d %d %d %d %d %d %d\n", a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y, true); return true; } if (acb == 0 && distance1(a,b) >= distance1(a,c) && distance1(b,a) >= distance1(b,c)) { //printf("%d %d %d %d %d %d %d %d %d\n", a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y, true); return true; } if (adb == 0 && distance1(a,b) >= distance1(a,d) && distance1(b,a) >= distance1(b,d)) { //printf("%d %d %d %d %d %d %d %d %d\n", a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y, true); return true; } //printf("%d %d %d %d %d %d %d %d %d\n", a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y, false); return false;*/ } int main() { int N; while (scanf("%d", &N) == 1) { point_t current = (point_t) { 0, 0 }; int direction = 0; for (int i = 0; i < N; i++) { int a; scanf("%d", &a); point_t next = (point_t) { current.x + a * dx[direction], current.y + a * dy[direction] }; lines[i] = line_t(current, next, i); current = next; direction++; direction %= 4; } for (int i = 0; i < N; i++) { for (int j = max(0, i-P); j < i-1; j++) { if (intersect(lines[i], lines[j])) { printf("%d\n", i); goto next_case; } } } printf("OK\n"); next_case: continue; } return 0; }