MINIEYE's engineer M is preparing to perform a real vehicle test on the recently developed ADAS product. Now he has found a path and divides it into N segments. Each segment has its own test value.
He will select several consecutive segments for testing. In order to enhance the credibility, the number of road segments must be greater than or equal to L; but long-time driving is not good for driver, so the number of road segments must be less than or equal to R; in order to ensure the test effect, the sum of the test values of the chosen segments must be greater than or equal to S.
M wants you to tell him how many kinds of test plans meet the above conditions.
The first line contains four integers, N, L, R, S (0 < N ≤ 106, 0 < L ≤ R ≤ N, -1011 ≤ S ≤ 1011).
The second line contains N integers, the ith integer Ci (-105 ≤ Ci ≤ 105) indicates the test value of the ith road segment.
Output a single integer, the number of test plans, in a single line.