Mirko là một người đàn ông rất giản dị. Bạn của Mirko, Darko đã cho anh ta một mảng gồm ~N~ số nguyên dương và yêu cầu anh ta trả lời ~Q~ truy vấn liên quan đến mảng đã cho.

Mỗi truy vấn bao gồm hai số nguyên, thể hiện vị trí đầu và cuối của một đoạn trong mảng. Câu trả lời cho truy vấn ấy là số lượng các giá trị khác nhau xuất hiện đúng hai lần trong đoạn đã cho.

Input

Dòng đầu tiên chứa số nguyên ~N~ và ~Q~ ~(1 \leq N, Q \leq 500000)~.

Dòng thứ hai chứa mảng gồm ~N~ số nguyên dương nhỏ hơn ~10^9~.

~Q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq N)~.

Output

Hãy xuất ra ~Q~ dòng lần lượt là kết quả của ~Q~ truy vấn.

Sample Input 1

5 1
1 2 1 1 1
1 3

Sample Output 1

1

Giải thích test ví dụ 1: trong đoạn ~[1,3]~ chỉ có một số duy nhất (~1~) xuất hiện đúng hai lần.

Sample Input 2

5 2
1 1 1 1 1 
2 4 
2 3 

Sample Output 2

0
1

Sample Input 3

5 2
1 1 2 2 3
1 1
1 5

Sample Output 3

0
2

Subtask

• ~40\%~ số test có ~N, Q \le 5000~
• ~60\%~ số test còn lại không có điều kiện gì thêm