Alice has $N$ integers $a_1$ , $a_2$ , _.... , $a_{n-1}$ , $a_n$ _. An integer may occur multiple times in the array.

Alice has to answer $Q$ queries, each query consisits of two integers $x$ and $y$. Alice need to find the maximum value of $| i-j|$ such that $a_i=x$ and $a_i=y$. Help Alice answer the $Q$ queries.

INPUT:

    The first line contains a single integer $N$.

    The second line contains $N$  space separated integers.

    The third line contains a single integer $Q$.

    $Q$ lines follow, each line contains two space sepatated integers $x$ and $y$.

OUTPUT:

    Output $Q$ lines, $i^{th}$ of which line should contain a single integer $max |i-j|$ associated with $i^{th}$ query if both $x$ and $y$ are in the array. If either of $x$ or $y$ is not present in the array output -1.

CONSTRAINTS:

    $2 \leq N \leq 200000$

   $0 \leq a_i \leq 10^9$ for all i from $1$ to $N$