多倍長整数を使わなくても解けます． $i \leftarrow P_i$ の有向辺を貼ったグラフを考えると以下のようなステップで解けます． $A$ を辞書順最小化する操作回数を $X$ とします．答えの列を $A'$ とします．

• $1$ を含むサイクルを考える．サイクルが含む頂点の列を $V = (V_1, V_2, \dots, V_n)$ として $A_{V_i}$ を昇順に並べた列を考える．この列を前から見ていって， $A_1$ をその値にできるかを判定する．サイクルの長さを $L_1$ として $X \ \mathrm{mod}\ L_1$ をある値にできるかと言い換えられる．可能なら， $A'_{V_i}$ と $X \ \mathrm{mod}\ L_1$ は確定する．
• $2$ を含むサイクルを考える．既に見ていたら飛ばす．上と同様の処理をする．ただし， $\mathrm{mod}\ L_1$ での操作回数と矛盾しないようにしたい．
• 以降 $3, 4, \dots, N$ についても同様に処理．

つまり操作回数について既にいくつかの数で割った余りが確定しており，それに矛盾しないように操作回数を定めたいという方針になります．

今見ているサイクルの長さを $L$ として $X \ \mathrm{mod}\ L$ をある値にできるかを判定したいです．これを $x$ とします．また $L = p_1^{c_1} p_2^{c_2} \dots p_m^{c_m}$ と素因数分解します．

このとき $x_i$ を $x$ を $p_i^{c_i}$ で割った余りとすると $X \equiv x \ \mathrm{mod}\ L$ というのは $X \equiv x_i \ \mathrm{mod}\ p_i^{c_i}$ が任意の $i$ について成り立つことと同値です．(中国剰余定理)
よって，これまでの結果で確定した $X \ \mathrm{mod}\ p_i^{c_i}$ の値と矛盾しないことを判定すれば良いです．
また， $x$ が決まることで $0 \leq j \leq c_i$ について $X\ \mathrm{mod}\ p_i^{j}$ が確定します．これを保存し，次のサイクルを見るときは保存した条件と矛盾しないようにすれば良いです．
計算量はエラトステネスのふるいなどで素因数分解ができ，あるサイクルを見るときに $X \ \mathrm{mod}\ L$ をある値にしてこれまでの結果と矛盾しないかや条件を保存するのは $O( c_1 + c_2 + \dots + c_m )$ で可能です． $O( c_1 + c_2 + \dots + c_m ) \leq O( \log N )$ なので，素因数分解以外は全体で $O( N \log N)$ で解けます．

実装例