Trong phòng tin 2, có hai cậu bé là Gấu và Khoa. Gấu thì nổi tiếng dễ thương và khôn ngoan, nhưng Khoa thì tai tiếng về sự quậy phá của mình. Vào một ngày xấu trời, Gấu vì đã chịu sự quậy phá quá mức từ Tuấn Khoa mà thốt lên rằng: "một thằng Tuấn Khoa đã chịu không nổi, đừng thêm thằng nào nữa". Thật vậy, trong năm 2709, người ta đã phát minh ra máy nhân bản con người, và nhân bản các thành viên phòng tin 2 lên thành ~N~ người đánh số từ ~1~ đến ~N~, người thứ ~i~ có tính cách là ~A_i~. Gấu có ~Q~ câu hỏi, câu hỏi thứ ~j~ bảo rằng trong đoạn ~[L_j, R_j]~ có bao nhiêu loại người xấu. Một loại người gọi là xấu nếu tồn tại đúng hai người có tính cách giống nhau. Nếu có nhiều hơn hai người, vì đây là những người xấu nên họ sẽ tự quánh nhau và biến mất. Do đó, với mỗi đoạn ~[L_j, R_j]~, hãy đếm số tính cách xuất hiện đúng hai lần trong đó.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \leq N, Q \leq 5*10^5)~.
• Dòng hai chứa ~N~ số nguyên ~A_i~ ~(1 \leq A_i \leq 10^9)~.
• ~Q~ dòng sau, dòng thứ ~j~ ~(1 \leq j \leq Q)~ chứa hai số nguyên ~[L_j, R_j]~ mô tả truy vấn ~(1 \leq L_j \leq R_j \leq N)~.

Dữ liệu ra

Gồm ~Q~ dòng là đáp án cho ~Q~ truy vấn.

Ví dụ

Đầu vào

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

Đầu ra

1
2
1