题目描述

如果一个整数序列 $a_1,a_2,\dots,a_n$ 的每个数字都在 $1$ 到 $n$ 之间，且没有两个数字相等，则称这个序列为全排列。例如$1,3,2$ 以及 $4,3,2,1$ 都是全排列。

我们将所有的全排列排序，定义全排列 $a_1,a_2,\dots,a_n$ 与 $b_1,b_2,\dots,b_m$ 的排序先后关系如下：

• 如果 $n<m$，则 $a$ 序列更靠前
• 如果 $n>m$，则 $b$ 序列更靠前
• 如果 $n=m$，则以字典序规则比较 $a$ 序列与 $b$ 序列，字典序更小的序列更靠前。

根据上述定义，可以得到

• 第 $1$ 个全排列是 $1$
• 第 $2$ 个全排列是 $1~2$
• 第 $3$ 个全排列是 $2~1$
• 第 $4$ 个全排列是 $1~2~3$

给定 $k$，请输出第 $k$ 个全排列。

输入格式

• 单个整数：表示 $k$

输出格式

• 单独一行：表示第 $k$ 个全排列

5

1 3 2

数据范围

• $30\%$ 的数据 $1\leq k\leq 1000$
• $60\%$ 的数据 $1\leq k\leq 1,000,000$
• $100\%$ 的数据 $1\leq k\leq 10^{15}$