## Problem for Cengiz

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Fahri has an interesting problem for Cengiz. There is an array of $$N$$ elements $$a_1, a_2, ..., a_N$$. Count the number of intervals $$[l, r]$$ such that

• $$1 ≤ l ≤ r ≤ N$$,
• $$a_l + a_{l+1} + ... + a_{r-1} + a_r < K$$.

Could you help Cengiz to solve this problem?

Input

The first line contains integer $$N$$.

The next line contains $$N$$ integers $$a_1, a_2,... a_N$$ separated with single spaces.

The following line contains integer $$K$$.

Output

Print the number of intervals.

Constraints

• $$1 ≤ N ≤ 2 · 10^5$$
• $$-10^9 ≤ a_i ≤ 10^9$$
• $$−10^9 ≤ K ≤ 10^9$$

Samples

Input(stdin)

4
1 1 1 2
3

Output(stdout)

6

Notes

While solving the sample Cengiz counts six intervals:

$$[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3].$$