给你一个规则的 $$$N$$$ 边多边形。将任意一边标记为边 $$$1$$$,然后按顺时针顺序将下边标记为边 $$$2$$$、$$$3$$$、$$$\dots$$$、$$$N$$$。 $$$i$$$ 侧有 $$$A_i$$$ 特殊点。这些点的位置使得 $$$i$$$ 边被分成长度相等的 $$$A_i + 1$$$ 段。
例如,假设您有一个规则的 $$$4$$$ 边多边形,即正方形。下图显示了当 $$$A = [3, 1, 4, 6]$$$ 时特殊点如何位于每条边内。最上边标记为边 $$$1$$$。
您想要创建尽可能多的非退化三角形,同时满足以下要求。每个三角形由 $$$3$$$ 不同的特殊点(不一定来自不同的边)作为其角组成。每个特殊点最多只能成为$$$1$$$三角形的角。所有三角形不得彼此相交。
确定可以创建的非退化三角形的最大数量。
如果三角形的面积为正,则该三角形是非退化的。
输入
第一行由一个整数 $$$N$$$ ($$$3 \leq N \leq 200\,000$$$) 组成。
以下行由 $$$N$$$ 整数 $$$A_i$$$ ($$$1 \leq A_i \leq 2 \cdot 10^9$$$) 组成。
输出
输出一个整数,表示您可以创建的非退化三角形的最大数量。
示例
输入 #1
4 3 1 4 6
输出 #1
4
输入 #2
6 1 2 1 2 1 2
输出 #2
3
输入 #3
3 1 1 1
输出 #3
1
注意
示例输入/输出#1 的说明
实现非退化三角形最大数量的一种可能的构造如下图所示。
示例输入/输出 #2 的说明
实现非退化三角形最大数量的一种可能的构造如下图所示。