CF1768D Lucky Permutation

给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。 你可以对排列 $p$ 进行下列操作任意次： - 选择整数 $i,j(1\leq i

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。 接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p$ 是一个 $1\sim n$ 的排列。

对于每组数据： 输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

In the first test case, the permutation already satisfies the condition. In the second test case, you can perform the operation with $ (i,j)=(1,2) $ , after that the permutation will be $ [2,1] $ which has exactly one inversion. In the third test case, it is not possible to satisfy the condition with less than $ 3 $ operations. However, if we perform $ 3 $ operations with $ (i,j) $ being $ (1,3) $ , $ (2,4) $ , and $ (3,4) $ in that order, the final permutation will be $ [1, 2, 4, 3] $ which has exactly one inversion. In the fourth test case, you can perform the operation with $ (i,j)=(2,4) $ , after that the permutation will be $ [2,1,3,4] $ which has exactly one inversion.