Most socially-distanced subsequence

题意翻译

### 题目描述 给出一个长度为 $n$ 的排列 $P$，你需要找到它的一个子序列 $P_{s_1},P_{s_2},\dots,P_{s_k}$ 满足： - $|P_{s_1}-P_{s_2}|+|P_{s_2}-P_{s_3}|+\dots+|P_{s_{k-1}}-P_{s_k}|$ 最大。 - 在上式最大的前提下 $k$ 最小。 求这个子序列的最长长度。 ### 输入格式 **本题有多组数据** 第一行一个整数 $T$，表示数据组数。 每组数据第一行一个整数 $n$。 之后一行 $n$ 个整数，表示给出的排列 $P$。 保证 $1\le T\le2\times10^4$，$2\le n\le10^5$，$1\le P_i\le n$，$\sum n\le10^5$。 ### 输出格式 每组数据第一行输出你选择的 $k$，之后一行输出 $k$ 个整数，表示你选择的子序列。

题目描述

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.

输入输出样例

输入样例 #1

2
3
3 2 1
4
1 3 4 2

输出样例 #1

2
3 1 
3
1 4 2

说明

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