골롱 수열

시간 제한2초메모리 제한128 MB

요약

n이 최대 20억일 때 자기 자신을 정의하는 골롬 수열의 n번째 항을 효율적으로 계산합니다.

문제

골롱 수열은 모든 자연수 k에 대해, 수열 안에서 값 k가 정확히 f(k)번 등장하는 단조 증가 수열이다. 여기서 단조 증가 수열이라는 말은 k가 커질 때 f(k)가 작아지지 않는다는 뜻이며, k와 f(k)는 모두 자연수이다.

이 조건을 만족하는 수열은 하나로 유일하게 정해진다.

n이 주어졌을 때 f(n)을 구하라.

첫째 줄에 n이 주어진다.

첫째 줄에 f(n)을 출력한다.