This is the hard version of the problem. The only difference is that $x=1$ in this version. You must solve both versions to be able to hack.

You are given two integers $n$ and $x$ ($x=1$). There are $n$ balls lined up in a row, numbered from $1$ to $n$ from left to right. Initially, there is a value $a_i$ written on the $i$-th ball.

For each integer $i$ from $1$ to $n$, we define a function $f(i)$ as follows:

• Suppose you have a set $S = \{1, 2, \ldots, i\}$.

• In each operation, you have to select an integer $l$ ($1 \leq l < i$) from $S$ such that $l$ is not the largest element of $S$. Suppose $r$ is the smallest element in $S$ which is greater than $l$.
  • If $a_l > a_r$, you set $a_l = a_l + a_r$ and remove $r$ from $S$.
  • If $a_l < a_r$, you set $a_r = a_l + a_r$ and remove $l$ from $S$.
  • If $a_l = a_r$, you choose either the integer $l$ or $r$ to remove from $S$:
    • If you choose to remove $l$ from $S$, you set $a_r = a_l + a_r$ and remove $l$ from $S$.
    • If you choose to remove $r$ from $S$, you set $a_l = a_l + a_r$ and remove $r$ from $S$.

• $f(i)$ denotes the number of integers $j$ ($1 \le j \le i$) such that it is possible to obtain $S = \{j\}$ after performing the above operations exactly $i - 1$ times.

For each integer $i$ from $x$ to $n$, you need to find $f(i)$.

The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 2 \cdot 10^5; x = 1$) — the number of balls and the smallest index $i$ for which you need to find $f(i)$.

The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the initial number written on each ball.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output $n-x+1$ space separated integers on a new line, where the $j$-th integer should represent $f(x+j-1)$.