Start: 2024-02-15 00:00:00

(23-24赛季)稠州常规赛07

End: 2024-02-17 00:00:00
Now  2026-05-09 19:37:05  类型: IOI  状态: Ended 

P4. 守序数
Description

如果一个十进制正整数的任意两个相邻的数字之差均不超过 1,则称该数字为守序数。

1 是第一个守序数,给定 n 请求出第 n 个守序数。


Input

单个整数表示 n

Output

单个整数表示答案

Examples

Input

13

Output

21
Hint

30\% 的数据,1\leq n\leq 100

60\% 的数据,1\leq n\leq 10000

100\% 的数据,1\leq n\leq 1,000,000


Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit