Given a sequence of length $n$, answer $q$ queries. For each query $[l, r]$, find the shortest subsegment $[l', r']$ such that all numbers appearing in $[l, r]$ also appear in $[l', r']$. You only need to output the length of $[l', r']$, which is $r' - l' + 1$.

Input

The first line contains a positive integer $n$. The next line contains $n$ positive integers, representing the elements of the sequence. The next line contains a positive integer $q$. The next $q$ lines each contain two positive integers $l, r$, representing a query.

Output

For each query, output a single positive integer on a new line representing the answer.

Subtasks

For all data, $1 \le n, q, a_i \le 2 \times 10^6$.

Examples

Input 1

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

Output 1

2
3
3