이보다 간단할 수 없다!

집에 돌아온 이반은 오늘 수학 동아리 수업에 대해 오랫동안 생각했다. 선생님은 수업에서 무한한 수열을 설명했고, 그중 하나의 예로 다음과 같은 양의 정수 수열을 보여 주었다: $\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}$)이 주어진다.

공백과 불필요한 앞자리 0 없이 정수 하나를 출력한다. 이 수는 주어진 수열의 $n$번째 원소이다.

심사위원단은 모든 테스트에서 제한 시간의 두 배 안에 실행되는 풀이가 존재함을 보장하지 않는다.