K보다 큰 구간

자연수 $n$개로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어진다. 구간 $[i, j]$ ($1 \le i \le j \le n$)의 합 $a_i + a_{i+1} + \dots + a_j$가 $k$보다 큰 쌍 $(i, j)$의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 수열의 길이 $n$이 주어진다. ($1 \le n \le 100\,000$)

둘째 줄에 수열을 이루는 자연수 $n$개가 공백으로 구분되어 주어진다. 각 자연수는 $100\,000$보다 크지 않다.

셋째 줄에 자연수 $k$가 주어진다. ($1 \le k \le 1\,000\,000\,000$)

구간 합이 $k$보다 큰 쌍 $(i, j)$의 개수를 첫째 줄에 출력한다.