問題文

長さ N = 30000 の数列 A が与えられます。A には 1 から N までの整数が 1 回ずつ現れます。ここから、あなたは以下の操作を K 回行います。

• 整数 i, j, k, l, v (1 ≦ i ≦ j ≦ N, 1 ≦ k ≦ l ≦ N, 0 ≦ v ≦ N - 1) を指定する。A_i, A_{i+1}, ... , A_{j} の値をそれぞれ v 減少させ、 A_k, A_{k+1}, ... , A_{l} の値をそれぞれ v 増加させる。
• ただし、A のすべての要素は常に 1 以上 N 以下でなければならない。同じ値が複数出現することは許される。
• また、区間 [i, j] と区間 [k, l] に重複があってはならず、2 つの区間の長さは等しくなければならない。

あなたは、この操作により、A の各要素の値を A_1 = 1, A_2 = 2, ... , A_N = N にできるだけ近づけたいです。 値 |A_1 - 1| + |A_2 - 2| + … + |A_N - N| ができるだけ小さくなるような手順を出力してください。

制約

• N = 30000
• 1000 ≦ K ≦ 3000
• 与えられる A は 1 から N までの整数のランダムな順列である。

採点方法

1 つのテストケースに対する点数は、生成された数列を A として 1,000,000,000 - |A_1 - 1| - |A_2 - 2| - … - |A_N - N| 点となる。

テストケースは 41 ケース与えられる。それぞれのテストケースについて、K = 1000, 1050, 1100, …, 2950, 3000 である。すべてのテストケースに対する点数の和が、その提出の得点となる。

なお、1 ケースでも出力が不正であった場合、example_01 以外の点数は全て 0 点となる。

入力例0

10 3
8
9
1
4
6
7
3
2
10
5

• この入力は制約を満たしません。

出力例0

1 2 7 8 6
7 7 5 5 4
5 5 10 10 5  

• 初期状態は {8,9,1,4,6,7,3,2,10,5} です。以下次のように変化します。
• {2,3,1,4,6,7,9,8,10,5}
• {2,3,1,4,10,7,5,8,10,5}
• {2,3,1,4,5,7,5,8,10,10}

入力例1

入力ファイル例はこちらから(zip)

採点結果の「example_01」が、こちらのデータとなります。このデータも採点対象となります。 なお、example_01 は K=2000 のデータです。