#joi2013ho5. [joi2013ho5]バブルソート (Bubble Sort)

[joi2013ho5]バブルソート (Bubble Sort)

バブルソートとは,列をソートするアルゴリズムの 11 つである.長さ NN の数列 AA を昇順にソートしたいとしよう.バブルソートは,隣り合う 22 つの数で大小関係が崩れているものがあれば,それらの位置を交換する.これを,数列を前から順に走査しながら行う.すなわち,Ai>Ai+1A_i > A_{i + 1} となっている場所があれば,その 22 数を交換するということを,i=1,2,ldots,N1i = 1, 2, \\ldots, N - 1 に対してこの順で行うのが 11 回の走査である.この走査を N1N − 1 回繰り返すことで,数列を昇順にソートできることが知られている.

数列 AA のバブルソートによる交換回数とは,数列 AA に上記のアルゴリズムを適用した時に,整数の交換が行われる回数である.(バブルソートとして知られるアルゴリズム及び実装には,ループの順番や範囲,及び終了条件など,細かな差異がある場合がある.ただし,同じ数列に適用した際の整数の交換回数はそれらの差異により変化しないことが知られている.)

例えば,以下のプログラムは長さ n の整数の配列 a をバブルソートによりソートする関数を C 言語で記述したものである.

`void bubble_sort(int *a, int n) {   int i, j;   for (i = 0; i < n - 1; ++i) {     for (j = 0; j < n - 1; ++j) {       if (a[j] > a[j + 1]) {         /* 以下 3 行が 1 回の整数の交換に相当 */         int x = a[j];         a[j] = a[j + 1];         a[j + 1] = x;       }     }   } }`

課題

長さ NN の数列 AA が与えられる.数列 AA の任意の場所の 22 つの整数を 11 回だけ交換した数列 AA' を作るとする.数列 AA' のバブルソートによる交換回数の最小値を求めるプログラムを作成せよ.(最初に交換する 22 つの整数は必ずしも隣り合っている必要はないことに注意せよ.)

制限

2leqqNleqq100,0002 \\leqq N \\leqq 100\\,000