정삼각형 세기

면접 대비

시간 제한2초메모리 제한512 MB

요약

원 위에 놓인 점들 사이의 호 길이가 주어질 때, 주어진 점을 꼭짓점으로 하는 정삼각형의 개수를 센다.

난이도: 보통10점 중 4점
유형: 누적 합, 수학, 투 포인터
정답자: 아직 제출이 없습니다

문제

원 위에 점 $N$ 개가 놓여 있다. 주어진 점을 꼭짓점으로 하는 서로 다른 정삼각형이 몇 개인지 세는 프로그램을 작성하라.

점의 위치는 원의 둘레를 따라 이웃한 두 점 사이 호의 길이로 정해진다. 아래 그림의 (a)는 이웃한 호의 길이가 차례로 4, 2, 4, 2, 2, 6, 2, 2인 점 8개를 나타내고, (b)는 그 점들로 만들 수 있는 정삼각형 2개를 나타낸다.

입력

첫째 줄에 점의 개수 $N$ 이 주어진다. 둘째 줄에 정수 $X_1, X_2, \dots, X_N$ 이 주어진다. $1 \le i \le N-1$ 인 $i$ 에 대해 $X_i$ 는 점 $i$ 와 점 $i+1$ 사이 호의 길이이고, $X_N$ 은 점 $N$ 과 점 $1$ 사이 호의 길이다. 점 $1$ 부터 점 $N$ 까지는 원의 둘레를 따라 한 방향으로 번호가 붙어 있다.

제한

$3 \le N \le 10^5$
$1 \le X_i \le 10^3$ ( $1 \le i \le N$ )

출력

주어진 점을 꼭짓점으로 하는 서로 다른 정삼각형의 개수를 한 줄에 출력한다.

예제2

예제 1
입력
```
8
4 2 4 2 2 6 2 2
```
예상 출력
```
2
```
예제 2
입력
```
6
3 4 2 1 5 3
```
예상 출력
```
1
```