Easy String Problem
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given a string with length , and the size of the alphabet also is .

There are  queries. For a query, you are given two integers  and you need to answer the number of different strings (which can be empty) that can be obtained by removing a substring containing .

输入描述:

The first line contains one integer  (), denoting the length of the string .
The second line contains  integers  ().
The third line contains one integer  (), denoting the number of queries.
For the -th to -th lines, each line contains two integers  (), 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

输出

复制 
4
5
3
2
2
1

说明

The string in the sample is equal to 'abca'.

For the first query :
'bca' can be obtained by removing substring .
'ca' can be obtained by removing substring .
'a' can be obtained by removing substring .
Empty string can be obtained by removing substring .
So the answer is .

For the third query :
'aa' can be obtained by removing substring .
'a' can be obtained by removing substring  or .
Empty string can be obtained by removing substring .
So the answer is .