В очередной день Егору стало скучно, и он решил чем-нибудь заняться. Но так как у него нет друзей, он придумал игру, в которую и хочет сыграть.
У Егора есть колода из \(n\) карт, на \(i\)-й карте сверху написано какое-то число \(a_i\). Егор хочет сыграть в игру некоторое количество раундов, пока не закончатся карты. В каждом раунде он берет некоторое ненулевое количество карт с верха колоды и заканчивает раунд. Если сумма чисел на набранных за раунд картах находится между \(l\) и \(r\) включительно, то раунд считается выигранным, иначе проигранным.
Егор знает, в каком порядке идут числа на картах в колоде. Помогите Егору узнать, какое наибольшее количество раундов он сможет выиграть в такой игре. Обратите внимание, что Егор не обязан выигрывать раунды подряд.
Выходные данные
Для каждого набора входных данных выведите одно число — наибольшее количество раундов, которое сможет выиграть Егор.
Примечание
В первом наборе входных данных Егор может выиграть \(3\) раунда:
- В первом раунде взять \(2\) верхние карты со значениями \(2\) и \(1\) и выиграть, так как в сумме они дают \(3\). Колода после этого будет выглядеть так: \([11, 3, 7]\).
- Во втором раунде взять верхнюю карту и проиграть, так как ее значение \(11\) больше \(r = 10\). Колода после этого будет выглядеть так: \([3, 7]\).
- В третьем раунде взять верхнюю карту со значением \(3\) и выиграть. Колода после этого будет выглядеть так: \([7]\).
- После этого в четвертом раунде Егору остается только взять последнюю карту в колоде со значением \(7\) и снова выиграть.
Во втором наборе входных данных Егор не сможет выиграть ни одного раунда, как бы он не старался.
В третьем наборе входных данных можно каждый раунд брать по одной карте, тогда первый и третий раунд будут проигрышными, а второй — выигрышным.
В четвертом наборе данных можно брать по две карты каждый раунд и всегда выигрывать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5 3 10
2 1 11 3 7
10 1 5
17 8 12 11 7 11 21 13 10 8
3 4 5
3 4 2
8 12 25
10 7 5 13 8 9 12 7
2 3 3
5 2
9 7 9
2 10 5 1 3 7 6 2 3
1 8 10
9
5 5 6
1 4 2 6 4
|
3
0
1
4
0
3
1
2
|