THE HOTEL WENT MAD

The island's hotel is not doing well in terms of clientele. A little due to the pandemic, a little due to the overall poor economic situation, the owner decided that something needs to change to attract more customers. A friend suggested that instead of having fixed prices, he should adjust the room rate day by day based on demand. With the help of the accounting department, which keeps a record of demand for previous years, the meteorological service, and his friend who estimates the future demand, the owner determined the prices he will offer for his rooms each day. In fact, on some days, he decided to offer the rooms for free to attract even more customers.

Thanasis wants to take a vacation this year and has always wanted to visit the island. When he found out about the room prices at the hotel, he made up his mind. However, his finances are not very good lately. He can spend a maximum of S euros in total, and, as a matter of principle, he is not willing to pay more than T euros on any given day.

With these constraints, help Thanasis count all possible time intervals he can stay at the hotel.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the hotel room prices for a period of N days, as well as the limits S and T set by Thanasis, and prints the number of different possible time intervals that satisfy the above constraints.

Input Files:

The input files named crazyhotel.in are text files with the following structure: The first line contains three integers separated by a space: the number N of days the hotel is available, the total amount S that Thanasis can spend, and the maximum amount T he is willing to pay per day. The second line contains N integers, separated in pairs by a space: the prices A~\mathbf{_1}~, A~\mathbf{_2}~, ..., A~\mathbf{_N}~ of the hotel rooms each day.

Output Files:

The output files named crazyhotel.out are text files with the following structure. They contain exactly one line that contains an integer: the number of different time intervals that Thanasis can stay at the hotel.

Constraints:

• 1 ~\le~ Ν ~\le~ 1.000.000
• 0 ~\le~ Α~_i~ ~\le~ 1.000
• 0 ~\le~ S ~\le~ 1.000.000.000
• 0 ~\le~ T ~\le~ 1.000
• The correct answer will not exceed 2.000.000.000.

Examples of Input - Output Files:

1o

STDIN (crazyhotel.in)

6 10 7
4 3 6 0 8 2

STDOUT (crazyhotel.out)

9

2o

STDIN (crazyhotel.in)

9 17 7
7 5 6 8 3 6 7 8 4

STDOUT (crazyhotel.out)

12

Explanation of the first example:

The number of days is N = 6. There are nine different time intervals with a total cost not exceeding S = 10 and a maximum daily rate not exceeding T=7. Five of these time intervals last only one day: 4, 3, 6, 0, and 2. Note that the day with a value of 8 > S has been excluded. There are still three intervals that last two days: 4+3, 3+6, 6+0, and one interval that lasts three days: 3+6+0.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: crazyhotel *)

for PASCAL coders

/* USER: username
LANG: C
TASK: crazyhotel */

for C coders

/* USER: username
LANG: C++
TASK: crazyhotel */

for C++ coders

/* USER: username
LANG: Java
TASK: crazyhotel */

for Java coders

# USER: username
# LANG: Python
# TASK: crazyhotel

for Python coders