index.md

生日禮物

今天是小愷的生日，因此小愷的爸爸決定帶小愷去買房子當作給他的生日禮物！小愷爸爸帶小愷來到了一條有 $n$ 棟房子的街上，其中第 $i$ 棟房子的價錢為 $a_i$，每棟房子的價錢皆為正整數。

小愷的爸爸原本打算把一整條街上所有的房子都送給小愷，但深知「勝不驕，敗不餒」的道理的他，在深思熟慮下還是決定不這麼做。
他打算給小愷一共 $c$ 元的預算，讓小愷自己決定要買哪些房子，但俗話說的好：「不經一番寒徹骨，焉得梅花撲鼻香」，小愷爸爸並不過多干涉小愷想買哪些房子。
但他卻有一些要求：
1.小愷買的所有房子必須全部彼此相連
2.小愷買的所有房子的總價錢不得和預算 $c$ 相差超過 $k$ 元，也就是說小愷爸爸不希望剩太多錢，也不希望超出預算太多

然而，小愷是一個非常懶的人，因此希望你幫他算出，一共有多少種購房方案可以符合小愷爸爸提出的兩個條件。

輸入

輸入有兩行。
第一行包含三個正整數 $n, c, k$，分別代表房子的數量、買房的預算和小愷爸爸可以接受的價差。
第二行包含 $n$ 個正整數 $a_1,a_2,...,a_n$，其中 $a_i$ 代表第 $i$ 棟房子的價錢。

輸出

輸出一個整數，表示一共有多少種購房方案可以符合小愷爸爸的要求。

輸入限制

• $1\le n\le 2.5\times 10^6$
• $1\le a_i \le 10^9$
• $1\le c\le 10^9$
• $0\le k<c$

\clearpage

子任務

\subtasks

範例輸入

\testfile{0-01.in}

範例輸出

\testfile{0-01.out}