Vương quốc Graphlandia

Trong vương quốc Graphlandia, có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Mỗi thành phố sở hữu một chỉ số đặc biệt phản ánh nền văn minh của nó, ký hiệu là \(A[i]\). Tuy nhiên, ban đầu không có con đường nào kết nối các thành phố, khiến chúng bị cô lập.

Nhà vua của Graphlandia đã ra lệnh xây dựng hệ thống đường sá để kết nối các thành phố, nhưng ông rất quan tâm đến sự đa dạng giữa các nền văn minh. Do đó, sau mỗi lần xây dựng một con đường mới giữa hai thành phố, ông yêu cầu một báo cáo về số cặp thành phố thuộc cùng khu vực liên thông nhưng có chỉ số nền văn minh khác nhau.

Input

--- Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N \leq 3 \times 10^5, 1 \leq Q \leq 3 \times 10^5)\) --- số thành phố và số truy vấn.

--- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((1 \leq A_i \leq N)\), mỗi số mô tả chỉ số của thành phố thứ \(i\).

--- \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N, u \neq v)\), biểu thị việc xây dựng một con đường giữa \(u\) và \(v\).

Output

--- Gồm \(Q\) dòng, mỗi dòng in ra một số nguyên --- số lượng cặp thành phố có chỉ số khác nhau trong cùng khu vực liên thông sau khi truy vấn tương ứng được thực hiện.

Example

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

1
2
5
8