Tý có một dãy số \(a_1, a_2, \ldots, a_N\). Tý đưa ra \(Q\) câu hỏi, mỗi câu hỏi gồm hai số \(L, R\), và muốn biết trong đoạn \([L,R]\) có bao nhiêu giá trị phân biệt.

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

• Dòng đầu: hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2000\)).
• Dòng hai: \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^5\)).
• \(Q\) dòng tiếp: mỗi dòng \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng giá trị phân biệt.

Ví dụ

Input:

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

Output:

2
3
4

Ràng buộc