← 返回题目列表

AtCoder · cpsco2019_s1_h

H. 最高和结束

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

配点 : 800 点

問題文

长度 N 整数序列 给出了 A_1, A_2, \ldots, A_N 和整数 有 X 。 满足以下所有条件的整数 计算对的数量 (l,\ m,\ r) 。 在

  • 1\le l \le m\le r\le N
  • A_l + A_m + A_r = X
  • A_m 满足 l\le i\le r 中 它是 A_i 的最大值。

制約

  • 1\le N\le 10^5
  • 0\le X\le 3\times 10^5
  • 0\le A_i\le 10^5
  • 所有输入均为整数

部分点

这个问题有部分要点。 如果您正确回答满足

  • N\le 2000 的输入, 将奖励300 积分。

入力

输入是按以下格式从标准输入给出的。

N\ X
A_1\ A_2\ \ldots\ A_N

出力

满足条件的对数为 请在 1 行输出。


入力例 1

6 9
1 2 4 4 3 2

出力例 1

6

(l,\ m,\ r)=(1,3,3), (1,3,4), (1,4,4), (2,3,5), (2,4,5), (5,5,5) 的 6 一。 满足


入力例 2

3 0
0 0 0

出力例 2

10

入力例 3

10 15
3 1 4 1 5 9 2 6 5 3

出力例 3

7