CF1998E1 Eliminating Balls With Merging (Easy Version)

_喝水_ —— 孙武，程序员健康指南 **这是问题的简单版本。本题中 $x=n$ 。你必须同时解决这两个版本的问题，才能 hack**。 给你两个整数 $n$ 和 $x$ ( $x=n$ )。有 $n$ 个球排成一排，从左到右编号为 $1$ 到 $n$ 。最初，在第 $i$ 个球上写着一个值 $a_i$。 对于从 $1$ 到 $n$ 的每个整数 $i$ ，我们定义一个函数 $f(i)$ 如下： - 假设有一个集合 $S = \{1, 2, \ldots, i\}$ 。 - 在每次运算中，必须从 $S$ 中选择一个整数 $l$ ( $1 \leq l < i$ )，使得 $l$ 不是 $S$ 的最大元素。假设 $r$ 是 $S$ 中大于 $l$ 的最小元素。 - 如果是 $a_l > a_r$ ，则令 $a_l = a_l + a_r$ 并从 $S$ 中删除 $r$ 。 - 如果是 $a_l < a_r$ ，则令 $a_r = a_l + a_r$ ，并从 $S$ 删除 $l$ 。 - 如果是 $a_l = a_r$ ，则从 $S$ 中选择删除整数 $l$ 或 $r$ ： - 如果选择从 $S$ 中删除 $l$ ，则设置 $a_r = a_l + a_r$ 并从 $S$ 中删除 $l$ 。 - 如果您选择从 $S$ 中删除 $r$ ，则需要设置 $a_l = a_l + a_r$ ，并从 $S$ 中删除 $r$ 。 - $f(i)$ 表示这样的整数 $j$ ( $1 \le j \le i$ )的个数，即执行上述操作恰好 $i - 1$ 次后可以得到 $S = \{j\}$ 。 对 $x$ 到 $n$ 的每个整数 $i$ 都需要求出 $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)$ 。 **样例解释** 在第一个测试用例中，要计算 $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$ ，并从 $S$ 中删除 $1$ 。现在， $S = \{2, 3, 4, 5\}$ 和 $a = [1, 3, 3, 2, 1]$ 。 - 选择 $l = 4$ 。自然是 $r = 5$ 。由于 $a_4> a_5$ ，我们设置 $a_4 = 2 + 1$ ，并从 $S$ 中删除 $5$ 。现在， $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$ 并从 $S$ 中删除 $3$ 。现在， $S = \{2, 4\}$ 和 $a = [1, 3, 3, 6, 1]$ 。 - 选择 $l = 2$ 。自然是 $r = 4$ 。由于 $a_2< a_4$ ，我们设置 $a_4 = 3 + 6$ ，并从 $S$ 中删除 $2$ 。最后是 $S = \{4\}$ 和 $a = [1, 3, 3, 9, 1]$ 。 在第二个测试案例中，要求计算 $f(7)$ 。可以证明，经过 $6$ 次运算后， $S$ 可以包含 $2$ 、 $4$ 、 $6$ 或 $7$ 。

In the first test case, you are required to calculate $ f(5) $ . It can be shown that after $ 4 $ operations, $ S $ can contain $ 2 $ , $ 3 $ , or $ 4 $ . The following shows the operations required to make $ S = \{4\} $ . - Initially, $ S = \{1, 2, 3, 4, 5\} $ and $ a = [1, 2, 3, 2, 1] $ . - Choose $ l = 1 $ . Naturally, $ r = 2 $ . Since $ a_1 < a_2 $ , we set $ a_2 = 1 + 2 $ and remove $ 1 $ from $ S $ . Now, $ S = \{2, 3, 4, 5\} $ and $ a = [1, 3, 3, 2, 1] $ . - Choose $ l = 4 $ . Naturally, $ r = 5 $ . Since $ a_4 > a_5 $ , we set $ a_4 = 2 + 1 $ and remove $ 5 $ from $ S $ . Now, $ S = \{2, 3, 4\} $ and $ a = [1, 3, 3, 3, 1] $ . - Choose $ l = 3 $ . Naturally, $ r = 4 $ . Since $ a_3 = a_4 $ , we have a choice whether to remove $ 3 $ or $ 4 $ . Since we want to preserve $ 4 $ , let's remove $ 3 $ . So, set $ a_4 = 3 + 3 $ and remove $ 3 $ from $ S $ . Now, $ S = \{2, 4\} $ and $ a = [1, 3, 3, 6, 1] $ . - Choose $ l = 2 $ . Naturally, $ r = 4 $ . Since $ a_2 < a_4 $ , we set $ a_4 = 3 + 6 $ and remove $ 2 $ from $ S $ . Finally, $ S = \{4\} $ and $ a = [1, 3, 3, 9, 1] $ . In the second test case, you are required to calculate $ f(7) $ . It can be shown that after $ 6 $ operations, $ S $ can contain $ 2 $ , $ 4 $ , $ 6 $ , or $ 7 $ .