問題文

長さ $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$ 点となる。

入力例0Copy

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

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

出力例0Copy

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$ のデータです。