时间限制：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）\)，表示需要查询在 \(A[a]..A[b]\) 内不同元素的数目。

【输出格式】

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

【输入输出样例】

　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
7
4
4

【数据限制】

　　对于 \(20\%\) 的数据，\(m,n≤5000\)
　　对于 \(40\%\) 的数据，\(m,n≤100000\)，1≤A[i]≤1000000\(
　　对于 \)100\%\( 的数据，\)m,n≤100000\(，1≤A[i]≤1000000000\)

【来源】

　　Mr.he