Cosider a sequence, consisting of $*n*$ integers: $*a*_{1}$, $*a*_{2}$, $...$, $*a*_{*n*}$. Jeff can perform the following operation on sequence $*a*$:

• take three integers $*v*$, $*t*$, $*k*$ $(1 ≤ *v*, *t* ≤ *n*; 0 ≤ *k*; *v* + *tk* ≤ *n*)$, such that $*a*_{*v*}$ = $*a*_{*v* + *t*}$, $*a*_{*v* + *t*}$ = $*a*_{*v* + 2*t*}$, $...$, $*a*_{*v* + *t*(*k* - 1)}$ = $*a*_{*v* + *tk*}$;
• remove elements $*a*_{*v*}$, $*a*_{*v* + *t*}$, $...$, $*a*_{*v* + *t*·*k*}$ from the sequence $*a*$, the remaining elements should be reindexed $*a*_{1}, *a*_{2}, ..., *a*_{*n* - *k* - 1}$.
• permute in some order the remaining elements of sequence $*a*$.

A beauty of a sequence $*a*$ is the minimum number of operations that is needed to delete all elements from sequence $*a*$.

Jeff's written down a sequence of $*m*$ integers $*b*_{1}$, $*b*_{2}$, $...$, $*b*_{*m*}$. Now he wants to ask $*q*$ questions. Each question can be described with two integers $*l*_{*i*}, *r*_{*i*}$. The answer to the question is the beauty of sequence $*b*_{*l*_{*i*}}$, $*b*_{*l*_{*i*} + 1}$, $...$, $*b*_{*r*_{*i*}}$. You are given the sequence $*b*$ and all questions. Help Jeff, answer all his questions.

Input

The first line contains integer $*m*$ $(1 ≤ *m* ≤ 10^{5})$. The next line contains $*m*$ integers $*b*_{1}$, $*b*_{2}$, $...$, $*b*_{*m*}$ $(1 ≤ *b*_{*i*} ≤ 10^{5})$.

The third line contains integer $*q*$ $(1 ≤ *q* ≤ 10^{5})$ — the number of questions. The next $*q*$ lines contain pairs of integers, $*i*$-th of them contains a pair of integers $*l*_{*i*}$, $*r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *m*)$ — the description of $*i*$-th question.

Output

In $*q*$ lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.