连写序列

题目描述

连写序列是将正整数从 1 开始，按从小到大顺序以十进制形式拼接而成的序列。例如，前 16 个数字构成的连写序列为 12345678910111213141516 。现给定一个整数 $n$ ，需要在连写序列中找出第 $n$ 个数字。

输入格式

输入为单个整数 $n$ 。

输出格式

输出单个数字作为答案。

数据范围

• 对于 30% 的数据，$1 \leq n \leq 1000$ 。
• 对于 60% 的数据，$1 \leq n \leq 10^9$ 。
• 对于 100% 的数据，$1 \leq n \leq 10^{18}$ 。

输入输出样例

输入样例 1

1

输出样例 1

1

输入样例 2

10

输出样例 2

1