Cho một mảng gồm ~N~ số tự nhiên. Bạn là hãy trả lời ~Q~ câu hỏi có dạng: Đếm xem trong khoảng từ vị trí ~L~ đến ~R~ của mảng số lượng các phần tử có giá trị khác nhau xuất hiện chính xác hai lần trong khoảng đã cho.

Input

Dòng đầu tiên ghi hai số nguyên ~N, Q~ thỏa ~1 \le N, Q \le 5.10^5~.

Dòng thứ hai chứa ~N~ số tự nhiên ~a_i~ thỏa ~1 \le a_i \le 10^9~.

~Q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~L, R~ thỏa ~1 \le L \le R \le N~.

Output

In kết quả cần tìm cho mỗi truy vấn, mỗi kết quả in trên một dòng.

Samples

Sample Input 1

5 2
1 1 2 2 3
1 1
1 5

Sample Output 1

0
2