Проще не бывает!

문제

Вернувшись домой из школы, Иван долго думал о сегодняшнем занятии кружка по математике, на котором учитель рассказывал о бесконечных числовых последовательностях. В качестве одного из примеров рассматривалась следующая интересная последовательность целых положительных чисел: $$\underbrace{\phantom{,}1},\underbrace{1,2,1},\underbrace{1,2,3,2,1},\underbrace{1,2,3,4,3,2,1},\mathrm{.}\mathrm{.}\mathrm{.}\backslash underbrace\{\backslash vphantom\{,\}1\},\; \backslash underbrace\{1,\; 2,\; 1\},\; \backslash underbrace\{1,\; 2,\; 3,\; 2,\; 1\},\; \backslash underbrace\{1,\; 2,\; 3,\; 4,\; 3,\; 2,\; 1\},\; ...$$

Учитель пояснил, что в этой последовательности каждое целое положительное число встречается бесконечное число раз. Однако Ивана заинтересовал ещё и другой вопрос: как определить, какое число находится в последовательности на месте под номером $nn$? На вопрос Ивана учитель ответил, что это очень просто, и предложил Ивану подумать над этой задачей самостоятельно.

Иван увлекается не только математикой, но и программированием, поэтому ему хочется реализовать алгоритм, который позволит быстро отвечать на поставленный вопрос для очень большого диапазона возможных $nn$. Помогите ему в этом.

입력

В первой строке входных данных находится одно целое число $nn$ ($1\le n\le {10}^{500000}1\; \backslash leq\; n\; \backslash leq\; 10^\{500\backslash ,000\}$).

출력

Выведите одно целое число без пробелов и ведущих нулей --- $nn$-й элемент заданной последовательности.

힌트

Жюри олимпиады не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.