시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB179916847.887%

문제

구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 N개 포함되어 있는 돌 더미 1개에서 시작한다. 두 사람은 턴을 번갈아 가지며, 구사과가 턴을 먼저 갖는다. 각 턴마다 다음을 할 수 있다.

  • 돌 더미 하나를 고르고, 돌 더미 k(k ≥ 2)개로 나눈다.
  • 새로 만든 돌 더미에 포함된 돌의 개수를 a1, a2, ..., ak라고 했을 때, a1 > a2 > ... > ak > 0, a1 - a2 = a2 - a3 = ... = ak-1 - ak = 1을 만족해야 한다.

더 이상 나눌 돌 더미가 없는 사람이 게임에서 진다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다.

출력

구사과가 이기는 경우에는 첫 턴에서 구사과가 만든 돌 더미의 개수 k를 출력한다. 가능한 k가 여러가지인 경우에는 가장 작은 값을 출력한다. 큐브러버가 이기는 경우에는 -1을 출력한다.

예제 입력 1

3

예제 출력 1

2

예제 입력 2

6

예제 출력 2

-1

예제 입력 3

100

예제 출력 3

8

출처