Thu Thập Số II

Cho một hoán vị của các số $1,2,\dots ,n$. Bạn cần thu thập các số theo thứ tự tăng dần bằng cách duyệt mảng từ trái sang phải nhiều lượt.

Sau mỗi thao tác hoán đổi hai vị trí trong mảng, hãy in ra số lượt tối thiểu cần thiết để thu thập tất cả các số.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$
• Dòng 2: $n$ số nguyên — hoán vị của $1,2,\dots ,n$
• $m$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a$ và $b$ — hoán đổi phần tử tại vị trí $a$ và vị trí $b$

Dữ liệu ra

In ra $m$ số nguyên — mỗi dòng là số lượt cần thiết sau thao tác tương ứng.

Ràng buộc

• $1\le n,m\le 2\times {10}^5$
• $1\le a,b\le n$

Ví dụ