AT_awc0003_d 連続練習日数

Takahashi is the manager of the track and field club, and he manages the practice records of the club members. The track and field club has a practice period of $ N $ days, and each day is numbered from $ 1 $ to $ N $ . On day $ i $ $ (1 \leq i \leq N) $ , a positive integer $ A_i $ representing the "practice intensity" for that day is recorded. According to the club's rules, a period consisting of $ r - l + 1 $ consecutive days from day $ l $ to day $ r $ is called an "achievement period" and is specially recognized if its length is at least $ K $ days and the total practice intensity within the period is at least the target value $ M $ . Takahashi wants to find out how many achievement periods qualify for recognition. Specifically, find the number of integer pairs $ (l, r) $ that satisfy all of the following conditions: - $ 1 \leq l \leq r \leq N $ - $ r - l + 1 \geq K $ (the length of the period is at least $ K $ days) - $ A_l + A_{l+1} + \cdots + A_r \geq M $ (the total practice intensity within the period is at least $ M $ )

> $ N $ $ K $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ - The first line contains an integer $ N $ representing the number of days in the practice period, an integer $ K $ representing the minimum length of a period, and an integer $ M $ representing the target value for the total practice intensity, separated by spaces. - The second line contains $ N $ integers $ A_1, A_2, \ldots, A_N $ representing the practice intensity for each day, separated by spaces.

Print the number of integer pairs $ (l, r) $ that satisfy the conditions, on a single line.

### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq K \leq N $ - $ 1 \leq M \leq 10^{14} $ - $ 1 \leq A_i \leq 10^9 $ $ (1 \leq i \leq N) $ - All input values are integers