给定长度为$$$n$$$的排列$$$p$$$,找到其长度至少为$$$2$$$的子序列$$$s_1$$$、$$$s_2$$$、$$$\ldots$$$、$$$s_k$$$,使得:
- $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ 在 $$$p$$$ 的所有子序列上尽可能大,长度至少为 $$$2$$$。
- 在所有此类子序列中,选择长度 $$$k$$$ 尽可能小的子序列。
如果多个子序列满足这些条件,则允许您找到其中任何一个。
如果 $$$a$$$ 可以通过删除一些(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是数组 $$$b$$$ 的子序列。
长度 $$$n$$$ 的排列是一个长度为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 排列 $$$p$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1$$$、$$$p_2$$$、$$$\ldots$$$、$$$p_{n}$$$($$$1 \le p_i \le n$$$、$$$p_i$$$ 是不同的)— 排列 $$$p$$$ 的元素。
测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,第一行应包含找到的子序列的长度 $$$k$$$。第二行应包含 $$$s_1$$$、$$$s_2$$$、$$$\ldots$$$、$$$s_k$$$ — 其元素。
如果多个子序列满足这些条件,则允许您找到其中任何一个。
示例
输入 #1
2 3 3 2 1 4 1 3 4 2
输出 #1
2 3 1 3 1 4 2
注意
在第一个测试用例中,有 $$$4$$$ 长度至少为 $$$2$$$ 的子序列:
- $$$[3,2]$$$ 给我们$$$|3-2|=1$$$。
- $$$[3,1]$$$ 给我们$$$|3-1|=2$$$。
- $$$[2,1]$$$ 给我们$$$|2-1|=1$$$。
- $$$[3,2,1]$$$ 给我们$$$|3-2|+|2-1|=2$$$。
所以答案是 $$$[3,1]$$$ 或 $$$[3,2,1]$$$。由于我们希望子序列尽可能短,所以答案是$$$[3,1]$$$。