当前没有测试数据。

题目描述

东东数是一个没有前导号$0$的十进制数（不能以$0$开头），并且任意相邻的两个数位之间的差值小于等于$1$。

如 $12345$、$1122332211$ 和 $34545673$ 都是东东数。

而 $135$、$520$、$1314$ 和 $0112$ 都不是东东数。

求第 $n$ 小的东东数。

输入格式

第一行一个整数 $n$。

输出格式

一个整数。

输入输出样例

样例输入 #1

1

样例输出 #1

1

样例输入 #2

14

样例输出 #2

22

数据范围

对于 $30$ 的数据：$n \le 10^2$

对于 $50$ 的数据：$n \le 10^3$

对于 $70$ 的数据：$n \le 10^4$

对于 $100$ 的数据：$n \le 10^5$