В очередной день Егору стало скучно, и он решил чем-нибудь заняться. Но так как у него нет друзей, он придумал игру, в которую и хочет сыграть.
У Егора есть колода из $$$n$$$ карт, на $$$i$$$-й карте сверху написано какое-то число $$$a_i$$$. Егор хочет сыграть в игру некоторое количество раундов, пока не закончатся карты. В каждом раунде он берет некоторое ненулевое количество карт с верха колоды и заканчивает раунд. Если сумма чисел на набранных за раунд картах находится между $$$l$$$ и $$$r$$$ включительно, то раунд считается выигранным, иначе проигранным.
Егор знает, в каком порядке идут числа на картах в колоде. Помогите Егору узнать, какое наибольшее количество раундов он сможет выиграть в такой игре. Обратите внимание, что Егор не обязан выигрывать раунды подряд.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le l \le r \le 10^9$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числа на картах сверху вниз.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^{5}$$$.
Для каждого набора входных данных выведите одно число — наибольшее количество раундов, которое сможет выиграть Егор.
85 3 102 1 11 3 710 1 517 8 12 11 7 11 21 13 10 83 4 53 4 28 12 2510 7 5 13 8 9 12 72 3 35 29 7 92 10 5 1 3 7 6 2 31 8 1095 5 61 4 2 6 4
3 0 1 4 0 3 1 2
В первом наборе входных данных Егор может выиграть $$$3$$$ раунда:
Во втором наборе входных данных Егор не сможет выиграть ни одного раунда, как бы он не старался.
В третьем наборе входных данных можно каждый раунд брать по одной карте, тогда первый и третий раунд будут проигрышными, а второй — выигрышным.
В четвертом наборе данных можно брать по две карты каждый раунд и всегда выигрывать.
Название |
---|