给定一个正 $N$ 边形。将其中任意一条边标记为边 1，然后按顺时针方向依次标记为边 $2, 3, \dots, N$。在边 $i$ 上有 $A_i$ 个特殊点。这些点的位置使得边 $i$ 被等分为 $A_i + 1$ 段。

例如，假设你有一个正 4 边形，即正方形。下图展示了当 $A = [3, 1, 4, 6]$ 时，特殊点在每条边上的分布情况。最上方的一条边被标记为边 1。

你希望在满足以下要求的前提下，尽可能多地创建非退化三角形。每个三角形由 3 个不同的特殊点（不一定来自不同的边）作为顶点组成。每个特殊点最多只能成为 1 个三角形的顶点。所有三角形之间不得相交。

确定你可以创建的非退化三角形的最大数量。

如果一个三角形的面积为正，则称其为非退化三角形。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 200\,000$)。 下一行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 2 \cdot 10^9$)。

输出格式

输出一个整数，表示你可以创建的非退化三角形的最大数量。

样例

输入 1

4
3 1 4 6

输出 1

4

说明 1

下图展示了一种可以达到最大非退化三角形数量的构造方案。

输入 2

6
1 2 1 2 1 2

输出 2

3

说明 2

下图展示了一种可以达到最大非退化三角形数量的构造方案。

输入 3

3
1 1 1

输出 3

1