Có $n$ phần tử đánh số từ $1 \sim n$ và $q$ thao tác.

1. Ban đầu cho mảng $a$ : $a_i$ cho biết phần tử đánh số $i$ thuộc cùng một tập hợp với phần tử $a_i$ ; nếu $a_i=0$ , phần tử $i$ tự tạo thành một tập hợp riêng.

2. Mỗi thao tác cho một đoạn $[l,r]$ , hợp nhất thành một tập hợp tất cả các tập hợp chứa các phần tử trong đoạn.

3. Sau khi hoàn thành tất cả thao tác, in ra số tập hợp cuối cùng.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $n$ (số phần tử) và $q$ (số thao tác)

Dòng thứ hai: mảng $a$ có độ dài $n$ ( $a_1 \sim a_n$ )

Tiếp theo là $q$ dòng: mỗi dòng hai số nguyên $l, r$ , biểu thị đoạn thao tác

Dữ liệu ra

In ra một số nguyên, biểu thị số tập hợp cuối cùng

Ví dụ

Input

Không có

Output

Không có

Ghi chú

Tóm tắt gợi ý

1. Cốt lõi là DSU (Union-Find) + tối ưu gộp đoạn, để xử lý lượng dữ liệu lớn cỡ $10^6$ .

2. Khi gộp một đoạn liên tiếp chỉ cần gộp các phần tử kề nhau, không cần duyệt toàn bộ đoạn.

3. Số tập hợp cuối cùng = số nút gốc trong DSU.

Phạm vi dữ liệu

• $2 \leq n \leq 10^6$

• $1 \leq q \leq 10^6$

• $1 \leq a_i < n$

• $1 \leq l < r \leq n$