入れ替える場所を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)で解けます。