← 返回题目列表

Codeforces · 1364/B

B. 社交距离最远的子序列

中文机器翻译题面 查看原题

给定长度为$$$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]$$$。