Lunlun 数

题目描述

当正整数 $X$ 满足以下条件时,称 $X$ 为 Lunlun 数:

• 将 $X$(不带前导零)十进制表示时,任意相邻两位的差的绝对值都不超过 $1$。

例如,$1234$、$1$、$334$ 等是 Lunlun 数,而 $31415$、$119$、$13579$ 等不是 Lunlun 数。

给定正整数 $K$。求第 $K$ 小的 Lunlun 数。

输入格式

输入按以下格式从标准输入给出:

$K$

输出格式

输出答案。

样例

15

23

将第 $1$ 小到第 $15$ 小的 Lunlun 数从小到大排列:

$1$,$2$,$3$,$4$,$5$,$6$,$7$,$8$,$9$,$10$,$11$,$12$,$21$,$22$,$23$

因此答案是 $23$。

1

1

13

21

100000

3234566667

注意答案可能超出 $32$ 位有符号整数的范围。

数据范围

• $1 \leq K \leq 10^5$
• 输入均为整数