某高速路是多个城市交通的枢纽。每天都有很多车辆往返于该高速路上。
为统计该高速路上各个城市的车辆行驶的数据，统计员在高速路上安装了一个高清抓拍的摄像头。摄像头抓拍到了 N 辆车的车牌，并通过车牌分析出了每辆车所属的城市。
现有 M 次查询，对于第 i 次查询，请你编程统计出从第 S_i 辆车开始，到第 T_i 辆车结束（含 S_i 和 T_i 这两辆车）的这个范围内，共抓拍到多少不同城市的车辆。
第 1 行读入一个整数 N，代表抓拍到的车辆的数量。
第 2 行读入 N 个整数，第 i 个整数 A_i 代表该车辆来自编号为 A_i 的城市。
第 3 行读入一个整数 M，代表询问的次数。
接下来 M 行，每行读入两个整数 S_i 和 T_i，代表询问的时间范围。
输出 M 行，每行输出一个整数，代表对于每个询问，查询到的结果。
10 1 2 3 2 8 7 3 6 5 8 5 1 4 2 5 5 10 1 10 3 8
3 3 5 7 5
20 1 3 9 2 3 4 10 20 1 3 9 10 20 3 6 7 8 10 20 7 6 1 5 6 10 11 15 16 20 8 18 10 20
4 5 5 4 8 7
区间 [1,4] 范围内共有 3 种不同的数：1 2 3。
区间 [2,5] 范围内共有 3 种不同的数：2 3 8。
\dots
对于 20\% 的数据，1 \le N,M \le 1000。
对于 100\% 的数据，1 \le N \le 5 \times 10^4，1 \le M \le 2 \times 10^5，1 \le A_i \le 10^6，1 \le S_i \le T_i \le N。