Tường có một danh sách gồm \(n\) cây khác nhau trong một khu rừng, mỗi cây được đánh dấu bằng một số nguyên. Danh sách các cây có thể chứa nhiều cây giống nhau. Có \(q\) yêu cầu, mỗi yêu cầu sẽ cho biết một đoạn các cây liên tiếp trong khu rừng, và Tường cần trả lời cho mỗi yêu cầu xem trong đoạn đó có bao nhiêu loài cây khác nhau.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) (số lượng cây) và \(q\) (số lượng yêu cầu). \((1 \le n,q \le 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\) đại diện cho loài của từng cây trong khu rừng \((1 \le A_i \le 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) đại diện cho khoảng các cây từ vị trí \(l\) đến \(r\).

Dữ liệu ra

• Đối với mỗi yêu cầu, xuất ra số lượng loài cây khác nhau xuất hiện trong đoạn từ cây thứ \(l\) đến cây thứ \(r\).

Input 1

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

Output 1

2
3
2

Input 2

6 5
3 4 1 3 3 3
5 5
6 6
3 4
5 6
3 4

Output 2

1
1
2
1
2