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