Stones

• 홀수턴에는 상대가 위치선택 → 내가 갯수선택. 짝수턴에는 내가 위치선택 → 상대가 갯수선택 으로 진행되는데.. 이렇게 보면 잘 안와닿지만 순서를 바꿔서 생각하면 간단해진다.
• 각자 자기턴에, 현재 위치에서 원하는 만큼 제거하고 다음 위치로 이동시킨뒤에 상대에게 턴을 넘긴다고 생각해보자. 이제 많이 보던 게임들과 비슷해졌다. 예를들면 게임이론. 이런 게임의 기본 전략은 상대에게 선택지를 주지 않는 것이다. 구체적으로 상대방에게는 돌이 1개만 남은 파일을 지정해줘서 항상 1개밖에 먹을수 없게 하는 것이다.
• 이 전략을 기본으로 구체적인 전략을 생각해보자. 가장 단순한 경우는 모든 파일에 돌이 2개 이상 있는 경우이다. 이때는 내가 현재 파일에서 1개만 남기고 제거한 뒤에 현재 파일을 넘겨준다. 상대는 1개를 제거해서 현재 파일을 없애고, 다른 파일을 나에게 지정해줄수밖에 없다. 나는 다시 그 파일에서 1개만 남기고 제거한뒤에 그 파일을 다시 지정해주고.. 이것을 반복하다가 파일이 1개만 남는 상황이 되면 다 제거하고 이기면 된다.
• 이제 모든 경우에 대해서 발전시켜보자. 나한테 지정된 파일에 돌이 1개밖에 없다면 나 역시 선택지가 없으니 생각할 필요가 없다. 1개 제거한 다음에 돌이 1개뿐인 다른 파일을 상대한테 지정해주면 된다. 돌이 1개뿐인 파일이 없다면 위에서 말한 상황이 되어서 상대가 이기게 되는데, 문제에서 처음 포지션은 항상 승리포지션으로 주어진다고 했으니 돌이 1개뿐인 다른 파일이 없는 경우는 일어나지 않는다.
• 이제 나한테 지정된 파일에 돌이 2개 이상 있을텐데, 이때는 파일을 다 제거할 것인지, 1개를 남기고 제거할 것인지를 결정해야 한다. 이것은 돌이 2개이상 있는 파일이 여러개 있을때와 1개만 있을때, 그리고 돌이 1개인 파일이 홀수개 있을때와 짝수개 있을때로 나누어서 4개 케이스에 대해서 전략이 달라진다. 답만 말하면 (2개이상짜리 파일이 여러개, 1개짜리 파일이 홀수개) 또는 (2개이상짜리 파일이 1개, 1개짜리 파일이 짝수개) 인 경우에는 다 제거해야 하고, 나머지 경우에는 1개를 남기고 제거해야 한다.
• 돌이 1개짜리 파일들을 셋으로 관리하면, 상대방한테 지정해줄 파일을 O(1)에 고를수 있고, 한턴을 O(1)에 진행할수 있다. 내턴+상대방턴에 파일 1개 이상이 줄어드므로, 게임이 종료되기까지는 O(n)턴이 걸린다.

"""Solution code for "BOJ 23066. Stones".

- Problem link: https://www.acmicpc.net/problem/23066
- Solution link: http://www.teferi.net/ps/problems/boj/23066

Tags: [game theory]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    a = [int(x) for x in sys.stdin.readline().split()]

    single_stone_piles = {i for i, a_i in enumerate(a) if a_i == 1}
    multiple_stone_pile_count = N - len(single_stone_piles)
    while True:
        k = int(sys.stdin.readline()) - 1

        if a[k] > 1:
            should_take_all = (multiple_stone_pile_count == 1) == (
                len(single_stone_piles) % 2 == 0
            )
            if should_take_all:
                print(a[k])
            else:
                print(a[k] - 1)
                single_stone_piles.add(k)
            multiple_stone_pile_count -= 1
        else:
            print(a[k])
            single_stone_piles.discard(k)

        if single_stone_piles:
            print(single_stone_piles.pop() + 1, flush=True)
        else:
            print('-1', flush=True)
            break

        y = int(sys.stdin.readline())


if __name__ == '__main__':
    main()