E. Уничтожение стены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в стратегическую компьютерную игру Rage of Empires II: Definitive Edition. Сейчас он собирается атаковать своего оппонента в игре, но вот незадача — противник успел построить стену, и войска Монокарпа не могут попасть в лагерь противника!

Стена состоит из $$$n$$$ секций, расположенных в ряд и пронумерованных слева направо, начиная с единицы. Прочность $$$i$$$-й секции изначально равна $$$a_i$$$. Если прочность какой-то секции станет равной $$$0$$$ или станет отрицательной, то эта секция будет считаться разрушенной.

Для успешной атаки Монокарп должен разрушить хотя бы две секции стены (любые две: возможно, соседние, но не обязательно). Для этого собирается использовать специальное осадное орудие — онагр. Когда онагр стреляет по секции стены, он наносит $$$2$$$ единицы урона этой секции и по $$$1$$$ единице урона соседним секциям. Иными словами, если онагр стреляет по секции $$$x$$$, прочность секции $$$x$$$ уменьшается на $$$2$$$, а прочности секций $$$x - 1$$$ и $$$x + 1$$$ (если они существуют) уменьшаются на $$$1$$$ каждая.

Монокарп может стрелять из онагра по любым секциям любое количество раз, в том числе можно стрелять по уже разрушенной секции.

Монокарп хочет посчитать минимальное количество выстрелов онагра, необходимое, чтобы разрушить хотя бы две секции стены. Помогите ему!

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

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество секций в стене.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$), где $$$a_i$$$ равно изначальной прочности $$$i$$$-й секции стены.

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

Выведите целое число — минимальное количество выстрелов онагра, необходимое, чтобы разрушить хотя бы две секции стены.

Примеры
Входные данные
5
20 10 30 10 20
Выходные данные
10
Входные данные
3
1 8 1
Выходные данные
1
Входные данные
6
7 6 6 8 5 8
Выходные данные
4
Входные данные
6
14 3 8 10 15 4
Выходные данные
4
Входные данные
4
1 100 100 1
Выходные данные
2
Входные данные
3
40 10 10
Выходные данные
7
Примечание

В первом примере можно разрушить $$$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$$$-я секции.