Thành phần liên thông

Time limit: 1.0s , Memory limit: 256M , Points: 0 (partial)

Bạn được cho một dãy hoán vị $P$ ~P~ độ dài $N$ ~N~ và một đồ thị $G$ ~G~ gồm $N$ ~N~ đỉnh. Giữa hai đỉnh $u$ ~u~ và $v$ ~v~ của đồ thị có cạnh nối hai chiều khi và chỉ khi $u < v$ ~u < v~ và $P_u < P_v$ ~P_u < P_v~.

Bạn cần xử lý $Q$ ~Q~ truy vấn, mỗi truy vấn bạn được cho cặp số nguyên $(i,j)$ ~(i,j)~ $(1 \le i,j \le N$ ~(1 \le i,j \le N~, $i \neq j)$ ~i \neq j)~, yêu cầu thực hiện các bước sau theo thứ tự:

Hoán đổi giá trị của $P_i$ ~P_i~ và $P_j$ ~P_j~.
Cập nhật lại danh sách cạnh của đồ thị dựa trên dãy hoán vị $P$ ~P~ đã thay đổi (thêm hoặc xóa cạnh).
Đếm số thành phần liên thông của đồ thị.

Lưu ý rằng dãy hoán vị $P$ ~P~ đã thay đổi sẽ được dùng cho truy vấn tiếp theo.

Input

Dòng đầu tiên chứa số nguyên $N$ ~N~ $(2 \le N \le 10^5)$ ~(2 \le N \le 10^5)~.
Dòng thứ hai chứa $N$ ~N~ số nguyên của dãy hoán vị $P$ ~P~ $(1 \le P_i \le N)$ ~(1 \le P_i \le N)~.
Dòng tiếp theo chứa số nguyên $Q$ ~Q~ $(1 \le Q \le 10^5)$ ~(1 \le Q \le 10^5)~.
$Q$ ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ ~i~ và $j$ ~j~ mô tả truy vấn.
Dữ liệu đảm bảo dãy $P$ ~P~ là một dãy hoán vị hợp lệ.

Output

Với mỗi truy vấn, in ra số thành phần liên thông trên một dòng.

Examples

Sample Input

Sample Output

3
2

Scoring

Subtask $1$ ~1~ với $30\%$ ~30\%~ số điểm: $N,Q \le 200$ ~N,Q \le 200~
Subtask $2$ ~2~ với $30\%$ ~30\%~ số điểm: $N,Q \le 5000$ ~N,Q \le 5000~
Subtask $3$ ~3~ với $40\%$ ~40\%~ số điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, đồ thị ban đầu có một cạnh nối giữa hai đỉnh $2-3$ ~2-3~.

Ở truy vấn thứ nhất, dãy hoán vị $P=\{3,2,1\}$ ~P=\{3,2,1\}~ và đồ thị không có cạnh nối. Có tổng cộng $3$ ~3~ thành phần liên thông.

Ở truy vấn thứ hai, dãy hoán vị $P=\{2,3,1\}$ ~P=\{2,3,1\}~ và đồ thị có một cạnh nối giữa hai đỉnh $1-2$ ~1-2~. Có tổng cộng $2$ ~2~ thành phần liên thông.