e-olymp
Задачи

Одинокий король

Одинокий король

prb4557-1

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из n его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) - возможные ходы короля показаны на рисунке снизу.

Определите, побывал ли король дважды на одном и том же поле за свои n ходов.

prb4557-2

Входные данные

В первой строке задано общее число ходов короля n (0n1000). В последующих n строках заданы направления перемещения короля: строка под номером i + 1 задаёт направление перемещения короля на i-ом ходу.

Выходные данные

Выведите единственное число - номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение "Ok" (без кавычек), а во второй - манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами (x1, y1) и (x2, y2) определяется по формуле: d = |x2 - x1| + |y2 - y1|.

Лимит времени 1 секунд
Лимит использования памяти 122.17 MiB
Входные данные #1
5
1
2
4
7
4
Выходные данные #1
4
Входные данные #2
5
1
2
4
6
4
Выходные данные #2
Ok
2