B. Задача робота
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Робот Док находится в зале, в котором в ряд стоят n компьютеров, пронумерованных слева направо от 1 до n. В каждом компьютере содержится ровно одна часть информации, каждую из которых Док хочет в итоге получить. Компьютеры оснащены системой защиты, поэтому, чтобы взломать i-й из них, роботу нужно собрать не менее ai любых частей информации из других компьютеров. Осуществить взлом Док может, только находясь непосредственно рядом с компьютером.

Робот собран по современным технологиям и может двигаться вдоль ряда компьютеров в любом из двух возможных направлений, однако смена направления движения требует большое количество ресурсов Дока. Сообщите минимальное количество смен направлений движения, которое придется сделать роботу для сбора всех n частей информации, если изначально он находится рядом с компьютером с номером 1.

Гарантируется, что существует хотя бы одна последовательность действий робота, приводящая к сбору всей информации. Изначально Док не владеет ни одной из частей информации.

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

В первой строке содержится число n (1 ≤ n ≤ 1000). Во второй строке содержатся n целых неотрицательных чисел a1, a2, ..., an (0 ≤ ai < n), разделенных пробелом. Гарантируется, что робот может собрать все части информации.

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

Выведите единственное число — минимальное количество смен направлений движения, которое придется сделать роботу для сбора всех n частей информации.

Примеры
Входные данные
3
0 2 0
Выходные данные
1
Входные данные
5
4 2 3 0 1
Выходные данные
3
Входные данные
7
0 3 1 0 5 2 6
Выходные данные
2
Примечание

В первом примере собрать все части информации оптимальным образом можно, собрав сначала часть информации в первом компьютере, затем в третьем, затем сменить направление движения и двигаться ко второму компьютеру, и, имея 2 части информации, собрать последнюю часть.

Во втором примере для сбора всех частей оптимальным образом Док может сначала поехать к четвертому компьютеру и получить часть информации, затем, имея одну часть, к пятому компьютеру и получить еще одну часть информации, затем таким же образом ко второму, потом к третьему, и, наконец, к первому. Смены направления произойдут перед движением от пятого ко второму компьютеру, затем от второго к третьему, далее от третьего к первому.

В третьем примере оптимальный порядок сбора частей из компьютеров может выглядеть так: 1->3->4->6->2->5->7.