/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます． また整数 K も与えられます．
あなたはこれから以下の操作を 0 回以上行います．
- 整数 l,r (1 \leq l < r \leq N) を選ぶ．ただしここで (l,r) は以下の条件をすべて満たす必要がある．
- K \leq r-l
- 操作を行う段階で P_l>P_r である．
- 同じ組 (l,r) を今までに選んだことが一度もない．
- そして，P_l と P_r の値を入れ替える．
あなたは操作回数を最大化したいです． その方法を一つ求めてください．
制約
- 2 \leq N \leq 500
- 1 \leq K \leq N-1
- (P_1,P_2,\cdots,P_N) は (1,2,\cdots,N) の順列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N K P_1 P_2 \cdots P_N
出力
以下の形式で答えを出力せよ．
m l_1 r_1 l_2 r_2 \vdots l_m r_m
ただしここで m は操作回数の最大値であり，l_i,r_i は i 回目の操作で選んだ l,r の値である． 複数の解がある場合は，どれを出力してもよい．
入力例 1
3 1 3 2 1
出力例 1
3 2 3 1 3 1 2
この例では操作回数の最大値は 3 です． 出力例の操作の様子は以下のとおりです．
- 1 回目の操作: (l,r)=(2,3) を選ぶ．1 \leq 3-2,\ P_2>P_3 かつ (2,3) を選んだことはないので条件は満たされている．P_2,P_3 の値を入れ替え，P=(3,1,2) になる．
- 2 回目の操作: (l,r)=(1,3) を選ぶ．1 \leq 3-1,\ P_1>P_3 かつ (1,3) を選んだことはないので条件は満たされている．P_1,P_3 の値を入れ替え，P=(2,1,3) になる．
- 3 回目の操作: (l,r)=(1,2) を選ぶ．1 \leq 2-1,\ P_1>P_2 かつ (1,2) を選んだことはないので条件は満たされている．P_1,P_2 の値を入れ替え，P=(1,2,3) になる．
入力例 2
5 4 1 4 3 2 5
出力例 2
0
入力例 3
4 2 4 1 2 3
出力例 3
2 1 4 1 3
入力例 4
10 5 8 7 6 10 9 3 1 5 2 4
出力例 4
15 3 8 2 8 3 10 3 9 1 8 2 10 2 9 2 7 1 10 5 10 1 9 4 10 4 9 1 7 1 6
Score : 600 points
Problem Statement
You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N). Additionally, you are given an integer K.
You can perform the following operation zero or more times:
- Choose integers l and r (1 \leq l < r \leq N). Here, the pair (l,r) must satisfy all of the following conditions:
- K \leq r-l.
- P_l > P_r at the time of the operation.
- The pair (l,r) has never been chosen before.
- Then, swap the values of P_l and P_r.
You want to maximize the number of operations. Find one way to achieve this.
Constraints
- 2 \leq N \leq 500
- 1 \leq K \leq N-1
- (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \cdots P_N
Output
Print the answer in the following format:
m l_1 r_1 l_2 r_2 \vdots l_m r_m
Here, m is the maximum number of operations, and l_i and r_i are the values of l and r chosen in the i-th operation, respectively. If multiple solutions exist, you can print any of them.
Sample Input 1
3 1 3 2 1
Sample Output 1
3 2 3 1 3 1 2
In this example, the maximum number of operations is 3. The operations in the sample output proceed as follows:
- 1st operation: Choose (l,r)=(2,3). We have 1 \leq 3-2 and P_2 > P_3, and (2,3) has not been chosen before, so the conditions are satisfied. Swap P_2 and P_3, resulting in P=(3,1,2).
- 2nd operation: Choose (l,r)=(1,3). We have 1 \leq 3-1 and P_1 > P_3, and (1,3) has not been chosen before, so the conditions are satisfied. Swap P_1 and P_3, resulting in P=(2,1,3).
- 3rd operation: Choose (l,r)=(1,2). We have 1 \leq 2-1 and P_1 > P_2, and (1,2) has not been chosen before, so the conditions are satisfied. Swap P_1 and P_2, resulting in P=(1,2,3).
Sample Input 2
5 4 1 4 3 2 5
Sample Output 2
0
Sample Input 3
4 2 4 1 2 3
Sample Output 3
2 1 4 1 3
Sample Input 4
10 5 8 7 6 10 9 3 1 5 2 4
Sample Output 4
15 3 8 2 8 3 10 3 9 1 8 2 10 2 9 2 7 1 10 5 10 1 9 4 10 4 9 1 7 1 6