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.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.ObjectInputStream.GetField;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;




	public class Q1 {
		
		static long MOD = 1000000007;
		static boolean b[], b1[], check;
		static ArrayList<Integer>[] amp, pa;
		static ArrayList<Pair>[] amp1;
		static ArrayList<Pair>[][] damp;
		static int left[],s[],right[],end[],sum[],dist[],cnt[],start[],color[],parent[],prime[],size[];
		static long ans = 0,k;
		static int p = 0;
		static FasterScanner sc = new FasterScanner(System.in);
		static Queue<Integer> queue = new LinkedList<>();
		static PriorityQueue<Integer> pq;
		static BufferedWriter log;
		static HashSet<Integer>[] hs;
		static HashMap<String,Integer> hm;
		static HashMap<Pair,Integer> hmp;
		static Stack<Integer> st;
		static boolean boo[][];
		static Pair prr[];
		static long parent1[],parent2[],size1[],size2[],arr1[],SUM[],MAX[];
		static int arr[];
		public static void main(String[] args) throws Exception {
	    	/*new Thread(null, new Runnable() {
				public void run() {
					try {

				} catch (Exception e) {
						System.out.println(e);
					}
				}
			}, "1", 1 << 26).start();*/
			soln();
		}
		static long dp[][];
		static int N,K,T;
		static int time = 0;
		static int cost[][];
		static boolean b11[];
		static HashMap<Integer,Integer> h = new HashMap<>();
		static long ans1;
		static long ans2;
		static int BLOCK = 350;
		public static void soln() throws IOException {
			//FasterScanner in = new FasterScanner(new FileInputStream("C:\\Users\\Admin\\Desktop\\QCL.txt"));
			//PrintWriter out = new PrintWriter("C:\\Users\\Admin\\Desktop\\A1.txt");
			log = new BufferedWriter(new OutputStreamWriter(System.out));
			int n = sc.nextInt(), m = sc.nextInt();
			int arr[] = sc.nextIntArray(n);
			Pair prr[] = new Pair[m];	
			int brr[] = arr.clone();
			Arrays.sort(brr);
			for(int i = 0; i< n ;i++){
				h.put(brr[i], i);
			}
			for(int i = 0; i< m; i++){
				prr[i] = new Pair(sc.nextInt()-1,sc.nextInt()-1,i);
			}
			Arrays.sort(prr);
			cnt = new int[n];
			b = new boolean[n];
			int ans[] = new int[m];
			int l = 0, r = 0;
			p  =0;
			for(int i = 0; i< m;i++){
				while(l<prr[i].u){
					if(b[l])
					del(arr[l]);
					b[l]  =false;
					l++;
				}
				while(l>=prr[i].u){
					if(!b[l])
					add(arr[l]);
					b[l]  = true;
					if(l == prr[i].u) break;
					l--;
				}
				while(r<=prr[i].v){
					if(r>l && !b[r]){ add(arr[r]);
					b[r] = true;
					}
					if(r == prr[i].v) break;
					r++;
				}
				while(r>prr[i].v){
					if(b[r])
					del(arr[r]);
					b[r] =false;
					r--;
				}
				ans[prr[i].z] = p;
			}
			for(int i : ans) log.write(i+"\n");
			log.close();
			//out.close();
		}
		static void add(int x){
			int d = h.get(x);
			if(cnt[d]==x){
				p--;
				cnt[d]++;
				return;
			}
			cnt[d]++;
			if(cnt[d]==x) p++;
			return;
		}
		static void del(int x){
			int d = h.get(x);
			if(cnt[d]==x){
				p--;
				cnt[d]--;
				return;
			}
			cnt[d]--;
			if(cnt[d]==x) p++;
			return;
		}
		static void bfs(int x){
			
		}
		static void dfs(int x){
			b[x] = true;
			if(amp[x].size()%2==1) p++;
			for(int p:amp[x]){
				if(!b[p]){
					dfs(p);
				}
			}
		}
		public static void seive(int n){
			b = new boolean[(n+1)];
			Arrays.fill(b, true);
			b[1] = false;
			for(int i = 2;i*i<=n;i++){
				if(b[i]){
					for(int p = 2*i;p<=n;p+=i){
						b[p] = false;
					}
				}
			}
			/*for(int i = 2;i<=n;i++){
				if(b[i]) prime[i] = i;
			}*/
		}
		
		static class Graph{
			int vertex;
			int weight;
			Graph(int v, int w){
				vertex = v;
				weight = w;
			}
		}
		static class Pair implements Comparable<Pair> {
			int u;
			int v;
			int z;
			public Pair(){
				u = 0;
				v = 0;
			}
			public Pair(int u, int v, int z) {
				this.u = u;
				this.v = v;
				this.z = z;
			}
			public int hashCode() {
				int hu = (int) (u ^ (u >>> 32));
				int hv = (int) (v ^ (v >>> 32));
				return 31*hu + hv;
			}
	 
			public boolean equals(Object o) {
				Pair other = (Pair) o;
				return (u == other.u && v == other.v);
			}
	 
			public int compareTo(Pair other) {
				return Long.compare(u/BLOCK, other.u/BLOCK) != 0 ? (Long.compare(u/BLOCK, other.u/BLOCK)) : (Long.compare(other.v,v));
			}
			
			public String toString() {
				return "[u=" + u + ", v=" + v + "]";
			}
		}
		
		public static void buildGraph(int n){
			for(int i =0;i<n;i++){
				int x = sc.nextInt()-1, y = sc.nextInt()-1;
				amp[x].add(y);
				amp[y].add(x);
			}
		}
		
		
		public static int getParent(long x){
			while(parent[(int) x]!=x){
				parent[ (int) x] = parent[(int) parent[ (int) x]];
				x = parent[ (int) x];
			}
			return (int) x;
		}
		static long min(long a, long b, long c){
			if(a<b && a<c) return a;
			if(b<c) return b;
			return c;
		}
		/*
		
		static class Pair3{
			int x, y ,z;
			Pair3(int x, int y, int z){
				this.x = x;
				this.y = y;
				this.z = z;
			}
		}*/
		static int sum(int n){
			String str = Integer.toString(n);
			int cnt = 0;
			for(int i = 0; i< str.length();i++){
				cnt+=(str.charAt(i)-'0');
			}
			return cnt;
		}
		 static void KMPSearch(String pat, String txt)
		    {
		        int M = pat.length();
		        int N = txt.length();
		 
		        // create lps[] that will hold the longest
		        // prefix suffix values for pattern
		        int lps[] = new int[M];
		        int j = 0;  // index for pat[]
		 
		        // Preprocess the pattern (calculate lps[]
		        // array)
		        computeLPSArray(pat,M,lps);
		 
		        int i = 0;  // index for txt[]
		        while (i < N)
		        {
		            if (pat.charAt(j) == txt.charAt(i))
		            {
		                j++;
		                i++;
		            }
		            if (j == M)
		            {
		               // parent.add((i-j));
		                j = lps[j-1];
		            }
		 
		            // mismatch after j matches
		            else if (i < N && pat.charAt(j) != txt.charAt(i))
		            {
		                // Do not match lps[0..lps[j-1]] characters,
		                // they will match anyway
		                if (j != 0)
		                    j = lps[j-1];
		                else
		                    i = i+1;
		            }
		        }
		    }
		 static void computeLPSArray(String pat, int M, int lps[])
		    {
		        // length of the previous longest prefix suffix
		        int len = 0;
		        int i = 1;
		        lps[0] = 0;  // lps[0] is always 0
		 
		        // the loop calculates lps[i] for i = 1 to M-1
		        while (i < M)
		        {
		            if (pat.charAt(i) == pat.charAt(len))
		            {
		                len++;
		                lps[i] = len;
		                i++;
		            }
		            else  // (pat[i] != pat[len])
		            {
		                // This is tricky. Consider the example.
		                // AAACAAAA and i = 7. The idea is similar 
		                // to search step.
		                if (len != 0)
		                {
		                    len = lps[len-1];
		 
		                    // Also, note that we do not increment
		                    // i here
		                }
		                else  // if (len == 0)
		                {
		                    lps[i] = len;
		                    i++;
		                }
		            }
		        }
		    }
		private static void permutation(String prefix, String str) {
		    int n = str.length();
		    if (n == 0); //hs.add(prefix);
		    else {
		        for (int i = 0; i < n; i++)
		            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
		    }
		}
		public static char give(char c1,char c2){
			if(c1!='a' && c2!='a') return 'a';
			if(c1!='b' && c2!='b') return 'b';
			return 'c';
		}
		
		public static void buildTree(int n){
			int arr[] = sc.nextIntArray(n);
			for(int i = 0;i<n;i++){
				int x = arr[i]-1;
				amp[i+1].add(x);
				amp[x].add(i+1);
			}
		}
		
		static class SegmentTree {
			boolean st[];
			boolean lazy[];

			SegmentTree(int n) {
				int size = 4 * n;
				st = new boolean[size];
				Arrays.fill(st, true);
				lazy = new boolean[size];
				Arrays.fill(lazy, true);
				//build(0, n - 1, 1);
			}
			
			/*long[] build(int ss, int se, int si) {
				if (ss == se) {
					st[si][0] = 1;
					st[si][1] = 1;
					st[si][2] = 1;
					return st[si];
				}
				int mid = (ss + se) / 2;
				long a1[] = build(ss, mid, si * 2), a2[] = build(mid + 1, se,
						si * 2 + 1);
				long ans[] = new long[3];
				if (arr[mid] < arr[mid + 1]) {
					ans[1] = Math.max(a2[1], Math.max(a1[1], a1[2] + a2[0]));
					if (a1[1] == (mid - ss + 1))
						ans[0] = ans[1];
					else
						ans[0] = a1[0];
					if (a2[2] == (se - mid))
						ans[2] = ans[1];
					else
						ans[2] = a2[2];
				} else {
					ans[1] = Math.max(a1[1], a2[1]);
					ans[0] = a1[0];
					ans[2] = a2[2];
				}
				st[si] = ans;
				return st[si];
			}*/

			void update(int si, int ss, int se, int idx, long x) {
				if (ss == se) {
					//arr[idx] += val;
					st[si]=false;
				} 
				else {
					int mid = (ss + se) / 2;
					if(ss <= idx && idx <= mid)
			        {
			             update(2*si, ss, mid, idx, x);
			        }
			        else
			        { update(2*si+1, mid+1, se, idx, x);
			        }
					st[si] = st[2*si]|st[2*si+1];
				}
			}
			/*boolean get(int qs, int qe, int ss, int se, int si){
				if(qs>se || qe<ss) return 0;
				if (qs <= ss && qe >= se) {
					return st[si];
				}
				int mid = (ss+se)/2;
				return get(qs, qe, ss, mid, si * 2)+get(qs, qe, mid + 1, se, si * 2 + 1);
			}*/
			void updateRange(int node, int start, int end, int l, int r, boolean val)
			{
			    if(!lazy[node])
			    { 
			        // This node needs to be updated
			        st[node] = lazy[node];    // Update it
			        if(start != end)
			        {
			            lazy[node*2] = lazy[node];                  // Mark child as lazy
			            lazy[node*2+1] = lazy[node];                // Mark child as lazy
			        }
			        lazy[node] = true;                                  // Reset it
			    }
			    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
			        return;
			    if(start >= l && end <= r)
			    {
			        // Segment is fully within range
			        st[node] =  val;
			        if(start != end)
			        {
			            // Not leaf node
			            lazy[node*2] = val;
			            lazy[node*2+1] = val;
			        }
			        return;
			    }
			    int mid = (start + end) / 2;
			    updateRange(node*2, start, mid, l, r, val);        // Updating left child
			    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
			    st[node] = st[node*2] | st[node*2+1];        // Updating root with max value 
			}

			boolean queryRange(int node, int start, int end, int l, int r)
			{
			    if(start > end || start > r || end < l)
			        return false;         // Out of range
			    if(!lazy[node])
			    {
			        // This node needs to be updated
			        st[node] = lazy[node];            // Update it
			        if(start != end)
			        {
			            lazy[node*2] = lazy[node];         // Mark child as lazy
			            lazy[node*2+1] = lazy[node];    // Mark child as lazy
			        }
			        lazy[node] = true;                 // Reset it
			    }
			    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
			        return  st[node];
			    int mid = (start + end) / 2;
			    boolean p1 = queryRange(node*2, start, mid, l, r);         // Query left child
			    boolean b = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
			    return (p1 | b);
			}
			void print() {
				for (int i = 0; i < st.length; i++) {
					System.out.print(st[i]+" ");
				}
				System.out.println();
			}
		}
		static int convert(int x){
			int cnt = 0;
			String str = Integer.toBinaryString(x);
			//System.out.println(str);
			for(int i = 0;i<str.length();i++){
				if(str.charAt(i)=='1'){
					cnt++;
				}
			}
			int ans = (int) Math.pow(3, 6-cnt);
			return ans;
		}
		static class Node2{
			Node2 left = null;
			Node2 right = null;
			Node2 parent = null;
			int data;
		}
		static class BinarySearchTree{
			Node2 root = null;
			int height = 0;
			int max = 0;
			int cnt = 1;
			ArrayList<Integer> parent = new ArrayList<>();
			HashMap<Integer, Integer> hm = new HashMap<>();
			public void insert(int x){
				Node2 n = new Node2();
				n.data = x;
				if(root==null){
					root = n;
				}
				else{
					Node2 temp = root,temb = null;
					while(temp!=null){
						temb = temp;
						if(x>temp.data) temp = temp.right;
						else temp = temp.left;
					}
					if(x>temb.data) temb.right = n;
					else temb.left = n;
					n.parent = temb;
					parent.add(temb.data);
				}
			}
			public Node2 getSomething(int x, int y, Node2 n){
				if(n.data==x || n.data==y) return n;
				else if(n.data>x && n.data<y) return n;
				else if(n.data<x && n.data<y) return getSomething(x,y,n.right);
				else return getSomething(x,y,n.left);
			}
			public Node2 search(int x,Node2 n){
				if(x==n.data){
					max = Math.max(max, n.data);
					return n;
				}
				if(x>n.data){
					max = Math.max(max, n.data);
					return search(x,n.right);
				}
				else{
					max = Math.max(max, n.data);
					return search(x,n.left);
				}
			}
			public int getHeight(Node2 n){
				if(n==null) return 0;
				height = 1+ Math.max(getHeight(n.left), getHeight(n.right));
				return height;
			}
		}
		static long findDiff(long[] arr, long[] brr, int m){
			int i = 0, j = 0;
			long fa = 1000000000000L;
			while(i<m && j<m){
				long x = arr[i]-brr[j];
				if(x>=0){
					if(x<fa) fa = x;
					j++;
				}
				else{
					if((-x)<fa) fa = -x;
					i++;
				}
			}
			return fa;
		}
		public static long max(long x, long y, long z){
			if(x>=y && x>=z) return x;
			if(y>=x && y>=z) return y;
			return z;
		}
		
		static long modInverse(long a, long mOD2){
		            return  power(a, mOD2-2, mOD2);
		}
		static long power(long x, long y, long m)
		{
		    if (y == 0)
		        return 1;
		    long p = power(x, y/2, m) % m;
		    p = (p * p) % m;
		 
		    return (y%2 == 0)? p : (x * p) % m;
		}
		static long power2(long x,BigInteger y,long m){
			long ans = 1;
			BigInteger two = new BigInteger("2");
			while(y.compareTo(BigInteger.ZERO)>0){
				if(y.getLowestSetBit()==y.bitCount()){
					x = (x*x)%MOD;
					y = y.divide(two);
				}
				else{
					ans = (ans*x)%MOD;
					y = y.subtract(BigInteger.ONE);
				}
			}
			return ans;
		}
		static BigInteger power2(BigInteger x, BigInteger y, BigInteger m){
			BigInteger ans = new BigInteger("1");
			BigInteger one  = new BigInteger("1");
			BigInteger two  = new BigInteger("2");
			BigInteger zero  = new BigInteger("0");
			while(y.compareTo(zero)>0){
				//System.out.println(y);
				if(y.mod(two).equals(one)){
					ans = ans.multiply(x).mod(m);
					y = y.subtract(one);
				}
				else{
					x = x.multiply(x).mod(m);
					y = y.divide(two);
				}
			}
			return ans;
		}
		static BigInteger power(BigInteger x, BigInteger y, BigInteger m)
		{
		    if (y.equals(0))
		        return (new BigInteger("1"));
		    BigInteger p = power(x, y.divide(new BigInteger("2")), m).mod(m);
		    p = (p.multiply(p)).mod(m);
		 
		    return (y.mod(new BigInteger("2")).equals(0))? p : (p.multiply(x)).mod(m);
		}
		static long d,x,y;
		public static void extendedEuclidian(long a, long b){
			if(b == 0) {
		        d = a;
		        x = 1;
		        y = 0;
		    }
		    else {
		        extendedEuclidian(b, a%b);
		        int temp = (int) x;
		        x = y;
		        y = temp - (a/b)*y;
		    }
		}
		
		public static long gcd(long n, long m){
			if(m!=0) return gcd(m,n%m);
			else return n;
		}
		
		static BufferedReader reader;
	    static StringTokenizer tokenizer;
	    static PrintWriter writer;
	
	
	   
	    static class FasterScanner {

			private final InputStream stream;
			private final byte[] buf = new byte[8192];
			private int curChar, snumChars;
			private SpaceCharFilter filter;

			public FasterScanner(InputStream stream) {
				this.stream = stream;
			}

			public int snext() {
				if (snumChars == -1)
					throw new InputMismatchException();
				if (curChar >= snumChars) {
					curChar = 0;
					try {
						snumChars = stream.read(buf);
					} catch (IOException e) {
						throw new InputMismatchException();
					}
					if (snumChars <= 0)
						return -1;
				}
				return buf[curChar++];
			}

			public int nextInt() {
				int c = snext();
				while (isSpaceChar(c)) {
					c = snext();
				}
				int sgn = 1;
				if (c == '-') {
					sgn = -1;
					c = snext();
				}
				int res = 0;
				do {
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}

			public long nextLong() {
				int c = snext();
				while (isSpaceChar(c)) {
					c = snext();
				}
				int sgn = 1;
				if (c == '-') {
					sgn = -1;
					c = snext();
				}
				long res = 0;
				do {
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}

			public int[] nextIntArray(int n) {
				int a[] = new int[n];
				for (int i = 0; i < n; i++) {
					a[i] = nextInt();
				}
				return a;
			}

			public long[] nextLongArray(int n) {
				long a[] = new long[n];
				for (int i = 0; i < n; i++) {
					a[i] = nextInt();
				}
				return a;
			}
	                
			public String readString() {
				int c = snext();
				while (isSpaceChar(c)) {
					c = snext();
				}
				StringBuilder res = new StringBuilder();
				do {
					res.appendCodePoint(c);
					c = snext();
				} while (!isSpaceChar(c));
				return res.toString();
			}

			public String nextLine() {
				int c = snext();
				while (isSpaceChar(c))
					c = snext();
				StringBuilder res = new StringBuilder();
				do {
					res.appendCodePoint(c);
					c = snext();
				} while (!isEndOfLine(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;
			}

			private boolean isEndOfLine(int c) {
				return c == '\n' || c == '\r' || c == -1;
			}

			public interface SpaceCharFilter {
				public boolean isSpaceChar(int ch);
			}
		}
	}  