时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出一个序列 \(A[1],A[2],…,A[n]\)，需要你写个程序回答一些询问：\(a\ b\)，询问 \(A[a]..A[b]\) 内不同元素的数目。要求在线算法实现。

【输入格式】

　　第一行包含两个正整数：\(n,m\)，分别表示序列元素数目和查询数目。
　　第二行有 \(n\) 个整数，第 \(i\) 个整数表示 \(A[i]\)。
　　再接下来的 \(m\) 行，每行两个整数 \(a,b（a≤b）\)，表示一个查询。为体现在线操作，设 \(lastAns\) 为上一次查询的时候程序输出的结果，如果之前没有查询过，则 \(lastAns=0\)。则实际查询的是：\(A[x]..A[y]\) 内的不同元素的数目,其中： \(x=min(a+lastAns,n)，y=min(b+lastAns,n)\)。

【输出格式】

　　针对每个查询，输出其答案。

【输入输出样例】

　Input

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

　Output

4
4
5
1
4

【数据说明】

　　对于 \(30\%\) 的数据 \(1≤n,m≤100\)。
　　对于 \(60\%\) 的数据 \(1≤n,m≤1000\)。
　　对于 \(100\%\) 的数据 \(1≤n,m≤10000\)，任何时候序列中的元素值不超过 1000000。

【来源】

　　Mr.he