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.


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

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    # n, x = map(int, input().split())
    n = int(input())
    arr = list(map(int, input().split()))
    ans = [arr[0]]
    for i in range(1, n - 1):
        if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
            ans.append(arr[i])
        elif arr[i - 1] > arr[i] and arr[i] < arr[i + 1]:
            ans.append(arr[i])
    ans.append(arr[-1])
    print(len(ans))
    print(*ans)


t = int(input())

for loop in range(t):

    n = int(input())
    p = list(map(int,input().split()))
    a = p

    ans = []
    

    for i in range(n):

        if i == 0 or i == n-1:
            ans.append(p[i])

        elif a[i-1] <= a[i] <= a[i+1]:
            continue
        elif a[i-1] >= a[i] >= a[i+1]:
            continue
        else:
            ans.append(p[i])

    print(len(ans))
    print(*ans)


for t in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = [a[0]] + [a[i] for i in range(1, n - 1) if not(a[i - 1] < a[i] < a[i + 1] or 
                                                   a[i - 1] > a[i] > a[i + 1])] + [a[-1]]
    print(len(b))
    print(*b)

for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    ans = [str(p[0])]
    for i in range(1,n-1):
        if p[i-1] < p[i] < p[i+1]:
            continue
        if p[i-1] > p[i] > p[i+1]:
            continue
        ans.append(str(p[i]))
    ans.append(str(p[-1]))
    print(len(ans))
    print(" ".join(ans))


for _ in range(int(input())):
    n = int(input())
    p = tuple(map(int, input().split()))
    ans = [p[i] for i in range(n) if i in (0, n - 1) or p[i] != sorted(p[i - 1:i + 2])[1]]
    print(len(ans))
    print(*ans)


t = int(input())
for test in range(t):
    n = int(input())
    l = list(map(int, input().rstrip().split()))
    i = 0
    arr = list()
    arr.append(str(l[0]))
    while i+1 < n:
        if i+1 == n-1 or (l[i] < l[i+1] and l[i+1] > l[i+2]) or (l[i] > l[i+1] and l[i+1] < l[i+2]):
            arr.append(str(l[i+1]))
        i += 1
    print(len(arr))
    print(" ".join(arr))

from collections import *
from sys import stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

t, = rl()
for _ in range(t):
    n, = rl()
    p = rl()
    s = [p[0]]
    for i in range(1, n-1):
        if p[i-1] < p[i] > p[i+1] or p[i-1] > p[i] < p[i+1]:
            s.append(p[i])
    s.append(p[-1])
    print(len(s))
    print(*s)


import sys
input = sys.stdin.readline

for nt in range(int(input())):
	n = int(input())
	a = list(map(int,input().split()))
	if n==2:
		print (2)
		print (*a)
		continue
	ans = [a[0]]
	if a[1]>a[0]:
		turn = 1
	else:
		turn = 0
	s = abs(a[1]-a[0])
	for i in range(2,n):
		if turn:
			if a[i]>a[i-1]:
				continue
			ans.append(a[i-1])
			turn = 0
		else:
			if a[i]<a[i-1]:
				continue
			ans.append(a[i-1])
			turn = 1
	ans.append(a[-1])
	print (len(ans))
	print (*ans)

from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))



q=nn()

for _ in range(q):
	n = nn()

	per = lm()

	best =[per[0]]

	for i in range(len(per)-2):
		minper = min(per[i], per[i+1], per[i+2])
		maxper = max(per[i], per[i+1], per[i+2])
		if minper==per[i+1] or maxper==per[i+1]:
			best.append(per[i+1])
	best.append(per[-1])
	print(len(best))
	print(*best)


import sys

def ii():
    return sys.stdin.readline().strip()

def idata():
    return [int(x) for x in ii().split()]

def solve_of_problem():
    n = int(ii())
    data = idata()
    ans = [data[0]]
    for i in range(1, n - 1):
        if data[i - 1] < data[i] > data[i + 1] or data[i - 1] > data[i] < data[i + 1]:
            ans += [data[i]]
    print(len(ans) + 1)
    print(*ans, data[-1])
    return

for ______ in range(int(ii())):
    solve_of_problem()

def main():
    n = int(input())
    lst = list(map(int, input().split()))
    take = [lst[0]]
    sign = 0
    for i in range(1, n):
        if i == n - 1:
            take.append(lst[i])
        else:
            if lst[i] > take[-1]:
                if lst[i + 1] < lst[i]:
                    take.append(lst[i])
            elif lst[i] < take[-1]:
                if lst[i + 1] > lst[i]:
                    take.append(lst[i])
    line = str(len(take)) + '\n'
    for i in take:
        line += str(i) + ' '
    print(line)

def __starting_point():
    t = int(input())
    for i in range(t):
        main()

__starting_point()

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    ans = [p[0]]
    for i in range(n-2):
        if (p[i]-p[i+1])*(p[i+1]-p[i+2])<0:
            ans.append(p[i+1])
    ans.append(p[-1])
    print(len(ans))
    print(*ans)

T = int(input())

for t in range(T):
    N = int(input())

    P = [int(_) for _ in input().split()]
    up = P[1] > P[0]
    res = [P[0]]

    for i in range(1, N-1):
        if up and P[i+1] < P[i]:
            res.append(P[i])
            up = False
        elif not up and P[i+1] > P[i]:
            res.append(P[i])
            up = True

    if P[N-1] != P[N-2]:
        res.append(P[N-1])

    print(len(res))
    print(' '.join(map(str, res)))


def f(n,l):
    output = [l[0]]
    for i in range(1,n-1):
        if (l[i]-l[i-1])*(l[i+1]-l[i]) < 0:
            output.append(l[i])
    output.append(l[-1])
    return str(len(output))+'\n'+' '.join([str(x) for x in output])

numberofcases = int(input())
for _ in range(numberofcases):
    n = int(input())
    l = [int(t) for t in input().split()]
    print(f(n,l))

def help():
	n = int(input())
	arr = list(map(int,input().split(" ")))

	peak = [False]*n
	down = [False]*n
	for i in range(n):
		if(i==0):
			if(arr[0]<arr[1]):
				down[0]=True
			if(arr[0]>arr[1]):
				peak[i]=True
		elif(i==n-1):
			if(arr[n-1]<arr[n-2]):
				down[i]=True
			if(arr[n-1]>arr[n-2]):
				peak[i]=True
		else:
			if(arr[i-1]<arr[i] and arr[i]>arr[i+1]):
				peak[i]=True
			elif(arr[i-1]>arr[i] and arr[i]<arr[i+1]):
				down[i]=True
	series = []
	for i in range(n):
		if(peak[i]==True or down[i]==True):
			series.append(i)
	ans = 0
	for i in range(len(series)-1):
		ans += abs(series[i]-series[i+1])
	print(len(series))
	for i in range(len(series)):
		print(arr[series[i]],end=" ")
	print()

for _ in range(int(input())):
	help()


import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    n = int(sys.stdin.readline().strip())
    p = list(map(int, sys.stdin.readline().strip().split()))
    ans = [p[0]]
    for i in range(1, n):
        if p[i] != ans[-1]:
            if len(ans) == 1:
                ans.append(p[i])
            else:
                if (ans[-2] - ans[-1]) * (ans[-1] - p[i]) > 0:
                    ans.pop()
                ans.append(p[i])
    print(len(ans))
    print(" ".join(list(map(str, ans))))