Монокарп играет в стратегическую компьютерную игру Rage of Empires II: Definitive Edition. Сейчас он собирается атаковать своего оппонента в игре, но вот незадача — противник успел построить стену, и войска Монокарпа не могут попасть в лагерь противника!
Стена состоит из \(n\) секций, расположенных в ряд и пронумерованных слева направо, начиная с единицы. Прочность \(i\)-й секции изначально равна \(a_i\). Если прочность какой-то секции станет равной \(0\) или станет отрицательной, то эта секция будет считаться разрушенной.
Для успешной атаки Монокарп должен разрушить хотя бы две секции стены (любые две: возможно, соседние, но не обязательно). Для этого собирается использовать специальное осадное орудие — онагр. Когда онагр стреляет по секции стены, он наносит \(2\) единицы урона этой секции и по \(1\) единице урона соседним секциям. Иными словами, если онагр стреляет по секции \(x\), прочность секции \(x\) уменьшается на \(2\), а прочности секций \(x - 1\) и \(x + 1\) (если они существуют) уменьшаются на \(1\) каждая.
Монокарп может стрелять из онагра по любым секциям любое количество раз, в том числе можно стрелять по уже разрушенной секции.
Монокарп хочет посчитать минимальное количество выстрелов онагра, необходимое, чтобы разрушить хотя бы две секции стены. Помогите ему!
Выходные данные
Выведите целое число — минимальное количество выстрелов онагра, необходимое, чтобы разрушить хотя бы две секции стены.
Примечание
В первом примере можно разрушить \(2\)-ю и \(4\)-ю секции стены за \(10\) выстрелов, например, совершив все \(10\) выстрелов в третью секцию. После этого прочности секций будут равны \([20, 0, 10, 0, 20]\). Существует и другой способ. Можно сначала выстрелить \(5\) раз во \(2\)-ю секцию и затем еще \(5\) раз в \(4\)-ю секцию. После этого прочности секций будут равны \([15, 0, 20, 0, 15]\).
Во втором примере достаточно одного выстрела по \(2\)-й секции. После этого \(1\)-я и \(3\)-я секции будут разрушены.
В третьем примере можно, например, выстрелить два раза во \(2\)-ю секцию (после этого прочности секций станут равны \([5, 2, 4, 8, 5, 8]\)), а затем выстрелить два раза в \(3\)-ю секцию (после этого прочности секций станут равны \([5, 0, 0, 6, 5, 8]\)). Таким образом, после четырех выстрелов будут разрушены \(2\)-я и \(3\)-я секции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
20 10 30 10 20
|
10
|
|
2
|
3
1 8 1
|
1
|
|
3
|
6
7 6 6 8 5 8
|
4
|
|
4
|
6
14 3 8 10 15 4
|
4
|
|
5
|
4
1 100 100 1
|
2
|
|
6
|
3
40 10 10
|
7
|