Cho dãy \(a_1,a_2,\ldots,a_n\) gồm các số nguyên dương và \(m\) truy vấn \([l,r]\).

Với mỗi truy vấn, hãy đếm có bao nhiêu giá trị \(x\) xuất hiện đúng \(x\) lần trong đoạn \(a_l,\ldots,a_r\). Mỗi giá trị thỏa mãn được tính một lần.

Dữ liệu vào

• Dòng đầu chứa \(n\) và \(m\).
• Dòng tiếp theo chứa \(n\) số \(a_1,\ldots,a_n\).
• \(m\) dòng sau, mỗi dòng chứa hai chỉ số \(l,r\).

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng, theo thứ tự ban đầu.

Ràng buộc

• \(1\le n,m\le10^5\).
• \(1\le a_i\le10^9\).
• \(1\le l\le r\le n\).

Ví dụ

7 2
3 1 2 2 3 3 7
1 7
3 4

3
1

Nguồn

Codeforces 220B — Little Elephant and Array.