No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Most socially-distanced subsequence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven 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.

Input

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

Output

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.

Example

Input

2 3 3 2 1 4 1 3 4 2

Output

2 3 1 3 1 4 2

Note

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/27/2021 18:14:21 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|