链接：
https://ac.nowcoder.com/acm/contest/32708/E
来源：牛客网
You are given a string with length n, and the size of the alphabet also is n.
There are q queries. For a query, you are given two integers l,r and you need to answer the number of different strings (which can be empty) that can be obtained by removing a substring containing [l,r].
输入描述:
The first line contains one integer n (3≤n≤105), denoting the length of the string aaa.
The second line contains nnn integers a1,a2,⋯,an (1≤ai≤n1).
The third line contains one integer qqq (1≤q≤105), denoting the number of queries.
For the 4-th to (q+3)-th lines, each line contains two integers l,r (1≤l≤r≤n), denoting a query.
输出描述:
For each query, output a number in a line indicating the answer.
示例1
输入
4
1 2 3 1
6
1 1
3 3
2 3
2 4
1 3
1 4
说明
The string in the sample is equal to 'abca'.
For the first query 1,1:
'bca' can be obtained by removing substring [1,1].
'ca' can be obtained by removing substring [1,2].
'a' can be obtained by removing substring [1,3].
Empty string can be obtained by removing substring [1,4].
So the answer is 4.
For the third query 2,3:
'aa' can be obtained by removing substring [2,3.
'a' can be obtained by removing substring [1,3] or [2,4].
Empty string can be obtained by removing substring [1,4].
So the answer is 3.