#P1998E2. Eliminating Balls With Merging (Hard Version)
Eliminating Balls With Merging (Hard Version)
Description
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)$.
Input
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$.
Output
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)$.
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
Note
In the first test case, below are the possible values of $j$ for each $f(i)$ from $1$ to $n$.
- For $f(1)$, the only possible value of $j$ is $1$.
- For $f(2)$, the only possible value of $j$ is $2$.
- For $f(3)$, the possible values of $j$ are $2$ and $3$.
- For $f(4)$, the possible values of $j$ are $2$ and $3$.
- For $f(5)$, the possible values of $j$ are $2$, $3$, and $4$.