CF1364B.Most socially-distanced subsequence

Given a permutation $p$ of length $n$, find its subsequence $s_1$, $s_2$, $\ldots$, $s_k$ of length at least $2$ such that:

• $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ is as big as possible over all subsequences of $p$ with length at least $2$.
• Among all such subsequences, choose the one whose length, $k$, is as small as possible.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deleting some (possibly, zero or all) elements.

A permutation of length $n$ is an array of length $n$ in which every element from $1$ to $n$ occurs exactly once.

给定一个长度为 $n$ 的排列 $p$，请找出其一个长度至少为 $2$ 的子序列 $s_1$, $s_2$, $\ldots$, $s_k$，使得：

• 在所有长度至少为 $2$ 的 $p$ 的子序列中，和式 $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ 尽可能大；
• 在所有满足上述最大和的子序列中，选择长度 $k$ 尽可能小的那个。

若存在多个满足条件的子序列，输出其中任意一个即可。

序列 $a$ 是数组 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中删除若干（可能为零个或全部）元素得到。

长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次。

The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^5$) — the length of the permutation $p$.

The second line of each test case contains $n$ integers $p_1$, $p_2$, $\ldots$, $p_{n}$ ($1 \le p_i \le n$, $p_i$ are distinct) — the elements of the permutation $p$.

The sum of $n$ across the test cases doesn't exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, the first line should contain the length of the found subsequence, $k$. The second line should contain $s_1$, $s_2$, $\ldots$, $s_k$ — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

对于每个测试用例，第一行应输出所找到子序列的长度 $k$；第二行应输出该子序列的元素 $s_1$, $s_2$, $\ldots$, $s_k$。

若存在多个满足条件的子序列，任选其一输出即可。

In the first test case, there are $4$ subsequences of length at least $2$:

• $[3,2]$ which gives us $|3-2|=1$.
• $[3,1]$ which gives us $|3-1|=2$.
• $[2,1]$ which gives us $|2-1|=1$.
• $[3,2,1]$ which gives us $|3-2|+|2-1|=2$.

So the answer is either $[3,1]$ or $[3,2,1]$. Since we want the subsequence to be as short as possible, the answer is $[3,1]$.

在第一个测试用例中，长度至少为 $2$ 的子序列共有 $4$ 个：

• $[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]$。