题目描述

小珂有一串长长的彩珠，珠子按颜色分成了许多种。她坚信不同颜色的珠子各有各的寓意，所以每次闲暇时，她都会随手截出连续的一段珠子，琢磨这一段里出现了哪些颜色。日子一天天过去，她收集的珠子越来越多，珠串也越来越长。

终于有一天，她想弄明白一个问题：任意取出的一段珠子中，一共包含多少种不同的颜色？珠串实在太长了，她数不过来，只好请擅长编程的你来帮忙回答。

输入格式

第一行一个正整数 $n$，表示珠串的长度。
第二行 $n$ 个正整数 $a_i$，表示珠串中第 $i$ 颗珠子的颜色种类。

第三行一个整数 $m$，表示小珂询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

输出格式

输出 $m$ 行，每行一个整数，依次表示每次询问对应的答案。

样例

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

2
2
4

提示

【数据范围】

对于 $20\%$ 的数据，$1\le n,m\leq 5000$；
对于 $40\%$ 的数据，$1\le n,m\leq 10^5$；
对于 $60\%$ 的数据，$1\le n,m\leq 5\times 10^5$；
对于 $100\%$ 的数据，$1\le n,m,a_i \leq 10^6$，$1\le l \le r \le n$。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB。