题目描述

东哥给你一个长度为 $n$ 的双端队列（初始顺序固定），你的任务是从队列的前端或后端依次取出数字，构造一个字典序最大的序列。

这太简单了，为了增加难度，东哥允许你在构造序列之前，最多交换两次不同位置的数字。

那现在该怎么办呢？

输入格式

第一行一个整数 $T\ (1 ≤ T ≤ 2*10^5)$，表示测试用例的数量。
对于每组测试用例：

• 第一行一个整数 $n\ (1 ≤ n ≤ 2*10^5)$，表示双端队列的长度。
• 第二行 $n$ 个互不相同的整数 $a₁, a₂, ..., aₙ\ (1 ≤ aᵢ ≤ n)$，表示双端队列中的数字。

题目保证 $\sum n ≤ 2*10^5$。

输出格式

2
5
5 3 2 4 1
8
1 3 5 7 8 6 4 2

5 4 3 2 1
8 7 6 2 4 5 3 1