题目描述

HH 有一串项链，由 $n$ 颗宝石组成，每颗宝石有一种颜色（用整数表示）。MMM 询问这串项链中，区间 $[l,r]$ 里有多少颗颜色互不相同的宝石（即该区间内不同颜色的数量）。

输入格式

第一行一个整数 $n$，表示宝石个数。
第二行 $n$ 个整数，第 $i$ 个表示第 $i$ 颗宝石的颜色 $a_i$。
第三行一个整数 $m$，表示询问个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示一次询问区间。

输出格式

输出 $m$ 行，每行一个整数，表示对应区间内不同颜色的数量。

数据范围

$1\le n\le 5\times 10^5$，$1\le m\le 2\times 10^5$，$1\le a_i\le 10^6$，$1\le l\le r\le n$。

样例

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

输出：

3
2
4