시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB165433.333%

## 문제

Karel wants to register his robot Karel for a robot contest. The aim of the contest is to escape from a maze using a program consisting of N instructions. Each instruction is in the form: “MOVE ai METERS FORWARD, THEN TURN 90◦ TO THE RIGHT”, where ai is a positive integer. We can simply encode the whole program for the robot as the sequence of integers a1 a2 a3 . . . aN representing the lengths of particular steps.

For example, if the robot starts at coordinates [0, 0] facing north and the encoded program is 1 2 3 4 5, the robot would end up at coordinates [−2, 3] facing east. An important property of any valid program is that the path the robot takes is not allowed to intersect itself at any point.

This sounds like a nice contest problem, doesn’t it? We want to give you an idea what it is like to organize a programming contest. Therefore, your task is to write a validator for the problem described above. (You may read more about validators in the validate problem.)

## 입력

The input contains several test cases. Each test case consists of two lines. The first line contains a single integer N (1 ≤ N ≤ 106), the number of instructions that form the robot’s program. The second line contains N space-separated integers a1 a2 a3 . . . aN (1 ≤ ai ≤ 109), an encoded program for the robot, as described above.

## 출력

For each test case, print exactly one line. If the given program describes a path that does not intersect itself, print “OK”. Otherwise output a single integer M (0 ≤ M < N), the maximum number of instructions from the beginning of the program that describe a valid path. That means the path described by the program consisting of instructions a1 a2 a3 . . . aM does not intersect itself and M is maximal with this property

## 예제 입력 1

7
3 1 1 3 2 2 6
3
2 1 1
6
2 1 4 4 4 3


## 예제 출력 1

3
OK
5