题目描述

$(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\sim n$ 的排列，现在要对它进行一次翻转操作，将区间 $[L,R]$ 翻转，$L\leq R$。显然一共有 $\frac{n(n+1)}{2}$ 组 $L,R$，且每一组 $L,R$ 都对应着一个排列，请输出这些排列中，字典序第 $k$ 小的。

3 5
1 3 2

2 3 1

5 15
1 2 3 4 5

5 4 3 2 1

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

9 2 1 6 5 4 10 7 8 3

提示

制約

• $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)$ です。