20934번 - 카드 모래성 출처분류

모래성 게임은 모래로 이루어진 성을 번갈아 가며 조금씩 가져가면서, 모래성을 쓰러뜨린 사람이 패배하는 게임이다. 주현이와 세중이는 옛 추억에 젖어 모래성 게임을 하고 싶었지만, 근처에 있는 모래장이 폐쇄되어 할 수 없었다. 그래도 $1$과 $5$ 사이의 양의 정수가 적힌 $N$장의 카드는 가지고 있었기 때문에, 카드로 즐길 수 있는 모래성 게임을 생각해냈다. 카드 모래성 게임의 규칙은 다음과 같다.

1. $N$개의 카드 슬롯을 준비하고, 각 슬롯에 $1$부터 $N$까지 번호를 매긴다.
2. 각 카드 슬롯에, $1$과 $5$ 사이의 양의 정수가 적힌 카드 한 장을 올려 둔다.
3. 두 사람은 서로 번갈아 가며 턴을 진행한다.
4. 각 사람의 턴이 되면, $N$개의 카드 슬롯 중 비어 있지 않은 카드 슬롯을 선택한다. 이때, 선택한 카드 슬롯의 번호가 $i$이고, 그 카드 슬롯에 놓인 카드에 적힌 숫자가 $c_i$라면 카드 슬롯을 선택한 사람은 해당 카드 슬롯을 포함하여 $i$번, $i+1$번, $...$, $i+c_i$번 카드 슬롯에 놓여 있는 카드들을 전부 가져가야 한다. 만약 그러한 카드 슬롯 중에 하나라도 존재하지 않거나 비어 있다면, $i$번 카드 슬롯을 선택할 수 없다.
5. 자신의 턴에 더이상 선택할 수 있는 카드 슬롯이 없는 사람은 게임에서 지게 된다.

머리가 좋은 세중이는 항상 최적의 방법으로 카드를 가져갈 것이다. 선공을 잡은 주현이는 당신의 훈수를 들어서라도 게임에서 이기고 싶어 한다. 승리에 목말라 있는 주현이를 위해, 훈수를 두어 보자.

첫째 줄에 카드의 개수 $N$이 주어진다. ($1 \le N \le 200$)

둘째 줄에 각 카드 슬롯들에 놓인 카드들에 적힌 숫자 $c_1$, $c_2$, $c_3$, $...$, $c_N$이 공백으로 구분되어 순서대로 주어진다. ($1 \le c_i \le 5$)

선공인 주현이가 승리하기 위해, 가장 처음으로 선택해야 하는 카드 슬롯의 번호를 출력한다.

만약 그러한 답이 여러 개라면, 가장 작은 답을 출력한다.

어떤 카드를 선택하더라도 주현이가 이길 수 없으면, -1을 출력한다.