题意：有一个数组 a[] 长度为n.
q组询问，每组询问[L,R]表示询问a1……aL,aR……an中有多少个不同的数字。n,q=1e5.

令an+i=ai，将原数组a[]的长度扩大为2n
原询问等价于[R,n+L],即询问aR……an,an+1,……,an+L中有多少个不同的数字。

莫队思想：利用 询问的离线性 和 答案支持连续的端点修改 两个性质，调整询问的顺序。
我们依据 询问的左端点的值 把所有的询问区间分为√n 组，每一组的长度是√n ，左端点值为x，则这个询问落在第(x/√n+1)组。
各组组内也要排序，组内的顺序即右端点的值从小到大。

具体做法：将所有询问排序，第一关键字为组号，第二关键字为右端点的值。
假设我们已经维护了一个结构，它可以求出一个询问的答案，并且维护了这个询问区间内每个数出现的次数。
那么：从一个询问到另一个询问，有两种情况：
①两个询问属于同组：最多修改√n 次左端点，修改ki次右端点
设该组内有mj个询问，则回答完这个组的询问的复杂度为：O(mj×√n +Σki)，(其中Σki<=n,Σmj=n). 即O(mj×√n +n)
②两个询问属于不同组：可以放弃当前维护的询问，另行维护(求出)一个结构，复杂度为O(n)
这种情况由于组号数，最多出现O(√n)次。
所有更换组的总复杂度O(n√n)；求所有组内询问的总复杂度：ΣO(mj×√n +n)=ΣO(mj×√n)+√nO(n)=O(n√n)。这两种操作是并列(互斥)的，所以总复杂度O(n√n).
--就是因为根号的缘故可能被卡-- 

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int a[200010];
int sq1e5=316;
struct quest
{
	int i,lef,rig;
	int ans;
	int group;
}s[100010];
int vis[100001];
bool my(quest a,quest b)
{
	if(a.group==b.group) return a.rig<b.rig;
	else return a.group<b.group;
}
bool re(quest a,quest b)
{
	return a.i<b.i;
}
int read()
{ 
	int x=0; char ch=getchar();
	if(ch==EOF) exit(0);
	while(!isdigit(ch))  ch=getchar();
	while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} 
	return x; 
 }
void put(int x)
{ 
	if(x==0){putchar('0'); putchar('\n'); return;} 
	if(x<0){putchar('-'); x=-x;} 
	int num=0; char ch[16]; 
	while(x) ch[++num]=x%10+'0',x/=10; 
	while(num) putchar(ch[num--]); 
	putchar('\n'); 
}
int add(int i,int f)
{
	if(f==1)
	{
		if(vis[i]){++vis[i];return 0;}
		else{++vis[i];return 1;}
	}
	else
	{
		--vis[i];
		if(vis[i])return 0;
		else return -1;
	}
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	int n=read(),q=read();
	do
	{
		for(int i=1;i<=n;++i) {a[i]=read();a[n+i]=a[i];}
		for(int i=1;i<=q;++i)
		{
			s[i].rig=read()+n;s[i].lef=read();
			s[i].i=i;
			//s[i].rig+=n;
			s[i].group=s[i].lef/sq1e5+1;
		}
		sort(s+1,s+1+q,my);
		int lef=n,rig=n+1;
		int cnt=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=q;++i)
		{
			if(s[i].group>s[i-1].group)
			{
				memset(vis,0,sizeof(vis));
				cnt=0;
				lef=s[i].lef;
				rig=s[i].rig;
				for(int o=n;o>=lef;--o) cnt+=add(a[o],1);
				for(int o=n+1;o<=rig;++o) cnt+=add(a[o],1);
				s[i].ans=cnt;
			}
			else
			{
				if(lef<s[i].lef)
				{
					for(int o=lef;o<s[i].lef;++o)
					{
						cnt+=add(a[o],-1);
					}
				}
				else
				{
					for(int o=lef-1;o>=s[i].lef;--o)
					{
						cnt+=add(a[o],1);
					}
				}
				lef=s[i].lef;
				for(int o=rig+1;o<=s[i].rig;++o)
				{
					cnt+=add(a[o],1);
				}
				rig=s[i].rig;
				s[i].ans=cnt;
			}
		}
		sort(s+1,s+1+q,re);
		for(int i=1;i<=q;++i)
		{
			put(s[i].ans);
		}
	}while(n=read(),q=read());
	return 0;
}