섬

2020년 국제 정보 올림피아드(IOI)는 국토 면적이 작고 수많은 섬으로 이루어진 나라인 Singapore에서 개최된다. IOI의 견학 중 하나에서 $N$명의 참가자는 이 섬들을 방문한다. 하지만 참가자들은 Fibonacci 힙을 어떻게 구현할지 생각하느라, 한 명씩 길을 잃고 돌아오지 못한다.

첫 번째 섬에서는 참가자 한 명이 사라지고, 두 번째 섬에서는 참가자 한 명이 더 사라진다. $a_i$이 섬 $i$에서 사라지는 참가자 수라면, 섬 $k$에서는 $a_{k-2} + a_{k-1}$명이 사라진다(남아 있는 참가자가 그보다 적다면 남아 있는 참가자 수만큼 사라진다).

그림은 첫 번째 예제에서 마지막(열두 번째) 참가자가 번호 5인 섬에서 사라진 뒤의 상황을 보여 준다.

마지막 참가자는 어느 섬에서 사라지는가?

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

케이스 | 배점 | 제한

$1$ |$40$| 마지막 섬에서 정확히 $a_k$명의 참가자가 사라진다.

$2$ |$60$| 추가 제한 없음.

첫 번째 줄에 참가자 수를 나타내는 정수 $1\le N \le 10\,000$이 주어진다.

$N$번째 참가자가 사라지는 섬의 번호인 정수 $A$을 출력한다.