Nathan 最近想去日本玩，於是他調查了接下來 \(n\) 天的機票價格，他發現第 \(i\) 天的機票不管是去程還是回程都是 \(a_i\) 元。因為 Nathan 多多少少還是有工作要處理，所以他預期只會去日本 \(l\) 天到 \(r\) 天，這裡天數的算法是 \((\)回國的日期\()-(\)去日本的日期\()+1\)。不只如此，Nathan 還計劃花在機票的價錢不能超過 \(k\)，不然他就沒錢請 Fysty 等人吃飯了。

請問他有幾種去程和回程的日期組合？即有多少數對 \((i,j)\) 滿足第 \(i\) 天去日本，第 \(j\) 天回國所花的機票價錢不超過 \(k\)？

註：請不要考慮時區問題，可以假設飛機在哪天起飛就會在哪天降落。

Input

第一行輸入四個正整數 \(n,l,r,k\ (1\le n,k\le 2\cdot 10^5,1\le l\le r\le n)\)。

第二行輸入 \(n\) 個正整數 \(a_1,a_2,\ldots,a_n\ (1\le a_i\le 2\cdot 10^5)\)。

Output

輸出一個整數，代表有多少對去程和回程的日期組合。

Constraints

第 \(1\) 組測資：\(1\le n\le 1000\)。(\(10\%\))

第 \(2\) 組測資：\(l=1,r=n,1\le a_i\le 10\)。(\(10\%\))

第 \(3\) 組測資：\(l=1,r=n\)。(\(30\%\))

第 \(4\) 組測資：無特別限制。(\(50\%\))

Sample Input 1

8 1 2 5
1 10 2 3 3 4 1 5

Sample Output 1

5

Sample Input 2

7 1 7 10
1 2 3 4 5 6 7

Sample Output 2

22