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.

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$ .

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.

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]$ .