Segments greater than K

Time limit2sMemory limit512 MB

Summary

Count the contiguous subarrays whose sum exceeds k.

Level: Medium5 of 10
Topics: Two pointers, Prefix sum
Solved: No attempts yet

Problem

A sequence of $n$ natural numbers $a_1, a_2, \dots, a_n$ is given. Write a program that counts the pairs $(i, j)$ with $1 \le i \le j \le n$ whose segment sum $a_i + a_{i+1} + \dots + a_j$ is greater than $k$ .

Input

The first line contains the length of the sequence, $n$ . ( $1 \le n \le 100\,000$ )

The second line contains the $n$ natural numbers of the sequence, separated by spaces. No number is greater than $100\,000$ .

The third line contains a natural number $k$ . ( $1 \le k \le 1\,000\,000\,000$ )

Output

Print the number of pairs $(i, j)$ whose segment sum is greater than $k$ on the first line.

Examples2

Example 1
Input
```
5
1 2 3 2 1
7
```
Expected output
```
3
```
Example 2
Input
```
5
1 1 1 1 1
2
```
Expected output
```
6
```