0 #P5360. [Lydsy1805月赛]二叉排序树

    ID: 4373 传统题 1000ms 512MiB 尝试: 101 已通过: 18 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划以值为状态状态维度消除数论约数成对枚举组合数学组合数乘法递推乘法原理构造与建模排列构造递归构造树算法二叉树遍历CF2500

[Lydsy1805月赛]二叉排序树

二叉排序树

题目描述

二叉排序树是一棵空树,或者是一棵满足以下性质的二叉树:

  • 若左子树非空,左子树中所有节点的值都小于或等于根节点的值。
  • 若右子树非空,右子树中所有节点的值都大于或等于根节点的值。
  • 左、右子树也都是二叉排序树。

按顺序将 nn 个互不相同的数 a1,a2,…,ana_1,a_2,\ldots,a_n 插入一棵空二叉排序树。插入 xx 时,从根开始:若当前节点为空,将其值设为 xx 并结束;否则,若 xx 小于当前节点的值,则递归插入左子树,反之递归插入右子树。

打乱一个序列的插入顺序后,可能仍得到完全相同的二叉排序树。例如 (2,3,1)(2,3,1) 与 (2,1,3)(2,1,3) 的结果相同。

给定 kk,判断是否存在一个序列,使恰好有 kk 种排列后的插入顺序,得到的树与原顺序插入所得的树完全相同。若存在,请构造一个满足输出要求的序列。

输入格式

从标准输入读入一个正整数 kk,满足 1≤k≤1091\le k\le10^9。

输出格式

若无解,向标准输出写出一行 -1。

否则,第一行输出正整数 nn,满足 1≤n≤40001\le n\le4000;第二行输出 nn 个互不相同的正整数 aia_i,满足 1≤ai≤n1\le a_i\le n。

若有多组合法解,可以输出任意一组。

样例

输入

8

输出

5
2 1 4 3 5

解释

对应的八种插入顺序为:

2 1 4 3 5
2 1 4 5 3
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 4 5 1 3
2 4 5 3 1

鸣谢 Claris 提供原题。