問題文

$N(N+1)/2$ 個のボールが下図のように $N$ 段のピラミッド型に並んでいる。 ピラミッドの頂上のボールの座標を $(0, 0)$ とし、$x (0\\leq x\\leq N-1)$ 段目の左から $y (0\\leq y\\leq x)$ 個目のボールの座標を $(x,y)$ とする。

各ボールには $0$ 〜 $N(N+1)/2-1$ の数字が書かれており、各ボールの数字は全て異なる。 一回の操作で6方向に隣接する2つのボールを入れ替えることが出来る。 ここで、座標 $(x_1,y_1)$ と $(x_2,y_2)$ にあるボールは以下のいずれかの条件を満たす場合に6方向に隣接している。

• $x_1=x_2-1$ かつ $y_1=y_2-1$
• $x_1=x_2-1$ かつ $y_1=y_2$
• $x_1=x_2$ かつ $y_1=y_2-1$
• $x_1=x_2$ かつ $y_1=y_2+1$
• $x_1=x_2+1$ かつ $y_1=y_2$
• $x_1=x_2+1$ かつ $y_1=y_2+1$

この操作を最大 $10000$ 回繰り返すことで、最下層を除くどのボール $(x,y) (0\\leq x\\leq N-2, 0\\leq y\\leq x)$ も自身の直下にある2つのボール $(x+1,y), (x+1,y+1)$ よりも小さい数字となるようにしたい。 出来るだけ操作回数が少なくなるような操作列を求めて欲しい。

得点

操作回数を $K$、操作終了後に条件に違反しているボールのペアの数を $E$ とする。 $E$ は $(x,y)$ と $(x+1,y') (y'\\in\\{y,y+1\\})$ の組であって、$(x,y)$ のボールの数字の方が $(x+1,y')$ のボールの数字より大きいようなものの総数である。

このとき、以下のスコアが得られる。

• $E=0$ の場合、$100000-5K$
• $E>0$ の場合、$50000-50E$

テストケースは全部で 150 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWA