Bạn được cho một mảng mà chứa mỗi số giữa \(1\ldots n\) chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ $14 đến \(n\) theo thứ tự tăng dần.

Trong mỗi vòng, bạn đi qua mảng từ trái sang phải và thu thập nhiều số nhất có thể.

Cho \(m\) thao tác hoán đổi hai số trong mảng, nhiệm vụ của bạn là báo cáo số lượng vòng sau mỗi thao tác.

Input

• Dòng đầu tiên có hai số nguyên \(n\) và \(m\): kích thước mảng và số lượng phép toán.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các số trong mảng.
• Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có hai số nguyên \(a\) và \(b\): các số tại vị trí \(a\) và \(b\) được hoán đổi.

Output

• In \(m\) số nguyên: số lượng vòng sau mỗi lần hoán đổi.

Constraints

• \(1 \le n,m \le 2 \cdot 10^5\)
• \(1 \le a,b \le n\)

Example

Sample input

5 3
4 2 1 5 3
2 3
1 5
2 3

Sample output

2
3
4