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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,q;
  	cin>>n>>q;
  	vector<int>a(n);
  	for(int i=0;i<n;i++)cin>>a[i];
  	vector<vector<int> >d(n);
  	vector<int>f(n);
  	vector<int>ans(q);
	vector<vector<int> >id(n);
  	for(int i=0;i<q;i++)
    {
      int l,r;
      cin>>l>>r;
      l--;
      r--;
      d[r].push_back(l);
      id[r].push_back(i);
    }
  	vector<int>p(n+1,-1);
  	for(int i=0;i<n;i++)
    {
      if(p[a[i]]!=-1)
      {
        for(int j=p[a[i]];j<n;j=(j|(j+1)))f[j]-=1;
      }
      p[a[i]]=i;
      for(int j=p[a[i]];j<n;j=(j|(j+1)))f[j]+=1;
  	  for(int j=0;j<d[i].size();j++)
      {
        int lsum=0;
        int rsum=0;
        for(int t=i;t>=0;t=(t&(t+1))-1)rsum+=f[t];
        if(d[i][j]>0)
        {
          for(int t=d[i][j]-1;t>=0;t=(t&(t+1))-1)lsum+=f[t];
        }
        ans[id[i][j]]=rsum-lsum;
      }
    }
  for(auto x:ans)cout<<x<<endl;   
  return 0;
}
     