Dãy con không trùng lặp
Cho dãy $a_1, a_2, ..., a_N$. Có $Q$ truy vấn, mỗi truy vấn là hai số nguyên $L,R$. Hãy chia dãy con $a_L,a_{L+1},...,a_R$ thành các dãy con liên tiếp nhau sao cho không tồn tại hai phần tử có giá trị giống nhau trong một dãy con. Số lượng dãy con ít nhất có thể là bao nhiêu?
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương $N, Q \ (0 < N,Q \le 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (0\le a_i \le 10^5)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $L,R \ (1\le L \le R \le N)$.
Kết quả
- In trên $Q$ dòng, mỗi dòng là kết quả cho từng câu hỏi.
Ví dụ
Ví dụ 1
input
7 2
1 4 6 4 2 3 4
2 6
1 7
output
2
3
Comments