题目内容

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

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

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

题解

问题描述

给定一个长度为 $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)$。