题目描述

光头强玩“帝国之怒II：最终版”——一款战略电脑游戏。现在他正计划在游戏中攻击对手，但由于对手已经筑起了一堵墙，光头强的部队无法进入对手的领土。

城墙由 $n$ 个部分组成，第 $i$ 个部分的初始耐久度为 $a_i$。如果某个部分的耐久度变为 0 或更少，则认为该部分已被打破。

为了攻击对手，光头强需要攻破城墙中至少两个部分（任何两个部分：可能相邻，也可能不相邻）。他计划使用投石车——一种特殊的攻城武器。投石车可以用来射击城墙的任何部分；射击会对目标部分造成 2 点伤害，对相邻部分造成 1 点伤害。换句话说，如果投石车射击 $x$ 部分，则 $x$ 部分的耐久度减少 2，而 $x-1$ 部分和 $x+1$ 部分（如果存在）的耐久度各减少 1。

光头强可以对任何部分进行任意次数的射击，他甚至可以射击已被打破的部分。

请帮助光头强计算打破至少两个部分所需的最小投石车射击次数。

输入格式

第一行包含一个整数 $n(2 ≤ n ≤ 2×10^5)$ — 墙的部分数。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n (1 ≤ a_i ≤ 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

样例说明

在第一个例子中，可以通过射击第三个部分 $10$ 次来在 $10$ 次中打破第 $2$ 个和第 $4$ 个部分。之后，耐久度变为 $[20,0,10,0,20]$。另一种方法是在第 $2$ 个部分射击 $5$ 次，另外在第 $4$ 个部分射击 $5$ 次。之后，耐久度变为 $[15,0,20,0,15]$。

在第二个例子中，只需射击第 $2$ 个部分一次即可。然后第 $1$ 个和第 $3$ 个部分将被打破。

在第三个例子中，只需射击第 $2$ 个部分两次（然后耐久度变为 $[5,2,4,8,5,8]$），然后再射击第 $3$ 个部分两次（然后耐久度变为 $[5,0,0,6,5,8]$）。因此，只需要四个射击就足以打破第 $2$ 个和第 $3$ 个部分。