AT_arc160_a [ARC160A] Reverse and Count

[problemUrl]: https://atcoder.jp/contests/arc160/tasks/arc160_a $ (1,\ 2,\ \dots,\ N) $ の順列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_N) $ が与えられます。 $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ を満たす整数の組 $ (L,\ R) $ に対して、$ A $ の $ L $ 番目から $ R $ 番目までの要素を反転してできる順列を $ f(L,\ R) $ とします。 ここで、「$ A $ の $ L $ 番目から $ R $ 番目までの要素を反転する」とは、$ A_L,\ A_{L+1},\ \dots,\ A_{R-1},\ A_R $ を $ A_R,\ A_{R-1},\ \dots,\ A_{L+1},\ A_{L} $ に同時に置き換えることを言います。 $ (L,\ R) $ を $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ を満たすように選ぶ方法は $ \frac{N(N\ +\ 1)}{2} $ 通りあります。 このような $ (L,\ R) $ の組全てに対して順列 $ f(L,\ R) $ をすべて列挙して辞書順にソートしたときに、先頭から $ K $ 番目にある順列を求めてください。 数列の辞書順とは？数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します。 1. $ |S|\ \lt\ |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|})\ =\ (T_1,T_2,\ldots,T_{|S|}) $。 2. ある整数 $ 1\ \leq\ i\ \leq\ \min\lbrace\ |S|,\ |T|\ \rbrace $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (S_1,S_2,\ldots,S_{i-1})\ =\ (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ が $ T_i $ より（数として）小さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

順列 $ f(L,\ R) $ を列挙して辞書順にソートしたときに、先頭から $ K $ 番目にある順列を $ B\ =(B_1,\ B_2,\ \dots,\ B_N) $ とする。 このとき以下の形式で $ B $ を出力せよ。 > $ B_1 $ $ B_2 $ $ \dots $ $ B_N $

### 制約 - $ 1\ \leq\ N\ \leq\ 7000 $ - $ 1\ \leq\ K\ \leq\ \frac{N(N\ +\ 1)}{2} $ - $ A $ は $ (1,\ 2,\ \dots,\ N) $ の順列 ### Sample Explanation 1 $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ を満たす $ (L,\ R) $ の組全てに対して順列 $ f(L,\ R) $ をすべて列挙すると次のようになります。 - $ f(1,\ 1)\ =\ (1,\ 3,\ 2) $ - $ f(1,\ 2)\ =\ (3,\ 1,\ 2) $ - $ f(1,\ 3)\ =\ (2,\ 3,\ 1) $ - $ f(2,\ 2)\ =\ (1,\ 3,\ 2) $ - $ f(2,\ 3)\ =\ (1,\ 2,\ 3) $ - $ f(3,\ 3)\ =\ (1,\ 3,\ 2) $ これらを辞書順にソートしたときに $ 5 $ 番目に来る順列は $ f(1,\ 3)\ =\ (2,\ 3,\ 1) $ です。よってこれを出力します。 ### Sample Explanation 2 答えは $ f(1,\ 5) $ です。