Trong một hệ thống giám sát dữ liệu, mỗi phần tử ~A[i]~ biểu thị mã định danh của một sự kiện được ghi lại theo thời gian.

Hệ thống cần thường xuyên xác định xem trong một khoảng thời gian nhất định có bao nhiêu loại sự kiện khác nhau đã xảy ra.

Yêu cầu: Cho mảng ~A~ gồm ~N~ phần tử và ~Q~ truy vấn. Mỗi truy vấn gồm hai số ~L,R~. Với mỗi truy vấn, hãy in ra số lượng giá trị khác nhau trong đoạn ~A[L..R]~.

Input

• Dòng ~1~: hai số nguyên ~N,Q~.

• Dòng ~2~: ~N~ số nguyên ~A_1,A_2,\dots,A_n~.

• ~Q~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~L,R~.

Output

~Q~ dòng, mỗi dòng là kết quả truy vấn tương ứng.

Scoring

Sample Input 1

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

Sample Output 1

2
3
3