入れ替える場所をa,b(a<b)と置きます。
やって意味のある入れ替えはとりあえず N[a] < N[b] になってないとダメです。(以下こうなってることを仮定)
また
- (a,b) (a,b') の2つの入れ替えがあった時 N[b] と N[b'] を比較して大きいほうがお得です。
- (a,b) (a,b') (ただしN[b]==N[b'])の場合は bとb'を比較して大きいほうが方がお得です。
- (a,b),(a',b') (ただしa<a')の場合これはN[a],N[b],N[a'],N[b']の値に限らず(a,b)の方がお得になります。
よってaを先頭から全部試してa<bでN[b]が一番大きくなってかつもっとも右にあるbを計算してN[a] < N[b]になっていればswapして終わりです。
これを単純にやるとO(n^2)
 
ただし毎回bを計算する必要はなくて例えば
maxIndex[a] := N[a+1],N[a+2],N[a+3]...値が一番大きく かつ もっとも右側にあるインデックス
みたいなものを定義して、aが大きい方からこの配列を埋めていけば
全体でもO(n)で解けます。

5YWl44KM5pu/44GI44KL5aC05omA44KSYSxiKGE8Yinjgajnva7jgY3jgb7jgZnjgIIK44KE44Gj44Gm5oSP5ZGz44Gu44GC44KL5YWl44KM5pu/44GI44Gv44Go44KK44GC44GI44GaIE5bYV0gPCBOW2JdIOOBq+OBquOBo+OBpuOBquOBhOOBqOODgOODoeOBp+OBmeOAgijku6XkuIvjgZPjgYbjgarjgaPjgabjgovjgZPjgajjgpLku67lrpopCuOBvuOBnwotIChhLGIpIChhLGInKSDjga4y44Gk44Gu5YWl44KM5pu/44GI44GM44GC44Gj44Gf5pmCIE5bYl0g44GoIE5bYiddIOOCkuavlOi8g+OBl+OBpuWkp+OBjeOBhOOBu+OBhuOBjOOBiuW+l+OBp+OBmeOAggotIChhLGIpIChhLGInKSAo44Gf44Gg44GXTltiXT09TltiJ10p44Gu5aC05ZCI44GvIGLjgahiJ+OCkuavlOi8g+OBl+OBpuWkp+OBjeOBhOOBu+OBhuOBjOaWueOBjOOBiuW+l+OBp+OBmeOAggotIChhLGIpLChhJyxiJykgKOOBn+OBoOOBl2E8YScp44Gu5aC05ZCI44GT44KM44GvTlthXSxOW2JdLE5bYSddLE5bYidd44Gu5YCk44Gr6ZmQ44KJ44GaKGEsYinjga7mlrnjgYzjgYrlvpfjgavjgarjgorjgb7jgZnjgIIK44KI44Gj44GmYeOCkuWFiOmgreOBi+OCieWFqOmDqOippuOBl+OBpmE8YuOBp05bYl3jgYzkuIDnlarlpKfjgY3jgY/jgarjgaPjgabjgYvjgaTjgoLjgaPjgajjgoLlj7PjgavjgYLjgoti44KS6KiI566X44GX44GmTlthXSA8IE5bYl3jgavjgarjgaPjgabjgYTjgozjgbBzd2Fw44GX44Gm57WC44KP44KK44Gn44GZ44CCCuOBk+OCjOOCkuWNmOe0lOOBq+OChOOCi+OBqE8obl4yKQoK44Gf44Gg44GX5q+O5ZueYuOCkuioiOeul+OBmeOCi+W/heimgeOBr+OBquOBj+OBpuS+i+OBiOOBsAptYXhJbmRleFthXSA6PSBOW2ErMV0sTlthKzJdLE5bYSszXS4uLuWApOOBjOS4gOeVquWkp+OBjeOBjyDjgYvjgaQg44KC44Gj44Go44KC5Y+z5YG044Gr44GC44KL44Kk44Oz44OH44OD44Kv44K5CuOBv+OBn+OBhOOBquOCguOBruOCkuWumue+qeOBl+OBpuOAgWHjgYzlpKfjgY3jgYTmlrnjgYvjgonjgZPjga7phY3liJfjgpLln4vjgoHjgabjgYTjgZHjgbAK5YWo5L2T44Gn44KCTyhuKeOBp+ino+OBkeOBvuOBmeOAgg==