Bé Loli đáng iu thích chơi đùa với trái tim lũ con trai mảng. Loli có mảng ~a~, chứa ~n~ phần tử nguyên dương, đánh số từ ~1~ đến ~n~.

Ngoài ra Loli còn có ~m~ câu hỏi liên quan tới mảng, mỗi câu hỏi có cấu trúc là một cặp số nguyên ~(l_j, r_j)~ ~(1\le l_j \le r_j \le n)~. Với mỗi câu hỏi ~(l_j, r_j)~, Loli sẽ bắt đứa em của mình phải đếm có bao nhiêu số ~x~ thỏa mãn, sao cho ~x~ xuất hiện đúng ~x~ lần trong các số từ ~a_{l_j}, a_{l_{j+1}}, \dots, a_{r_j}~.

Bạn hãy giúp đứa em của Loli trả lời toàn bộ câu hỏi của Loli, để nó còn được chơi Free Fire trong yên bình.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n, m\ (1\le n, m\le 10^5)~ - là kích cỡ của mảng ~a~ và số lượng câu hỏi.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1\le a_i \le 10^9)~.
• ~m~ dòng cuối cùng chứa ~m~ câu hỏi Loli đưa ra. Dòng thứ ~j~ là câu hỏi thứ ~j~ bao gồm cặp số nguyên ~(l_j, r_j)~ ~(1\le l_j \le r_j \le n)~.

Output

• In ra ~m~ dòng, mỗi dòng một số nguyên là đáp án của ~m~ câu hỏi. Dòng thứ ~j~ trả lời câu hỏi thứ ~j~.

Sample Input

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

Sample Output

3
1