题目描述

海狸 Bert 是各种“树”的专家：白杨树、柳树、杨树、桦树，以及二叉搜索树（Binary Search Tree，BST）。前面那些树适合拿来筑坝，而为了记录自己已经砍下的所有树木，Bert 使用一棵二叉搜索树。

一棵 BST 的每个结点都保存一个值，并满足如下性质：

• 一个结点的值严格大于其左子树中所有结点的值；
• 一个结点的值严格小于其右子树中所有结点的值。

现在考虑一种不会进行旋转或其他再平衡操作的普通 BST 插入。向树中插入一个当前尚未出现的值 $x$ 时，执行以下过程：

1. 从根结点开始；
2. 若当前结点的值小于 $x$，则进入其右子树，否则进入其左子树；
3. 如果要进入的子树不存在，就在该位置新建一个值为 $x$ 的结点；否则继续重复上述过程。

Bert 已经砍下了 $n$ 棵树，并为了方便给它们分别编号为 $1,2,\ldots,n$。他会选择 $1\sim n$ 的一个排列 $p_1,p_2,\ldots,p_n$，然后按这个顺序将编号插入一棵初始为空的 BST。也就是说，$p_1$ 会成为根结点，之后依次插入 $p_2,p_3,\ldots,p_n$。

Bert 希望所有编号插入完成后，得到的 BST 满足 AVL 平衡性质：对于树中的每个结点，其左子树与右子树的高度之差的绝对值不超过 $1$。规定不存在的空子树高度为 $0$，因此叶子结点对应的子树高度为 $1$。

请你求出一个排列 $p_1,p_2,\ldots,p_n$，使得按该排列进行普通 BST 插入后得到一棵满足 AVL 平衡性质的 BST，并且这个排列在所有合法排列中字典序最小。

对于两个长度相同的排列 $p$ 和 $q$，如果在第一个满足 $p_f\ne q_f$ 的位置 $f$ 上有 $p_f<q_f$，则称 $p$ 的字典序小于 $q$。

可以证明，对题目给出的任意合法 $n$，至少存在一个满足要求的排列。

输入格式

输入一行一个整数 $n$，表示 BST 中结点的数量。

$1\le n\le 2\times 10^5$。

输出格式

输出一行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示所求的字典序最小排列。

样例 1

1

1

样例 2

5

2 1 4 3 5

样例说明

对于第二组样例，按照 $2,1,4,3,5$ 的顺序进行普通 BST 插入，最终得到的树为：

    2
   / \
  1   4
     / \
    3   5

它满足 AVL 平衡性质，并且不存在字典序更小的合法插入排列。