CF1998E2 Eliminating Balls With Merging (Hard Version)

喝水。 —— 孙武，《成为一名健康程序员的艺术》 这是这个问题的更难的版本。唯一的区别是在这个版本中 $x = 1$。你必须破解这两个版本才能破解。 你被给定了两个整数 $n$ 和 $x$ ( $x = 1$ )，有 $n$ 个球排成一排，从左到右从 $1$ 到 $n$ 编号。最初，在第 $i$ 个球上写了一个值 $a_i$。 对于从 $1$ 到 $n$ 的每一个整数 $i$，我们定义函数 $f(i)$ 如下： + 假设你有一个集合 $S = \{1, 2, \ldots, i\}$。 + 对于每一次操作，你需要从 $S$ 中选择出一个整数 $l$ $(1 \le l < i)$，使得 $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)$ 的个数，使得在执行上述运算 $i − 1$ 次后可以得到 $S = \{ j \}$。 对于每一个整数 $i$ 从 $x$ 到 $n$，你需要找到 $f(i)$。

第一行包含一个整数 $t$ $(1 ≤ t ≤ 10^4)$，也就是测试组数。 每一组测试数据的第一行包含两个整数 $n$ 和 $x$ $(1 ≤ n ≤ 2 \cdot 10^5;x = 1)$，也就是球的数量和最小的索引 $i$ 你需要找到 $f(i)$。 每一组测试数据的第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ $(1 ≤ a_i ≤ 10^9)$，也就是每个球上写的数字。 保证所有测试数据中的 $n$ 之和小于等于 $2 \cdot 10^5$。

对于每一组测试数据，在新的一行中输出 $n - x + 1$ 个用一个空格隔开的整数，其中第 $j$ 个数应当表示 $f(x + j - 1)$。

对于第一组数据，下面是对于每个 $1$ 到 $n$ 的 $i$，$j$ 可以取到的所有数值： + 对于 $f(1)$，$j$ 只能取 $1$。 + 对于 $f(2)$，$j$ 只能取 $2$。 + 对于 $f(3)$，$j$ 能取 $2$ 和 $3$。 + 对于 $f(4)$，$j$ 能取 $2$ 和 $3$。 + 对于 $f(5)$，$j$ 能取 $2$，$3$ 和 $4$。