책장 정리

Irma는 도서관에서 일한다. 매일 그녀는 방문객들이 책장에서 책 몇 권을 꺼내 읽고, 꺼낸 자리에 그대로 다시 꽂는 모습을 본다. 보통 사람들은 순서를 어지럽혀서 읽은 두 권의 책 위치를 서로 바꾼다. $n$권의 책이 어떤 순서로 꽂혀 있는 특정 책장 하나를 살펴보자. 책에는 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호가 붙어 있다. $i$번째 방문객은 $x\_i$번 위치와 $y\_i$번 위치의 책을 꺼내 같은 위치에 다시 꽂지만, 순서를 잘못 바꿔 놓는다. $i$번째 방문객이 떠난 뒤에는 $x\_i$번 위치에 있던 책이 $y\_i$번 위치로, $y\_i$번 위치에 있던 책이 $x\_i$번 위치로 간다.

저녁에 도서관 문을 닫은 뒤 Irma는 모든 책을 제자리에 돌려놓으려 한다. 각 책에는 $p\_i$라는 번호가 있는데, 이 책이 최종적으로 있어야 할 위치다. 책을 옮기기 위해 Irma는 책장에서 아무 책이나 꺼내 맨 앞이나 맨 뒤에 꽂을 수 있다. 그러면 그 책은 책장의 첫 번째 또는 마지막 자리에 놓인다.

Irma가 모든 책을 제자리에 돌려놓기 위해 할 수 있는 최소 이동 횟수는 얼마인가? 이 질문에 $p\_i$로 정해지는 초기 배치와, 방문객이 두 책의 위치를 바꿀 때마다 답하시오.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. ($2 \le n \le 2 \cdot 10^5$; $0 \le q \le 2 \cdot 10^5$) $n$은 책장에 있는 책의 수, $q$는 방문객의 수다. 다음 줄에는 $n$개의 서로 다른 정수 $p\_i$가 주어진다. ($1 \le p\_i \le n$) 이는 $i$번 위치에 있는 책이 최종적으로 $p\_i$번 위치에 있어야 한다는 뜻이다.

다음 $q$개 줄은 도서관 방문객을 나타낸다. 각 줄에는 두 정수 $x\_i$, $y\_i$가 주어진다. ($1 \le x\_i < y\_i \le n$) 이는 $i$번째 방문객이 $x\_i$번 위치와 $y\_i$번 위치의 책 두 권을 바꿔 놓았다는 뜻이다.

$q + 1$개의 정수를 출력한다. 초기 순서에서 모든 책을 정리하는 데 필요한 최소 이동 횟수, 첫 번째 방문객이 떠난 뒤의 순서에서 필요한 최소 이동 횟수, ..., $q$명의 방문객이 모두 떠난 뒤의 순서에서 필요한 최소 이동 횟수를 차례로 출력한다.

책의 초기 순서는 $(5, 1, 2, 4, 3)$이다. 이 책을 정리하려면 먼저 책 $4$를 맨 뒤로 옮기고, 그다음 책 $5$를 맨 뒤로 옮기면 된다. 첫 번째 방문객이 떠난 뒤 책장은 $(5, 1, 2, 3, 4)$가 되고, 책 $5$를 맨 뒤로 옮기기만 하면 된다. 두 번째 방문객이 떠난 뒤 책의 순서는 $(3, 1, 2, 5, 4)$이다. 이 순서에서 최소 이동 횟수는 $3$이며, $3$번의 이동으로 최종 순서를 만드는 방법은 여러 가지다.