配点 : $600$ 点

問題文

長さ $N$ の整数列 $a =$ {$a_1, a_2, \cdots , a_N$} と、整数 $K$ が与えられます。

$a$ の空でない連続する部分列 {$a_l, a_{l+1}, \cdots , a_r$} $(1 \leq l \leq r \leq N)$ は $N(N+1)/2$ 個存在します。これらのうち、算術平均が $K$ 以上であるものは何個あるでしょうか？

制約

• 入力値はすべて整数である。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq a_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$a_1$

$a_2$

$:$

$a_N$

出力

$a$ の空でない連続する部分列のうち、算術平均が $K$ 以上であるものの個数を出力せよ。

3 6
7
5
7

5

以下に、$a$ のすべての空でない連続する部分列を示します。

• {$a_1$} = {$7$}
• {$a_1, a_2$} = {$7, 5$}
• {$a_1, a_2, a_3$} = {$7, 5, 7$}
• {$a_2$} = {$5$}
• {$a_2, a_3$} = {$5, 7$}
• {$a_3$} = {$7$}

これらの平均はそれぞれ $7$, $6$, $19/3$, $5$, $6$, $7$ であり、このうち $6$ 以上であるものは $5$ 個です。なお、{$a_1$} と {$a_3$} は含まれる要素の値では区別できませんが、これらは個別に数えます。

1 2
1

0

7 26
10
20
30
40
30
20
10

13