На тропе подряд расположены n участков. Известно положительное время прохождения каждого участка. Маршрутом называется один или несколько соседних участков. Сколько различных маршрутов можно пройти не более чем за t минут? Маршруты различаются номерами первого или последнего участка. Пустой маршрут не считается.
Формат входных данных
В первой строке записаны n и t (1 ≤ n ≤ 100000, 1 ≤ t ≤ 1000000000). Во второй строке — n целых времён aᵢ (1 ≤ aᵢ ≤ 1000000000) в порядке участков.
Формат выходных данных
Выведите количество подходящих маршрутов. Ответ может превышать 2³¹ − 1; в C++ нужен 64-битный тип.
| № | Входные данные | Выходные данные |
|
1
|
4 5
2 1 3 2
|
7
|