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].\)