長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられます。以下のクエリを実行するプログラムを書いてください。
i j: $A_i, A_{i+1}, \ldots, A_j$ に含まれる値の種類数を出力せよ。
入力
1 行目には数列の長さ $N$ が与えられる ($1 \le N \le 100{,}000$)。
2 行目には $A_1, A_2, \ldots, A_N$ が与えられる ($1 \le A_i \le 1{,}000{,}000$)。
3 行目にはクエリの個数 $M$ が与えられる ($1 \le M \le 100{,}000$)。
4 行目から $M$ 行目までには、各クエリ $i, j$ が与えられる ($1 \le i \le j \le N$)。
出力
各クエリに対して、答えを 1 行ずつ出力せよ。
入出力例
入力例 1
5 1 1 2 1 3 3 1 5 2 4 3 5
出力例 1
3 2 3