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

---

【题目描述】

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

【输入格式】

　　第一行包含一个正整数：\(n\)，分别表示序列元素数目和查询数目
　　第二行有 \(n\) 个整数，第 \(i\) 个整数表示 \(A[i]\)
　　第三行是一个整数 \(m\)
　　再接下来的 \(m\) 行，每行两个整数 \(a,b（a<=b）\)，表示需要查询在 \(A[a]..A[b]\) 内不同元素的数目。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

4
4
7
4
4

【数据限制】

　　对于 \(30\%\) 的数据，\(0<n≤100\)，\(0<m≤1000\)
　　对于 \(60\%\) 的数据，\(0<n≤3000\)，\(0<m≤200000\)
　　对于 \(100\%\) 的数据，\(0<n≤50000\)，\(0<m≤200000\)，\(0≤A[i]≤1000000\)

【来源】

　　Mr.he**