在本题中，给定两个固定参数 $k$ 和 $W$。

我们称一个长度为 $2k$ 的序列 $a_1, a_2, \dots, a_{2k}$ 为 shaky，当且仅当满足： $$\sum_{i=1}^{k} (k - i + 1)(a_i + a_{2k-i+1}) \geq W$$

我们称一个序列 $b_1, b_2, \dots, b_m$ 为 wavelike，当且仅当： $m \geq 2k$。 它至少包含一个 shaky 子序列。注意，该 shaky 子序列不需要是连续的。

给定一个序列 $s_1, s_2, \dots, s_n$，请从中选出尽可能多的互不相交的 wavelike 连续子序列。注意，选出的连续子序列不需要覆盖整个序列。这里，“连续子序列”指它必须是连续的（即子串）。

输入格式

第一行包含三个整数 $n, k$ 和 $W$ ($2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq \frac{n}{2}, |W| \leq 10^{17}$)。 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$ ($|s_i| \leq 10^6$)。

输出格式

输出一行一个整数，表示能够选出的互不相交的 wavelike 连续子序列的最大数量。

样例

样例输入 1

9 2 25
6 4 3 5 7 1 2 5 8

样例输出 1

2

样例输入 2

9 2 30
6 4 3 5 7 1 2 5 8

样例输出 2

1

样例输入 3

2 1 1
0 0

样例输出 3

0

样例输入 4

2 1 -6
-1 -5

样例输出 4

1