Mô tả bài toán: Số lượng giá trị khác nhau trong khoảng

Bạn được cung cấp một mảng gồm ~n~ số nguyên và ~q~ truy vấn. Với mỗi truy vấn, bạn cần trả lời có bao nhiêu giá trị khác nhau xuất hiện trong đoạn ~[a, b]~ của mảng.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: kích thước mảng và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~: các giá trị trong mảng.
• Sau đó có ~q~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~, mô tả một truy vấn:
  • ~a~: chỉ số bắt đầu (1-based index).
  • ~b~: chỉ số kết thúc (1-based index).

Output:

• Với mỗi truy vấn, in ra số lượng giá trị khác nhau xuất hiện trong đoạn ~[a, b]~.

Ràng buộc:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq x_i \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ví dụ:

Input:

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

Output:

2
3
3

Giải thích:

1. Truy vấn 1 3: Các phần tử trong đoạn ~[1, 3]~ là [3, 2, 3], có 2 giá trị khác nhau (3, 2).
2. Truy vấn 2 4: Các phần tử trong đoạn ~[2, 4]~ là [2, 3, 1], có 3 giá trị khác nhau (2, 3, 1).
3. Truy vấn 1 5: Các phần tử trong đoạn ~[1, 5]~ là [3, 2, 3, 1, 2], có 3 giá trị khác nhau (3, 2, 1).