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

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

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

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

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

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

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