给定一个长度为 $n$ 的字符串，其字母表大小也为 $n$。 共有 $q$ 次询问。对于每次询问，给定两个整数 $l, r$，你需要回答通过删除包含区间 $[l, r]$ 的子串所能得到的不同字符串（可以为空）的数量。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示字符串 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。 第三行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示询问次数。 接下来的 $q$ 行，每行包含两个整数 $l, r$ ($1 \le l \le r \le n$)，表示一次询问。

输出格式

对于每次询问，输出一行，表示答案。

样例

样例输入 1

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

样例输出 1

4
5
3
2
2
1

说明

样例中的字符串为 “abca”。 对于第一次询问 1, 1： 通过删除子串 $[1, 1]$ 可以得到 “bca”。 通过删除子串 $[1, 2]$ 可以得到 “ca”。 通过删除子串 $[1, 3]$ 可以得到 “a”。 通过删除子串 $[1, 4]$ 可以得到空串。 所以答案为 4。

对于第三次询问 2, 3： 通过删除子串 $[2, 3]$ 可以得到 “aa”。 通过删除子串 $[1, 3]$ 或 $[2, 4]$ 可以得到 “a”。 * 通过删除子串 $[1, 4]$ 可以得到空串。 所以答案为 3。