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

---

【题目描述】

　　HH同学有一串由各种颜色的贝壳构成的项链，有一天，他突然提出一个问题：某一段贝壳中，包含了多少种不同的颜色？这个问题很难回答，因为项链实在太长。于是他只有求助于你。

【输入格式】

　　第一行：一个整数 \(N\)，表示项链包含的贝壳数量，分别编号为 \(1..N\)。
　　第二行：\(N\) 个正整数，依次表示项链中贝壳的颜色（0..1 000 000之间的整数）。
　　第三行：一个整数 \(M\)，表示 HH 的询问。
　　接下来的 \(M\) 行，每行两个整数 \(L\) 和 \(R(1≤L≤R≤N)\)，表示询问区间。

【输出格式】

　　\(M\) 行，每行一个整数，依次表示询问对应的答案。

【输入输出样例】

　Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

　Output

2
2
4

【数据限制】

　　对于 \(30\%\) 的数据，\(N≤100\)，\(M≤1000\)
　　对于 \(60\%\) 的数据，\(N≤3000\)，\(M≤200000\)
　　对于 \(100\%\) 的数据，\(N≤50000\)，\(M≤200000\)

【来源】

　　Mr.he