← 返回题目列表

AtCoder · abc409_c

F. 等边三角形

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

分数: 300 点

问题陈述

有一个圆,有周长 L,和点 1,2,\ldots,N 放置在这个圆圈上。对于 i=1,2,\ldots,N-1,点 i+1 位于以下位置 d_i 从点顺时针 i 在圆圈上。

查找整数三元组的数量 (a,b,c)\ (1\leq a\lt b\lt c\leq N) 满足以下两个条件:

  • 三点 a, b,和 c 都在不同的位置。
  • 顶点位于三点的三角形 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

五点安排如下。两对满足条件: (a,b,c)=(1,2,4),(1,4,5).


示例输入 2

4 4
1 1 1

示例输出 2

0

示例输入 3

10 12
4 4 5 7 1 7 0 8 5

示例输出 3

13