Задача для Зеника

Обмеження: 2 сек., 256 МіБ

Сьогодні Марічка розповіла Зенику одну цікаву задачу.

Є масив, який складається з \(n\) елементів. Скільки існує проміжків \([l, r]\) таких, що:

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

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

Зеник хоче вразити дівчину, тому з усіх зусиль намагається розв’язати цю задачу.

А вам під силу ця задача?

Вхідні дані

У першому рядку задано ціле число \(n\) — розмір масиву.

У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.

У третьому рядку задано ціле число \(k\).

Вихідні дані

У єдиному рядку виведіть ціле число — відповідь на задачу. Зверніть увагу на те, що відповідь може перевищувати \(10^{9}\).

Обмеження

44% тестів:

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

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

56% тестів:

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 1 1 2 3	6

Примітки

Існує 6 проміжків, що задовольняють умову задачі:

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