No.397 NO MORE KADOMATSU

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 148
作問者 : koyumeishikoyumeishi / テスター : btkbtk
1 ProblemId : 1233 / 出題時の順位表

問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

  • $A_1, A_2, A_3$ は全て異なる
  • $3$ つの要素の中で $A_2$ が最も大きい,または,$A_2$ が最も小さい

先日の門松列コンテストが不評だったので、門松列をぶち壊します。

長さ $N$ の数列 $A$ が与えられます。
あなたは

  • $A$ の $u$番目の要素と $v$番目の要素を入れ替える ($0 \leq u,v < N$ , $u \neq v$)
という操作を何度もすることができます。
この操作を繰り返して、 $A$ の連続部分列に門松列を含まないようにしてください。
操作後の $A$ に $A_i, A_{i+1}, A_{i+2}$ が門松列となるような $i$ が存在すると不正解となります。

クエリ数が見えると面白いかもと思ったので、リアクティブ問題になっています。 入出力の項を注意して読んでください。

入力

$N$
$A_0$ $A_1$ ... $A_{N-1}$
$Dummy$

1 行目に数列の長さ $N$ 、 2 行目に$A$の各要素が空白区切りで与えられます。
3 行目の入力はリアクティブジャッジ用のダミー入力です。 解答を出力した後に受け取ってください。 (受け取らなくても通るかも知れませんが、念のため)
入力は全て整数で、以下の制約を満たします。
$3 \leq N \leq 100$
$1 \leq A_i \leq 100$
$Dummy = -1$

出力

$M$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$

1 行目に操作の回数、 2 行目以降に 1 行ずつに i 回目の操作の $u$,$v$ ($0 \leq u,v < N$ , $u \neq v$) を出力してください。
最後に標準出力の flush をしてください。
特に交換回数に制限はありませんが、あまりに多いとジャッジ側が TLE するかもしれません。

サンプル

サンプル1
入力
3
1 3 2
-1
出力例
2
0 1
1 2

出力の一例です。
[1,3,2] -> [3,1,2] -> [3,2,1] となり、連続部分列に門松列を含まなくなります。
0-indexed であることに留意してください。 また、ダミー入力は解答出力後に受け取ってください

サンプル2
入力
6
1 3 2 2 3 1
-1
出力例
1
1 5

[1,3,2,2,3,1] -> [1,1,2,2,3,3]

サンプル3
入力
10
1 2 3 4 5 6 7 8 9 10
-1
出力例
0

元々門松列を含まないので交換回数はゼロでも大丈夫です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。