28398번 - I forgor 💀

문제

무메이는 기억력 향상을 위해 매일매일 같은 그림 찾기 게임으로 수련하고 있다. 이 게임에는 1ドル$부터 $N$까지의 정수가 적힌 카드가 수마다 두 장씩 있다. 이 카드들을 섞고 책상에 일렬로 내려놓아 수가 보이지 않게 한다. 턴마다 무메이는 카드를 두 장 골라 뒤집은 다음, 두 카드에 쓰인 수가 같다면 둘을 책상에서 치우고, 아니라면 도로 뒤집어 놓는다. 이를 반복해서 모든 카드를 책상에서 치우는 것이 목표이다.

때는 2043년. 무메이는 이 게임에서 어떤 실수도 범하지 않을 정도로 누구보다 뛰어난 기억력을 얻게 되었다. 이제 무메이는 다음과 같이 정해진 절차로 게임을 진행한다.

1. 같은 수가 쓰인 카드 한 쌍을 알고 있다면, 그 두 카드를 뒤집고 책상에서 치운다.
2. 그렇지 않다면, 우선 뒤집어 본 적 없는 카드 중 맨 왼쪽에 있는 것을 뒤집는다.
   1. 해당 카드와 같은 수가 쓰인 다른 카드를 알고 있다면, 그 카드를 뒤집고 둘을 책상에서 치운다.
   2. 그렇지 않다면, 여전히 지금까지 뒤집어 본 적 없는 카드 중 맨 왼쪽에 있는 것을 뒤집는다. 두 카드에 적힌 수가 같다면 둘을 책상에서 치우고, 아니라면 도로 뒤집어 놓는다.

위 절차를 따르면 턴마다 고를 카드 쌍이 유일하게 결정됨을 증명할 수 있다.

당신은 책상의 카드를 탐지해 게임을 마치는 데 필요한 턴 수를 미리 알려주는 프로그램을 작성하기로 했다. 그런데 게임이 너무 재미없다고 생각한 장난꾸러기 벨즈가 카드 쌍을 아무렇게나 서로 바꾸기 시작했다. 카드가 바뀔 때마다 필요한 턴 수를 구하는 프로그램을 작성하여라.

입력

첫 줄에 카드의 종류 수 $N$과 카드를 바꾸는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1\leq N,Q\leq 200,円 000)$

다음 줄에 일렬로 놓인 카드에 적힌 수가 공백으로 구분되어 차례대로 주어진다. 모든 수는 1ドル$ 이상 $N$ 이하의 정수이며, 각 정수는 정확히 두 번씩 등장한다.

다음 $Q$줄에 $l$번째와 $r$번째 카드를 서로 바꿨음을 나타내는 정수 $l$과 $r$이 공백으로 구분되어 주어진다. 모든 행동의 영향은 누적된다. 즉 모든 $i$에 대해 초기 상태에서 1,2,ドル\cdots ,i-1$번째 행동이 차례대로 시행된 다음에 $i$번째 행동이 시행된다. $(1\leq l<r\leq 2N)$

출력

첫 줄에는 초기 상태에서 게임을 마치는 데 필요한 턴 수를 출력한다.

다음 줄부터 $Q$줄에 걸쳐 각 행동이 시행된 뒤에 게임을 마치는 데 필요한 턴 수를 출력한다.

제한

힌트