题目描述

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$。你需要选择两个整数 $l, r$（$1 \le l \le r \le n$），并将排列的子区间 $[l, r]$ 反转。反转后的排列为 $p_1, p_2, \dots, p_{l-1}, p_r, p_{r-1}, \dots, p_l, p_{r+1}, p_{r+2}, \dots, p_n$。

请你找出通过恰好一次反转操作能够得到的字典序最小的排列。

注意，对于两个长度相同且不同的排列 $a$ 和 $b$，如果在第一个不同的位置，$a$ 的元素小于 $b$ 的元素，则 $a$ 的字典序小于 $b$。

排列是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试数据的组数。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 500$），表示排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），表示排列的元素。

输出格式

对于每组测试数据，输出通过恰好一次反转操作能够得到的字典序最小的排列。

说明/提示

在第一个测试用例中，排列长度为 $1$，因此唯一可能的区间是 $[1,1]$。反转后的排列为 $[1]$。

在第二个测试用例中，通过反转区间 $[1,2]$ 可以得到升序排列。反转后的排列为 $[1,2,3]$。

在第三个测试用例中，最优的区间是 $[2,3]$。反转后的排列为 $[1,2,4,3]$。

在第四个测试用例中，没有更小的字典序排列，因此可以选择区间 $[1,1]$，保持不变。反转后的排列为 $[1,2,3,4,5]$。

由 ChatGPT 4.1 翻译

样例

4
1
1
3
2 1 3
4
1 4 2 3
5
1 2 3 4 5

1 
1 2 3 
1 2 4 3 
1 2 3 4 5