問題文

長さ 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 点が与えられます。

入力例 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