/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
円周が L の円があり、この円周上に点 1,2,\ldots,N が配置されています。i=1,2,\ldots,N-1 に対し、点 i+1 は点 i から時計回りに円周上を d_i 進んだ位置にあります。
整数の組 (a,b,c)\ (1\leq a\lt b\lt c\leq N) であって、以下の 2 つをともに満たすものの個数を求めてください。
- 3 点 a,b,c はすべて異なる位置にある。
- 3 点 a,b,c を頂点とする三角形は正三角形である。
制約
- 3\leq L,N\leq 3\times 10^5
- 0\leq d_i\lt L
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L
d_1 d_2 \ldots d_{N-1}
出力
答えを出力せよ。
入力例 1
5 6 4 3 1 2
出力例 1
2
5 つの点の配置は以下のようになります。条件を満たすのは (a,b,c)=(1,2,4),(1,4,5) の 2 つです。
入力例 2
4 4 1 1 1
出力例 2
0
入力例 3
10 12 4 4 5 7 1 7 0 8 5
出力例 3
13
Score : 300 points
Problem Statement
There is a circle with circumference L, and points 1,2,\ldots,N are placed on this circle. For i=1,2,\ldots,N-1, point i+1 is located at a position that is d_i clockwise from point i on the circle.
Find the number of integer triples (a,b,c)\ (1\leq a\lt b\lt c\leq N) that satisfy both of the following conditions:
- The three points a, b, and c are all at different positions.
- The triangle with vertices at the three points a, b, and c is an equilateral triangle.
Constraints
- 3\leq L,N\leq 3\times 10^5
- 0\leq d_i\lt L
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L
d_1 d_2 \ldots d_{N-1}
Output
Output the answer.
Sample Input 1
5 6 4 3 1 2
Sample Output 1
2
The arrangement of the five points is as follows. Two pairs satisfy the conditions: (a,b,c)=(1,2,4),(1,4,5).
Sample Input 2
4 4 1 1 1
Sample Output 2
0
Sample Input 3
10 12 4 4 5 7 1 7 0 8 5
Sample Output 3
13