码学堂 | Eliminating Balls With Merging (Easy Version)

描述

这是本题的简单版本。该版本唯一区别是 $x = n$ 。你必须解决两个版本，才可以进行 hack。

给定两个整数 $n$ 和 $x$ （ $x = n$ ）。有 $n$ 个球排成一行，从左到右编号 $1$ 到 $n$ 。初始时，第 $i$ 个球上写有数值 $a_i$ 。

对于每一个整数 $i$ 从 $1$ 到 $n$ ，我们定义函数 $f(i)$ 如下：

$f(i)$ 代表整数 $j$ （ $1\le j \le i$ ）的数量：经过恰好 $i-1$ 次上述操作后，可以让集合 $S = {j}$ 。

对于每一个整数 $i$ 从 $x$ 到 $n$ ，求 $f(i)$ 。

输入

第一行包含整数 $t$ （ $1 \le t \le 10^4$ ），代表测试用例数量。

每个测试用例第一行包含两个整数 $n,x$ （ $1 \le n \le 2\cdot10^5; x = n$ ）：球的数量，以及需要计算 $f(i)$ 的最小下标 $i$ 。

每个测试用例第二行包含 $a_1,a_2,\dots,a_n$ （ $1 \le a_i \le 10^9$ ），每个球上初始写的数字。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ 。

输出

对每个测试用例，在新的一行输出 $n-x+1$ 个空格分隔的整数，其中第 $j$ 个整数代表 $f(x+j-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

样例输出

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$ ，把 $1$ 从 $S$ 删除。现在 $S={2,3,4,5}$ ， $a=[1,3,3,2,1]$ 。
选择 $l=4$ ，自然 $r=5$ 。因为 $a_4>a_5$ ，令 $a_4=2+1$ ，把 $5$ 从 $S$ 删除。现在 $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$ ，把 $3$ 从 $S$ 删除。现在 $S={2,4}$ ， $a=[1,3,3,6,1]$ 。
选择 $l=2$ ，自然 $r=4$ 。因为 $a_2 < a_4$ ，令 $a_4=3+6$ ，把 $2$ 从 $S$ 删除。最终 $S={4}$ ， $a=[1,3,3,9,1]$ 。

第二个测试用例需要计算 $f(7)$ 。可以证明，经过 $6$ 次操作后，集合 $S$ 可以包含 $2,4,6,7$ 。