给定一个正n边形，第i条边上有ai个特殊点，将这条边平均分成ai+1份。
如下图为正四边形(正方形)及每条边上的特殊点A=[3,1,4,6]。

现在请你在满足以下条件的前提下构造尽量多的三角形：

•  三角形的顶点是某条边上的特殊点
•  三角形不能相交
•  一个特殊点最多成为一个三角形的顶点。

第一行为正整数n(3≤n≤200000).

下一行为N个整数数ai(1≤ai≤2e9).

输出一个整数，表示最多能构造的三角形的数量.

4
3 1 4 6

4

测试样例2：
输入：
6
1 2 1 2 1 2
输出：
3

测试样例3：
输入：
3
1 1 1
输出：
1


测试样例1，可进行如下方式构造。

测试样例2，可进行如下方式构造。