We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

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


Output

2
3
1


Input

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8


Output

1
2
2
1
2
2
6
3
3
3
import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt(),q= sc.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++)
			arr[i] =sc.nextInt();
		Pair[] qs = new Pair[q + 1];
		for(int i=1;i<=q;i++)
			qs[i] = new Pair(sc.nextInt(), sc.nextInt(),i - 1);
		qs[0] = new Pair(0,0,0);
		Arrays.parallelSort(qs);
		int[] last = new int[(int)6e5];
		int[] ans = new int[q];
		int size = 1;
		while(size<n) size*=2;
		SegmentTree st = new SegmentTree(size + 1);
		for(int i=1;i<=q;i++) {
			if(qs[i].r != qs[i-1].r) {
				HashSet<Integer> hs  =new HashSet<Integer>();
				for(int j=qs[i].r; j>qs[i-1].r;j--) 
					if(!hs.contains(arr[j-1])) {
						hs.add(arr[j-1]);
						st.update_point(j, 1);
						if(last[arr[j-1]]>0)
							st.update_point(last[arr[j-1]],	0);
						last[arr[j-1]] = j;
					}
			}
			ans[qs[i].i] = st.query(qs[i].l, qs[i].r);
		}
		for(int x:ans)
			out.println(x);
		out.close();
	}
	static class Pair implements Comparable<Pair>{
		int l,r,i;
		Pair(int l, int r, int i){
			this.l =l;
			this.r=r;
			this.i =i;
		}
		@Override
		public int compareTo(Pair o) {
			if(r==o.r)
				return o.l - l;
			return r - o.r;
		}
		
	}
	static class SegmentTree { // 1-based DS, OOP

		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;
		
		SegmentTree(int size)		
		{
			N = size - 1;
			sTree = new int[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
//			lazy = new int[N<<1];
//			build(1,1,N);
		}
		
		void build(int node, int b, int e)	// O(n)
		{
			if(b == e)					
				sTree[node] = array[b];
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = sTree[node<<1]+sTree[node<<1|1];
			}
		}
		
		
		void update_point(int index, int val)			// O(log n)
		{
			index += N - 1;				
			sTree[index] = val;			
			while(index>1)				
			{
				index >>= 1;
				sTree[index] = sTree[index<<1] + sTree[index<<1|1];		
			}
		}
		
		
		void update_range(int i, int j, int val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}
		
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				sTree[node] += (e-b+1)*val;			
				lazy[node] += val;				
			}							
			else		
			{
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		
			}
			
		}
		void propagate(int node, int b, int mid, int e)		
		{
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
			sTree[node<<1] += (mid-b+1)*lazy[node];		
			sTree[node<<1|1] += (e-mid)*lazy[node];		
			lazy[node] = 0;
		}
		
		int query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		int query(int node, int b, int e, int i, int j)	// O(log n)
		{
			if(i>e || j <b)
				return 0;		
			if(b>= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
//			propagate(node, b, mid, e);
			int q1 = query(node<<1,b,mid,i,j);
			int q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	
					
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}
