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

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

Вам даны два целых числа $$$n$$$ и $$$x$$$ ($$$x=1$$$). В ряд выстроены $$$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 = 1$$$) — количество шаров и наименьший индекс $$$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 1
1 2 3 2 1
7 1
4 5 1 2 1 4 5
11 1
1 2 3 1 1 9 3 2 4 1 3
Выходные данные
1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4
Примечание

Для первого набора входных данных ниже приведены возможные значения $$$j$$$ для каждого $$$f(i)$$$ от $$$1$$$ до $$$n$$$.

  • Для $$$f(1)$$$ единственным возможным значением $$$j$$$ является $$$1$$$.
  • Для $$$f(2)$$$ единственным возможным значением $$$j$$$ является $$$2$$$.
  • Для $$$f(3)$$$ возможные значения $$$j$$$: $$$2$$$ и $$$3$$$.
  • Для $$$f(4)$$$ возможные значения $$$j$$$: $$$2$$$ и $$$3$$$.
  • Для $$$f(5)$$$ возможные значения $$$j$$$: $$$2$$$, $$$3$$$ и $$$4$$$.