The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai. 

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.

Help the Little Elephant to count the answers to all queries.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

Output

In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.

Examples

Input

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


Output

3
1
							import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
											public class Solution implements Runnable
											{
												static final long MAX = 1000000007L;
												static class InputReader
												{
													private InputStream stream;
													private byte[] buf = new byte[1024];
													private int curChar;
													private int numChars;
													private SpaceCharFilter filter;
													private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
											 
													public InputReader(InputStream stream)
													{
														this.stream = stream;
													}
													
													public int read()
													{
														if (numChars==-1) 
															throw new InputMismatchException();
														
														if (curChar >= numChars)
														{
															curChar = 0;
															try 
															{
																numChars = stream.read(buf);
															}
															catch (IOException e)
															{
																throw new InputMismatchException();
															}
															
															if(numChars <= 0)				
																return -1;
														}
														return buf[curChar++];
													}
												 
													public String nextLine()
													{
														String str = "";
											            try
											            {
											                str = br.readLine();
											            }
											            catch (IOException e)
											            {
											                e.printStackTrace();
											            }
											            return str;
													}
													public int nextInt()
													{
														int c = read();
														
														while(isSpaceChar(c)) 
															c = read();
														
														int sgn = 1;
														
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														
														int res = 0;
														do 
														{
															if(c<'0'||c>'9') 
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														while (!isSpaceChar(c)); 
														
														return res * sgn;
													}
													
													public long nextLong() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														int sgn = 1;
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														long res = 0;
														
														do 
														{
															if (c < '0' || c > '9')
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														while (!isSpaceChar(c));
															return res * sgn;
													}
													
													public double nextDouble() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														int sgn = 1;
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														double res = 0;
														while (!isSpaceChar(c) && c != '.') 
														{
															if (c == 'e' || c == 'E')
																return res * Math.pow(10, nextInt());
															if (c < '0' || c > '9')
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														if (c == '.') 
														{
															c = read();
															double m = 1;
															while (!isSpaceChar(c)) 
															{
																if (c == 'e' || c == 'E')
																	return res * Math.pow(10, nextInt());
																if (c < '0' || c > '9')
																	throw new InputMismatchException();
																m /= 10;
																res += (c - '0') * m;
																c = read();
															}
														}
														return res * sgn;
													}
													
													public String readString() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														StringBuilder res = new StringBuilder();
														do 
														{
															res.appendCodePoint(c);
															c = read();
														} 
														while (!isSpaceChar(c));
														
														return res.toString();
													}
												 
													public boolean isSpaceChar(int c) 
													{
														if (filter != null)
															return filter.isSpaceChar(c);
														return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
													}
												 
													public String next() 
													{
														return readString();
													}
													
													public interface SpaceCharFilter 
													{
														public boolean isSpaceChar(int ch);
													}
												}
											 	
												public static void main(String args[]) throws Exception
												{
													new Thread(null, new Solution(),"Solution",1<<26).start();
												}
													
												
												public void run() 
												{
													InputReader sc= new InputReader(System.in);
													PrintWriter w= new PrintWriter(System.out);
													int n = sc.nextInt();
													int m = sc.nextInt();
													int[] arr=  new int[n];
													for(int i = 0;i < n;i++) {
														arr[i] = sc.nextInt();
													}
													blksize = (int)Math.sqrt(n);
													int[] ans = new int[m];
													Pair[] p = new Pair[m];
													for(int i = 0;i < m;i++) {
														int l = sc.nextInt()-1;
														int r = sc.nextInt()-1;
														p[i] = new Pair(l,r,i);
													}
													Arrays.sort(p);
													int st = 0;
													int en = 0;
													int[] bri = new int[100005];
													Arrays.fill(bri,0);
													int count = 0;
													for(int i = 0;i < p.length;i++) {
														while(st < p[i].a) {
															if(arr[st] > 100000) {
																st++;
																continue;
															}
															bri[arr[st]]--;
															if(bri[arr[st]]== arr[st]) {
																count++;
															}
															if(bri[arr[st]] == arr[st] - 1) {
																count--;
															}
															st++;
														}
														while(st > p[i].a) {
															
															if(arr[st-1] > 100000) {
																st--;
																continue;
															}
															bri[arr[st-1]]++;
															if(bri[arr[st-1]]== arr[st-1]) {
																count++;
															}
															if(bri[arr[st-1]] == arr[st-1] + 1) {
																count--;
															}
															st--;
														}
														while(en <= p[i].b) {
															
															if(arr[en] > 100000) {
																en++;
																continue;
															}
															bri[arr[en]]++;
															if(bri[arr[en]]== arr[en]) {
																count++;
															}
															if(bri[arr[en]] == arr[en] + 1) {
																count--;
															}
															en++;
														}
														while(en > p[i].b + 1) {
															if(arr[en-1] > 100000) {
																en--;
																continue;
															}
															bri[arr[en-1]]--;
															if(bri[arr[en-1]]== arr[en-1]) {
																count++;
															}
															if(bri[arr[en-1]] == arr[en-1] - 1) {
																count--;
															}
															en--;
														}
														
														ans[p[i].c] = count;
													}
													for(int i = 0;i < ans.length;i++) {
														w.println(ans[i]);
													}
													w.close(); 
												}
												static int blksize = 1;
												static class Pair implements Comparable<Pair>{
													int a;
													int b;
													int c;
													Pair(int a,int b,int c){
														this.a  =a;
														this.b = b;
														this.c = c;
													}
													Pair(){}	
													public boolean equals(Object o)
													{
														Pair p = (Pair)o;
														return true;
													}
													
													public int compareTo(Pair p){
														if(this.a/blksize == p.a/blksize) {
															return Integer.compare(this.b,p.b);
														}
														return Integer.compare(this.a/blksize,p.a/blksize);
													}
													public int hashCode(){
														
													    return 1;
													}
												}
								}