Робот Док находится в зале, в котором в ряд стоят n компьютеров, пронумерованных слева направо от 1 до n. В каждом компьютере содержится ровно одна часть информации, каждую из которых Док хочет в итоге получить. Компьютеры оснащены системой защиты, поэтому, чтобы взломать i-й из них, роботу нужно собрать не менее ai любых частей информации из других компьютеров. Осуществить взлом Док может, только находясь непосредственно рядом с компьютером.
Робот собран по современным технологиям и может двигаться вдоль ряда компьютеров в любом из двух возможных направлений, однако смена направления движения требует большое количество ресурсов Дока. Сообщите минимальное количество смен направлений движения, которое придется сделать роботу для сбора всех n частей информации, если изначально он находится рядом с компьютером с номером 1.
Гарантируется, что существует хотя бы одна последовательность действий робота, приводящая к сбору всей информации. Изначально Док не владеет ни одной из частей информации.
Выходные данные
Выведите единственное число — минимальное количество смен направлений движения, которое придется сделать роботу для сбора всех n частей информации.
Примечание
В первом примере собрать все части информации оптимальным образом можно, собрав сначала часть информации в первом компьютере, затем в третьем, затем сменить направление движения и двигаться ко второму компьютеру, и, имея 2 части информации, собрать последнюю часть.
Во втором примере для сбора всех частей оптимальным образом Док может сначала поехать к четвертому компьютеру и получить часть информации, затем, имея одну часть, к пятому компьютеру и получить еще одну часть информации, затем таким же образом ко второму, потом к третьему, и, наконец, к первому. Смены направления произойдут перед движением от пятого ко второму компьютеру, затем от второго к третьему, далее от третьего к первому.
В третьем примере оптимальный порядок сбора частей из компьютеров может выглядеть так: 1->3->4->6->2->5->7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 0
|
1
|
|
2
|
5
4 2 3 0 1
|
3
|
|
3
|
7
0 3 1 0 5 2 6
|
2
|