这是问题的困难版本。唯一的区别是这个版本中的$$$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 \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$$$,您可以选择整数 $$$l$$$ 或 $$$r$$$ 从 $$$S$$$ 中删除: 如果您选择从 $$$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 = 1$$$) — 球的数量以及需要找到 $$$f(i)$$$ 的最小索引 $$$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)$$$。
示例
输入 #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 1 2 2 3 1 1 1 1 1 3 4 1 1 2 2 2 1 1 1 3 3 4
注意
在第一个测试用例中,以下是从 $$$1$$$ 到 $$$n$$$ 的每个 $$$f(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$$$。