Самая короткая «сытая» серия перекусов

После школы ты заходишь в магазин несколько раз подряд. В i-й заход ты покупаешь перекусы на сумму a[i].

Ты хочешь выбрать подряд идущие заходы так, чтобы общая сумма была не меньше S, и при этом таких заходов было как можно меньше.

Если ни один подряд идущий отрезок не набирает сумму хотя бы S, считай, что план не удался.

Формат ввода

• В первой строке дано целое число t — количество наборов данных.
• Далее идут t наборов данных.
• В каждом наборе данных в первой строке два целых числа n и S.
• Во второй строке n целых чисел a1, a2, ..., an.

Формат вывода Для каждого набора данных выведи одно целое число — минимальную длину подряд идущего отрезка с суммой >= S. Если такого отрезка нет, выведи 0.

Ответ для каждого набора данных выведи с новой строки.

Ограничения

• 1 <= t <= 4
• 1 <= n <= 20000
• 1 <= S <= 10^9
• 1 <= ai <= 10^5
• Сумма значений n по всем наборам данных не превышает 20000.
• В этой задаче могут встречаться значения, которые в некоторых языках требуют 64-битный тип (int64). В Python это уже учтено.

Пример Ввод:

3
1 1
1
1 2
1
5 5
1 1 1 1 1

Вывод:

1
0
5

Ключевое наблюдение: все a[i] >= 1, значит сумма на отрезке монотонно меняется при движении границ. Если расширять окно вправо, сумма только растёт; если сдвигать левую границу вправо, сумма только уменьшается. Поэтому можно искать ответ одним проходом: как только сумма стала >= S, пытаемся сжать окно слева, не теряя условие — так и получаем минимальную длину для каждого правого конца.

Почему работает приём «два указателя»: каждая граница двигается только вперёд, назад не нужно, потому что «лишние» элементы слева уже точно не помогут сделать окно короче при том же правом конце.

План:

• Заведи l = 0, cur_sum = 0, best = n + 1.
• Иди правой границей r от 0 до n-1:
• добавь a[r] в cur_sum.
• пока cur_sum >= S, обновляй ответ и сжимай окно слева:
• best = min(best, r - l + 1)
• cur_sum -= a[l], l += 1
• Если best не изменился, выведи 0, иначе best.

Сложность: O(n) по времени (каждый индекс уходит из окна максимум один раз) и O(1) по памяти.

Частая ошибка: использовать if cur_sum >= S вместо while — тогда окно не сожмётся до минимума, и ответ получится больше нужного.