给你一个排列 $$$p_1, p_2, \dots, p_n$$$。然后,按以下方式构造无向图:在顶点 $$$i$$$ 和 $$$j$$$ 之间添加一条边,使得 $$$i < j$$$ 当且仅当 $$$p_i > p_j$$$ 时。您的任务是计算该图中连接组件的数量。
当且仅当沿着连接 $$$u$$$ 和 $$$v$$$ 的边至少有一条路径时,两个顶点 $$$u$$$ 和 $$$v$$$ 属于同一连通分量。
排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$k$$$ — 连接组件的数量。
示例
输入 #1
6 3 1 2 3 5 2 1 4 3 5 6 6 1 4 2 5 3 1 1 6 3 2 1 6 5 4 5 3 1 5 2 4
输出 #1
3 3 1 1 2 1
注意
每个单独的测试用例如下图所示。彩色方块代表排列的元素。对于一种排列,每种颜色代表一些连接的组件。不同颜色的数量就是答案。