E1. Удаление шаров с помощью слияния (лёгкая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Пейте воду.
— Сунь-Цзы, Искусство стать здоровым программистом

Это лёгкая версия задачи. Единственное отличие в том, что в этой версии $$$x=n$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Вам даны два целых числа $$$n$$$ и $$$x$$$ ($$$x=n$$$). В ряд выстроены $$$n$$$ шаров, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Изначально на $$$i$$$-м шаре записано значение $$$a_i$$$.

Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$ мы определяем функцию $$$f(i)$$$ следующим образом:

  • Предположим, что у вас есть множество $$$S = \{1, 2, \ldots, i\}$$$.

  • В рамках одной операции вам нужно выбрать целое число $$$l$$$ ($$$1 \leq l < i$$$) из $$$S$$$ такое, что $$$l$$$ не является наибольшим элементом $$$S$$$. Предположим, что $$$r$$$ — наименьший элемент $$$S$$$, значение которого больше $$$l$$$.

    • Если $$$a_l > a_r$$$, то установить $$$a_l = a_l + a_r$$$ и удалить $$$r$$$ из $$$S$$$.
    • Если $$$a_l < a_r$$$, то установить $$$a_r = a_l + a_r$$$ и удалить $$$l$$$ из $$$S$$$.
    • Если $$$a_l = a_r$$$, вы выбираете целое число $$$l$$$ или $$$r$$$ для удаления из $$$S$$$:
      • Если вы решили удалить $$$l$$$ из $$$S$$$, вы устанавливаете $$$a_r = a_l + a_r$$$ и удаляете $$$l$$$ из $$$S$$$.
      • Если вы решили удалить $$$r$$$ из $$$S$$$, вы устанавливаете $$$a_l = a_l + a_r$$$ и удаляете $$$r$$$ из $$$S$$$.

  • $$$f(i)$$$ обозначает количество целых чисел $$$j$$$ ($$$1 \le j \le i$$$) таких, что можно получить $$$S = \{j\}$$$, выполнив вышеописанную операцию ровно $$$i - 1$$$ раз.

Для каждого целого числа $$$i$$$ от $$$x$$$ до $$$n$$$ необходимо найти $$$f(i)$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5; x = n$$$) — количество шаров и наименьший индекс $$$i$$$, для которого нужно найти $$$f(i)$$$.

Вторая строка каждого набора входных данных содержит $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — начальное число, записанное на каждом шаре.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите на отдельной строке $$$n-x+1$$$ целых числа, разделенных пробелом, где $$$j$$$-е целое число равняется $$$f(x+j-1)$$$.

Пример
Входные данные
3
5 5
1 2 3 2 1
7 7
4 5 1 2 1 4 5
11 11
1 2 3 1 1 9 3 2 4 1 3
Выходные данные
3
4
4
Примечание

В первом наборе входных данных требуется вычислить $$$f(5)$$$. Можно показать, что после $$$4$$$ операций $$$S$$$ может содержать $$$2$$$, $$$3$$$ или $$$4$$$. Ниже показаны операции, необходимые для того, чтобы получить $$$S = \{4\}$$$.

  • Изначально $$$S = \{1, 2, 3, 4, 5\}$$$ и $$$a = [1, 2, 3, 2, 1]$$$.
  • Выбираем $$$l = 1$$$. Тогда $$$r = 2$$$. Так как $$$a_1 < a_2$$$, зададим $$$a_2 = 1 + 2$$$ и удалим $$$1$$$ из $$$S$$$. Теперь $$$S = \{2, 3, 4, 5\}$$$ и $$$a = [1, 3, 3, 2, 1]$$$.
  • Выбираем $$$l = 4$$$. Тогда $$$r = 5$$$. Поскольку $$$a_4 > a_5$$$, зададим $$$a_4 = 2 + 1$$$ и удалим $$$5$$$ из $$$S$$$. Теперь $$$S = \{2, 3, 4\}$$$ и $$$a = [1, 3, 3, 3, 1]$$$.
  • Выбираем $$$l = 3$$$. Тогда $$$r = 4$$$. Поскольку $$$a_3 = a_4$$$, у нас есть выбор, удалить $$$3$$$ или $$$4$$$. Поскольку мы хотим сохранить $$$4$$$, удалим $$$3$$$. Итак, зададим $$$a_4 = 3 + 3$$$ и удалим $$$3$$$ из $$$S$$$. Теперь $$$S = \{2, 4\}$$$ и $$$a = [1, 3, 3, 6, 1]$$$.
  • Выбираем $$$l = 2$$$. Тогда $$$r = 4$$$. Поскольку $$$a_2 < a_4$$$, зададим $$$a_4 = 3 + 6$$$ и удалим $$$2$$$ из $$$S$$$. Наконец, $$$S = \{4\}$$$ и $$$a = [1, 3, 3, 9, 1]$$$.

Во втором наборе входных данных требуется вычислить $$$f(7)$$$. Можно показать, что после $$$6$$$ операций $$$S$$$ может содержать $$$2$$$, $$$4$$$, $$$6$$$ или $$$7$$$.