题目背景

检定站的记录员把每天的过检编号抄成一行，编号可以重复。上级下来若干次核查，每次圈出其中连续的一段，只想知道这段记录里"只出现过一次"的编号有多少个——出现两次以上的编号一律不管，没出现过的当然也不算。

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，以及 $q$ 次询问。每次询问给出两个整数 $l, r$（$1 \le l \le r \le n$），请回答：在 $a_l, a_{l+1}, \dots, a_r$ 这些数中，恰好出现一次的不同数值有多少个。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

第三行一个整数 $q$。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

输出格式

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

输入输出样例 #1

输入 #1

5
1 2 2 3 1
3
1 5
1 2
2 3

输出 #1

1
2
0

输入输出样例 #2

输入 #2

1
7
1
1 1

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

0
0
1

说明

样例解释

样例 1：区间 $[1,5]$ 中 $1$ 出现 $2$ 次、$2$ 出现 $2$ 次、$3$ 出现 $1$ 次，恰好出现一次的不同数值只有 $3$，答案为 $1$；区间 $[1,2]$ 中 $1$ 与 $2$ 各出现一次，答案为 $2$；区间 $[2,3]$ 中 $2$ 出现两次，答案为 $0$。

样例 2：区间只有 $7$ 一个数，出现 $1$ 次，答案为 $1$。

样例 3：区间 $[1,4]$ 与 $[2,3]$ 中数值 $2$ 都出现两次以上，答案为 $0$；区间 $[1,1]$ 中只有单独一个 $2$，出现一次，答案为 $1$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n, q \le 100$；
• 对于 $60\%$ 的数据，$1 \le n, q \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^{5}$，$1 \le a_i \le 10^{9}$。