들불

다음과 같은 양의 정수 수열 A를 정의한다.

A[0] = 1, A[1] = 1이다. 2 이상의 정수 i에 대해, A[i]는 다음 조건을 만족하는 가장 작은 양의 정수이다. i − 2k ≥ 0인 모든 정수 k > 0에 대해 세 항 A[i − 2k], A[i − k], A[i]가 등차수열을 이루지 않는다. 즉, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k]이다.

이 수열은 다음과 같이 유일하게 결정된다. A[0] = 1, A[1] = 1, A[2] = 2, A[3] = 1, A[4] = 1, A[5] = 2, A[6] = 2, A[7] = 4, A[8] = 4 등. A[2] = 1이면 A[0] = 1, A[1] = 1, A[2] = 1이 등차수열을 이루므로 A[2]는 1이 될 수 없다. 이때 i = 2, k = 1이다. A[2]가 1보다 큰 정수이면 조건을 만족한다. 따라서 A[2]는 가능한 값 중 가장 작은 양의 정수인 2가 된다. 마찬가지로 A[3] = 1임을 쉽게 알 수 있다. A[4] = 3이면 A[4] − A[4 − 2] = A[4 − 2] − A[4 − 2 × 2]이므로 A[4]는 3이 될 수 없다. 이때 i = 4, k = 2이다. A[4]에는 1, 2, 4 같은 다른 자연수도 가능하지만 가장 작은 값은 1이다. 따라서 A[4] = 1이다.

이 수열은 산점도가 들판에 번지는 불처럼 보이기 때문에 “fire on field” 또는 “forest fire”라고 불린다. 아래 그림을 참고하라.

음이 아닌 정수 n이 주어질 때 A[n]을 출력하는 프로그램을 작성하라.

프로그램은 표준 입력에서 데이터를 읽는다. 입력은 음이 아닌 정수 n (0 ≤ n ≤ 1,000) 하나를 포함하는 한 줄로 이루어진다.

프로그램은 표준 출력에 결과를 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 A[n]이 있어야 한다.