An sở hữu một chuỗi hạt tuyệt đẹp gồm \(N\) viên ngọc trai xếp cạnh nhau và được đánh số từ \(1\) đến \(N\). Mỗi viên ngọc trai được nhuộm một màu sắc đại diện bởi một số nguyên dương.

An muốn thực hiện các truy vấn thống kê thẩm mỹ cho chuỗi hạt của mình. Cụ thể, có \(Q\) truy vấn thuộc dạng:

• L R: Đếm xem trong đoạn các viên ngọc từ vị trí \(L\) đến vị trí \(R\) trên chuỗi hạt có bao nhiêu màu sắc khác nhau.

Hãy viết chương trình xử lý nhanh các yêu cầu của An.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) biểu thị màu sắc của các viên ngọc trên chuỗi (\(1 \le a_i \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) mô tả một truy vấn (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng màu sắc khác nhau tìm được trên một dòng riêng biệt.

Ví dụ

Input:

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

Output:

2
2
3