정렬하기

• 처음에 정렬된 상태면 0라운드만에 끝나니까 더 생각할 필요가 없다.
• 처음에 정렬된 상태가 아니라면, 여기에서 에르맥은 한 번에 정렬이 될 수 없는 상태로 바꿀수 있다. 이후에는 아이잔이 어떻게 두 수를 바꾸어도, 에르맥이 똑같은 두 수를 다시 바꾸면 원래대로 돌아가므로 무한히 끝나지 않는다.
  • 에르맥이 한번에 정렬이 될수 없는 상태로 만들수 있다는 것은 자명하다.. 쉽게 생각하면 [작성중] 순열 사이클 분할 (Permutation cycle decomposition)의 이론을 생각해서, 처음에 사이클의 개수가 N-1 개라면 사이클의 개수가 N-2개가 되도록 스왑해주면, 아이잔은 어떻게 움직여도 사이클의 개수를 1개 이상 늘릴 수 없으므로 한번의 스왑으로 정렬시킬수 없다.
• 결국 해야할 것은 S가 바뀔때마다, S가 정렬된 상태인지 아닌지만 확인해주면 된다. 이것은 단순히 잘못된 위치에 놓여져 있는 원소의 개수를 추적하지만 하면 되므로 O(1)에 가능하다. 총 시간복잡도는 O(n+m)
• 실수하기 쉬운 부분은, N=2일 때에는 예외처리가 필요하다는 점이다. N=2라면, 에르맥이 어떻게 하더라도, 아이잔이 정렬시킬수 있다. 결국 답은 0 또는 1이 나온다.
  • N=1일때에는 모든 답이 1이지만, 따로 예외처리를 하지 않고 문제를 풀더라도 답을 구하는데에는 문제가 없다

"""Solution code for "BOJ 16219. 정렬하기".

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

Tags: [ad hoc]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    S = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())
    X_and_Y = [[int(x) for x in sys.stdin.readline().split()] for _ in range(M)]

    misplaced_count = sum(1 for i, x in enumerate(S) if i != x)
    answers = []
    for x, y in X_and_Y:
        if S[x] == x:
            misplaced_count += 1
        if S[y] == y:
            misplaced_count += 1
        if S[x] == y:
            misplaced_count -= 1
        if S[y] == x:
            misplaced_count -= 1
        S[x], S[y] = S[y], S[x]

        if misplaced_count == 0:
            answers.append('0')
        else:
            answers.append('-1' if N >= 3 else '1')

    print(' '.join(answers))


if __name__ == '__main__':
    main()