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.IOException; 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*; 


public class Main 
{ 	

    public final static int OO = Integer.MAX_VALUE;
    private static Reader r; 	


	public static void main(String[] args)throws Exception 	 	
	{ 	 		
		r = new Reader(); 	 

		r.readLine();
		int n = r.readInt(0);
		int m = r.readInt(1);

		r.readLine();
		List<Integer> arr = r.getIntegersList();

		SquareRootDecomposition srd = new SquareRootDecomposition(n);
		srd.setQCount(m);

		for (int i=0;i < m;++i)
		{
			r.readLine();
			srd.addQuery(r.readInt(0) - 1, r.readInt(1) - 1);
		}

		StringBuilder res = new StringBuilder();
		for (int v:srd.getResult(arr))
			res.append(v).append("\n");

		System.out.print(res.toString().trim());
		r.close(); 	
	}

	private static void dfs(int v, boolean []flag, List<List<Integer>> graph)
	{
		flag[v] = true;

		for (int u:graph.get(v))
		{
			if (!flag[u])
			{
				dfs(u, flag, graph);
			}
		}

	}

	private static int bfs(List<List<Integer>> graph, int v)
	{
		Queue<Integer> queue = new LinkedList<>();

		queue.add(v);

		boolean flag[] = new boolean[graph.size()];

		while (!queue.isEmpty())
		{
			v = queue.poll();

			flag[v] = true;

			for (int u:graph.get(v))
				if (!flag[u])
				{
					queue.add(u);
				}
		}
		return v;
	}

	private static int longestPathInTree(List<List<Integer>> graph, int v)
	{
		v = bfs(graph, v);

		Queue<Pair> level = new LinkedList<>();

		boolean []isV = new boolean[graph.size()];

		Pair p = new Pair(v, 0);
		level.add(p);

		while (!level.isEmpty())
		{
			p = level.poll();
			isV[p.f] = true;
			v = p.f;


			for (int u:graph.get(v))
				if (!isV[u])
				{
					level.add(new Pair(u, p.s + 1));
				}
		}


		return p.s;
	}

	public static int lower_bound(List<Integer> arr, int lo, int hi, int key, int arrSize)
	{
		if (hi == arrSize)
			--hi;

		int len = hi + 1;
		int mid = (lo + hi) / 2;

		while (true)
		{
			if (arr.get(mid) >= key)
			{
				hi = mid - 1;
				if (hi < lo)
					return mid;
			}
			else
			{
				lo = mid + 1;
				if (hi < lo)
					return mid < len - 1 ?mid + 1: -1;
			}
			mid = (lo + hi) / 2;
		}
	}

	public static int lower_bound(List<Integer> arr, int key)
	{

		int len = arr.size();
		int lo = 0;
		int hi = len - 1;
		int mid = (lo + hi) / 2;

		while (true)
		{
			if (arr.get(mid) >= key)
			{
				hi = mid - 1;
				if (hi < lo)
					return mid;
			}
			else
			{
				lo = mid + 1;
				if (hi < lo)
					return mid < len - 1 ?mid + 1: 
					/*
					 custom code here -1 default
						 */len; 
			}
			mid = (lo + hi) / 2;
		}
	}

	public static int upper_bound(List<Integer> arr, int lo, int hi, int key, int arrSize)
	{

		if (hi == arrSize)
			--hi;

		if (arr == null || arr.isEmpty())
			return -1;

		int len = hi + 1;
		int mid = (lo + hi) / 2;

		while (true)
		{
			if (arr.get(mid) <= key)
			{
				lo = mid + 1;
				if (hi < lo) 
					return mid < len - 1 ?mid + 1: -1; 
			}
			else
			{
				hi = mid - 1;
				if (hi < lo)
					return mid;
			}
			mid = (lo + hi) / 2;
		}

	}

	public static int upper_bound(List<Integer> arr, int key)
	{

		int len = arr.size();
		int hi = len - 1;
		int lo = 0;
		int mid = (lo + hi) / 2;

		while (true)
		{
			if (arr.get(mid) <= key)
			{
				lo = mid + 1;
				if (hi < lo) 
					return mid < len - 1 ?mid + 1: 
					/*
					 custom code here -1 default
						 */len; 
			}
			else
			{
				hi = mid - 1;
				if (hi < lo)
					return mid;
			}
			mid = (lo + hi) / 2;
		}

	}

} 

class Query implements Comparable<Query>
{
	int l,r,blockSize,queryN;

	public Query(int l, int r, int blockSize, int queryN)
	{
		this.l = l;
		this.r = r;
		this.blockSize = blockSize;
		this.queryN = queryN;
	}

	@Override
	public int compareTo(Query o)
	{
		if (l / blockSize != o.l / blockSize)
			return l / blockSize - o.l / blockSize;
		return r - o.r;
	}

	@Override
	public String toString()
	{
		return l + 1 + " " + (r + 1) + " " + queryN + " " + blockSize;
	}


}

class SquareRootDecomposition
{
	private int n;

	private Query queries[];
	private int qCount;
	private int blockSize;
	private int idx = 0;

	SquareRootDecomposition(int n)
	{
		this.n = n;
	}

	void setQCount(int qCount)
	{
		this.qCount = qCount;
		queries = new Query[qCount];
		blockSize = (int)Math.sqrt(n);
	}

	void addQuery(int l, int r)
	{
		queries[idx] = new Query(l, r, blockSize, idx);
		++idx;
	}

	int[] getResult(List<Integer> arr)
	{
		int res[] = new int[qCount];
		
		Arrays.sort(queries);
		
		int freq[] = new int[n+1];
		
		int l=1,r=0,ans=0;
		for (int i=0;i<qCount;++i)
		{
			Query q = queries[i];

			
			while (r > q.r)
			{
				int v = arr.get(r);
				if(v<=n)
				{
					ans += --freq[v]==v?1:freq[v]==v-1?-1:0;
				}
				
				--r;
			}

			while (r < q.r)
			{
				++r;
				int v = arr.get(r);
				if(v<=n)
				{
					ans += ++freq[v]==v?1:freq[v]==v+1?-1:0;
				}
				
			}

			while (l < q.l)
			{
				int v = arr.get(l);
				if(v<=n)
				{
					ans += --freq[v]==v?1:freq[v]==v-1?-1:0;
				}
				++l;
			}

			while (l > q.l)
			{
				
				--l;
				int v = arr.get(l);
				if(v<=n)
				{
					ans += ++freq[v]==v?1:freq[v]==v+1?-1:0;
				}
			}
			
			res[q.queryN] = ans;
		}

		return res;
	}
}

class SegmentTree
{
	// limit to array size
	private final static int N = 1_000_00;

	// array size
	int n;

	int t[];
	int arr[];

	SegmentTree(int arr[], int n)
	{
		this.n = n;
		t = new int[2 * n];
		this.arr = arr;
	}

	void build()
	{
		for (int i=0;i < n;++i)
			t[n + i] = arr[i];

		for (int i=n - 1;i > 0;--i)
			t[i] = t[i << 1] + t[i << 1 | 1];

	}

	void modify(int p, int val)
	{
		for (t[p + n] = val;p > 1;p >>= 1)
		{
			t[p >> 1] = t[p] + t[p ^ 1];
		}
	}

	int query(int l, int r) 
	{ 
		int res = 0; 
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) 
		{ 
			if ((l & 1) != 0) 
				res += t[l++]; 
			if ((r & 1) != 0) 
				res += t[--r]; 
		} 
		return res; 
	}

}


class Pair implements Comparable<Pair>
{ 	
	int f,s; 	
	public Pair() 	
	{} 
	public Pair(int f, int s) 	
	{ 	
		this.f = f; 	
		this.s = s; 	
	} 

	@Override 	
	public String toString() 
	{ 		
		return f + " " + s; 	
	} 	

	@Override 	
	public int compareTo(Pair o) 	
	{ 		
		if (f == o.f) 			
			return s - o.s; 		
		return f - o.f; 	
	} 
}

class Reader
{ 	
	private BufferedReader reader; 
	private String line[]; 	

	public Reader() 	
	{ 		
		reader = new BufferedReader(new InputStreamReader(System.in)); 	
	} 	

	public String[] getLine() 	
	{ 		
		return line; 	
	} 	

	public void readLine() 	throws IOException 
	{ 		
		line = reader.readLine().split(" "); 	
	} 	

	public List<Integer> getIntegersList()
	{
		List<Integer> res = new ArrayList<>();
		for (String str:line)
			res.add(Integer.parseInt(str));
		return res;

	}

	public int readInt(int pos)throws IOException 	
	{ 		
		return Integer.parseInt(line[pos]); 	
	} 	

	public double readDouble(int pos)throws IOException 	
	{ 		
		return Double.parseDouble(line[pos]); 	
	} 	

	public long readLong(int pos)throws IOException 
	{ 		
		return Long.parseLong(line[pos]); 
	} 	

	public String readString(int pos)throws IOException 	
	{ 		
		return line[pos]; 	
	} 	

	public void close()throws IOException 
	{ 		
		reader.close(); 	
	}

}

class Vertix implements Comparable<Vertix>
{
	int to,w;

	public Vertix(int to, int w)
	{
		this.to = to;
		this.w = w;
	}

	@Override
	public int compareTo(Vertix p1)
	{
		return w - p1.w;
	}

}

class Dijkstra
{
	boolean isDirected;
	int n;
	List<List<Vertix>> adjList;
	int distance[];
	int parent[];
	boolean visited[];

	Dijkstra(int n, boolean isDirected)
	{
		this.isDirected = isDirected;
		this.n = n;
		adjList = new ArrayList<>();
		distance = new int[n + 1];
		parent = new int[n + 1];
		visited = new boolean[n + 1];

		for (int i=0;i <= n;++i)
		{
			adjList.add(new ArrayList<Vertix>());
			distance[i] = Main.OO;
			parent[i] = -1;

		}

	}

	void addEdge(int fr, int to, int w)
	{
		adjList.get(fr).add(new Vertix(to, w));

		if (!isDirected)
			adjList.get(to).add(new Vertix(fr, w));

	}

	Stack<Integer> getShortestPath(int src, int dis)
	{
		PriorityQueue<Vertix> queue = new PriorityQueue<>();

		distance[src] = 0;
		queue.add(new Vertix(src, 0));

		while (!queue.isEmpty())
		{
			Vertix v = queue.poll();
			int to = v.to;

			if (visited[to])
				continue;

			if (to == dis)
			{

				Stack<Integer> res = new Stack<>();

				res.add(dis);

				for (int c=parent[dis];c != src;c = parent[c])
					res.add(c);

				res.add(src);

				return res;
			}

			visited[to] = true;

			for (Vertix vv:adjList.get(to))
			{
				if (!visited[vv.to] && distance[vv.to] > distance[to] + vv.w)
				{
					distance[vv.to] = distance[to] + vv.w;
					parent[vv.to] = to;
					queue.add(new Vertix(vv.to, distance[vv.to]));
				}
			}
		}
		return null;

	}

}



