Вы играете в одну очень популярную компьютерную игру. Очередной уровень состоит из \(n\) подряд идущих локаций, пронумерованных от \(1\) до \(n\), каждая из которых содержит либо землю, либо воду. Известно, что первая и последняя локации содержат землю, и ваша задача — попасть с первой локации на последнюю, при этом если вы попадете на локацию с водой, то вы погибнете, так что вы можете перемещаться только между локациями с землей.
Вы можете бесплатно совершать прыжки между соседними локациями, а также не более одного раза совершить прыжок с любой локации с землей \(i\) на любую локацию с землей \(i + x\), затратив на это \(x\) монет (\(x \geq 0\)).
Ваша задача — вывести минимальное количество монет, необходимое для того, чтобы переместиться с первой локации на последнюю.
Обратите внимание, что это всегда возможно, так как и первая, и последняя локация являются локациями с землей.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В первом наборе входных данных достаточно сделать один бесплатный прыжок с первой локации на вторую, которая также последняя, поэтому ответ \(0\).
Во втором наборе единственный способ добраться с первой локации до последней — перепрыгнуть между ними сразу, что будет стоить \(4\) монеты.
В третьем наборе можно за \(2\) монеты прыгнуть с первой локации на третью, а затем бесплатно прыгнуть на четвертую, поэтому ответ \(2\). Можно показать, что это оптимальный способ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 1
5
1 0 1 0 1
4
1 0 1 1
|
0
4
2
|