나누기 게임

시간 제한1초메모리 제한512 MB

요약

N개의 돌 더미에서 시작해 한 더미를 연속된 내림차순 k개 더미로 나누는 게임에서, 선공이 이기기 위한 가장 작은 첫 분할 k 또는 -1을 구한다.

문제

구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 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을 출력한다.