Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Juicer

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKolya is going to make fresh orange juice. He has *n* oranges of sizes *a*_{1}, *a*_{2}, ..., *a*_{n}. Kolya will put them in the juicer in the fixed order, starting with orange of size *a*_{1}, then orange of size *a*_{2} and so on. To be put in the juicer the orange must have size not exceeding *b*, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than *d*. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input

The first line of the input contains three integers *n*, *b* and *d* (1 ≤ *n* ≤ 100 000, 1 ≤ *b* ≤ *d* ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value *d*, which determines the condition when the waste section should be emptied.

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output

Print one integer — the number of times Kolya will have to empty the waste section.

Examples

Input

2 7 10

5 6

Output

1

Input

1 5 10

7

Output

0

Input

3 10 10

5 7 7

Output

1

Input

1 1 1

1

Output

0

Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2021 13:37:53 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|