Self-Intersecting Path

Karel enters his robot in a maze escape contest. The robot runs a program of $N$ instructions. Instruction $i$ says: move $a_i$ meters forward, then turn 90 degrees to the right. The whole program is written as the integers $a_1, a_2, \dots, a_N$, one distance per instruction.

The robot starts at $(0, 0)$ facing north. With the program $1, 2, 3, 4, 5$ it stops at $(-2, 3)$ facing east.

A program is valid when the path the robot draws never touches itself. Two consecutive instructions draw two segments that share the corner between them, and that corner is the one allowed exception. Any other point shared by two segments, even a single point where they only graze each other, makes the program invalid.

For each program, decide whether it is valid. If it is not, find how many instructions from the beginning still draw a valid path.

The input holds several test cases and ends at the end of the file. Each test case takes two lines. The first line has one integer $N$ ($1 \le N \le 10^6$), the number of instructions. The second line has $N$ integers $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$) separated by spaces.

Print one line for each test case. If the path of the given program never touches itself, print OK. Otherwise print one integer $M$ ($0 \le M < N$), the largest number such that the path of the program $a_1, a_2, \dots, a_M$ never touches itself.