訂機票


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

Comments

There are no comments at the moment.