삼각형 만들기

정$N$각형이 주어진다. 임의의 한 변을 1번 변으로 하고, 거기서 시계 방향으로 다음 변을 2, 3, ..., $N$번 변으로 번호를 매긴다. $i$번 변 위에는 $A_i$개의 특별한 점이 있으며, 이 점들은 $i$번 변을 길이가 모두 같은 $A_i + 1$개의 구간으로 나누도록 놓여 있다.

예를 들어 정사각형(정$4$각형)에서 $A = [3, 1, 4, 6]$이면, 각 변 위 특별한 점의 위치는 아래 그림과 같다. 가장 위쪽 변이 1번 변이다.

다음 조건을 지키면서 넓이가 0이 아닌 삼각형을 최대한 많이 만들려고 한다. 각 삼각형은 서로 다른 특별한 점 3개를 꼭짓점으로 가진다(세 점이 반드시 같은 변 위에 있을 필요는 없다). 각 특별한 점은 최대 1개의 삼각형의 꼭짓점이 될 수 있다. 모든 삼각형은 서로 교차하면 안 된다.

만들 수 있는 넓이가 0이 아닌 삼각형의 최대 개수를 구하라.

삼각형의 넓이가 양수이면 넓이가 0이 아닌 삼각형이다.

첫 줄에 정수 $N$($3 \le N \le 200\,000$)이 주어진다.

다음 줄에 $N$개의 정수 $A_i$($1 \le A_i \le 2 \cdot 10^9$)가 주어진다.

만들 수 있는 넓이가 0이 아닌 삼각형의 최대 개수를 정수 하나로 출력한다.