这是问题的简单版本。唯一的区别是这个版本中的 $$$x=n$$$ 。您必须解决这两个版本才能进行破解。
给定两个整数 $$$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$$$,您可以选择整数 $$$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 = n$$$) - 球的数量和需要找到 $$$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 5 1 2 3 2 1 7 7 4 5 1 2 1 4 5 11 11 1 2 3 1 1 9 3 2 4 1 3
输出 #1
3 4 4
注意
在第一个测试用例中,您需要计算$$$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$$$。