Cho một dãy ~A~ gồm ~n~ phần tử và ~q~ truy vấn, mỗi truy vấn cho 2 số ~[l, r]~.

Hãy tính số lượng giá trị xuất hiện đúng 2 lần trong đoạn con từ ~l~ đến ~r~.

Input

• Dòng đầu tiên gồm 2 số ~n~ và ~q~ (~n \le 5 \times 10^5~, ~q \le 5 \times 10^5~).
• Dòng thứ 2 chứa ~n~ số nguyên dương bé hơn ~10^9~ là các phần tử của mảng ~A~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số ~l, r~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Sample Input 1

5 2
1 1 2 2 3 
1 1 
1 5

Sample Output 1

0
2