Problem for Zenik

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Today Marichka told Zenik an interesting problem.

There is an array consisting of \(n\) elements. How many intervals \([l, r]\) exist such that:

1. \(1 \le l \le r \le n\),

2. \(a_l + a_{l+1} + \ldots + a_{r-1} + a_r < k\).

Zenik wants to impress the girl, so he is trying his best to solve this problem.

Can you handle this problem too?

Input

The first line contains an integer \(n\) — the size of the array.

The second line contains \(n\) integers \(a_i\) — the elements of the array.

The third line contains an integer \(k\).

Output

Print a single integer in a single line — the answer to the problem. Pay attention that the answer can exceed \(10^{9}\).

Constraints

44% of tests:

\(1 \le n \le 1474\),

\(|a_i|, |k| \le 10^{6}\),

56% of tests:

\(1 \le n \le 147474\),

\(|a_i|, k \le 10^{9}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 1 1 2 3	6

Notes

There are 6 intervals satisfying the problem condition:

\([1, 1]\), \([2, 2]\), \([3, 3]\), \([4, 4]\), \([1, 2]\), \([2, 3]\).