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 \leq i, j \leq 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 \leq N \leq 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 \leq P_{i} \leq N)$ .
Dòng tiếp theo chứa số nguyên $Q$ $Q$ $(1 \le Q \le 10^5)$ $(1 \leq Q \leq 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

Copy

Sample Output

Copy

3
2

Scoring

Subtask $1$ $1$ với $30\%$ $30 %$ số điểm: $N,Q \le 200$ $N, Q \leq 200$
Subtask $2$ $2$ với $30\%$ $30 %$ số điểm: $N,Q \le 5000$ $N, Q \leq 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.