题解

问题描述

给定一个长度为 $n$ 的排列 $p = [p_1, p_2, \dots, p_n]$。称下标 $i$（$1 \le i < n$）为“好位置”，如果存在 $j$ 满足 $i < j \le n$ 且 $p_i > p_j$。记原排列中“好位置”的个数为 $G(p)$。

要求构造另一个排列 $q$，满足：

1. $q \neq p$；
2. $G(q) = G(p)$。

题目内容

小苯定义一个数组的“好位置”为：满足其右侧存在比其小的元素形式化的即:

在数组$a$中对于$1≤i<n$存在$1≤i<j≤n$使得$a_i>a_j$，则称$i$为“好位置”。

现在小苯有一个长度为$n$ 的排列$p$，他希望你构造一个长为n的排列$q$，满足$p≠q$同时$p,q$的“好位置”个数相同。

输入描述

本题包含多组测试数据。

第一行一个正整数$T(1≤T≤10000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行

第一行一个正整数$n(1≤n≤200000)$，表示排列$p$的长度。

第二行$n$个正整数$p_i(1≤p_i≤n)$，表示排列$p$。(保证输入是一个排列)

(保证所有测试数据中，$n$的总和不超过$200000$)

输出描述

输出包含$T$行，对于每组测试数据输出一行。

如果可以找到一个满足条件的$q$，则先输出一行一个字符串“$YES$”(不含双引号)，表示可以找到，再在下一行输出一行$n$个数字表示满足条件的排列q(有多解输出任意即可。)

如果找不到一个满足条件的$q$，则输出一个“$NO$”(不含双引号)。

样例1

输入

2 
4
2 1 3 4
3 
1 2 3

输出

YES
1 2 4 3
NO

说明

对于第一个测试数据:

$[2, 1, 3,4]$的"好位置”个数为$1$。(好位置有:$i=1$)

$[1,2,4,3]$的“好位置”个数也为$1$。(好位置有:$i=3$)