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.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.PrintWriter;
import java.io.OutputStream;
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Alex
 */
public class Main{
	public static void main(String[] args){
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
	static class TaskD{
		public void solve(int testNumber, InputReader in, OutputWriter out){
			int n = in.ri(), m = in.ri();
			int[] a = IOUtils.readIntArray(in, n);
			HashMap<Integer, Integer> count = new HashMap<>();
			for(int val : a) incr(count, val);
			IntPair[] queries = new IntPair[m];
			for(int i = 0; i < m; i++) queries[i] = new IntPair(in.ri() - 1, in.ri() - 1);
			int[] res = new int[m];
			for(int val : count.keySet()) {
				if(count.get(val) >= val){
					int[] temp = new int[n + 1];
					for(int i = 1; i <= n; i++) temp[i] = temp[i - 1] + (a[i - 1] == val ? 1 : 0);
					for(int i = 0; i < m; i++) {
						IntPair query = queries[i];
						if(temp[query.second + 1] - temp[query.first] == val) res[i]++;
					}
				}
			}
			for(int val : res) out.printLine(val);
		}
		void incr(HashMap<Integer, Integer> hm, int val){
			if(hm.containsKey(val)) hm.put(val, hm.get(val) + 1);
			else hm.put(val, 1);
		}
	}
	static class OutputWriter{
		private final PrintWriter writer;
		public OutputWriter(OutputStream outputStream){
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}
		public OutputWriter(Writer writer){
			this.writer = new PrintWriter(writer);
		}
		public void close(){
			writer.close();
		}
		public void printLine(int i){
			writer.println(i);
		}
	}
	static class IntPair implements Comparable<IntPair>{
		public int first;
		public int second;
		public IntPair(int first, int second){
			this.first = first;
			this.second = second;
		}
		public String toString(){
			return "(" + first + "," + second + ")";
		}
		public boolean equals(Object o){
			if(this == o) return true;
			if(o == null || getClass() != o.getClass()) return false;
			IntPair intPair = (IntPair) o;
			return first == intPair.first && second == intPair.second;
		}
		public int hashCode(){
			int result = first;
			result = 31 * result + second;
			return result;
		}
		public int compareTo(IntPair o){
			if(first < o.first)
				return -1;
			if(first > o.first)
				return 1;
			if(second < o.second)
				return -1;
			if(second > o.second)
				return 1;
			return 0;
		}
	}
	static class IOUtils{
		public static int[] readIntArray(InputReader in, int size){
			int[] array = new int[size];
			for(int i = 0; i < size; i++)
				array[i] = in.readInt();
			return array;
		}
	}
	static class InputReader{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		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 int ri(){
			return readInt();
		}
		public int readInt(){
			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 boolean isSpaceChar(int c){
			if(filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}
		public static boolean isWhitespace(int c){
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public interface SpaceCharFilter{
			public boolean isSpaceChar(int ch);
		}
	}
}

