← 返回题目列表

Codeforces · 1906/M

M. 三角形结构

中文机器翻译题面 查看原题

给你一个规则的 $$$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 的说明

实现非退化三角形最大数量的一种可能的构造如下图所示。