After getting over the initial shock of the variety of candy apples, Molly finally decides to explore the carnival.

However, she had not taken two steps when the sign of a giant manga booth caught her eye. There are $N$ different volumes of manga lined up in a row, the $i^{th}$ of which belongs to the ${a_i}^{th}$ series.

Molly is eager to explore the rest of the carnival but cannot resist perusing this grand selection of manga. However, Molly is a cat and therefore cannot read. Additionally, she can only focus on one contiguous interval of the manga display at a time.

You recall that Molly considers a series of manga in an interval interesting if their frequency in that interval is even (and positive).

Can you write a program to help Molly determine the amount of interesting manga?

Input Specification

Line $1$: One integer $N$, denoting the number of volumes of manga on display.
Line $2$: $N$ space-separated integers $a_i$ $(1\le i\le N)$, denoting the series number of the $i^{th}$ volume.
Line $3$: One integer $Q$, denoting the number of queries Molly will give.
Next $Q$ lines: Two space-separated integers $p_j,q_j$ $(1\le j\le Q)$ denoting the left- and rightmost manga included in Molly's queried interval.

Output Specification

Your program should output $Q$ integers, each on their own line, denoting the number of manga series with an even frequency in the queried interval in the order they are given in the input.

Constraints

For all subtasks:

$1\le p_j\le q_j\le N$

$1\le a_i\le {10}^5$

Subtask	Points	$N$	$Q$
1	30	$1\le N\le 100$	$1\le Q\le 100$
2	70	$1\le N\le {10}^5$	$1\le Q\le {10}^5$

Sample Input

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

Sample Output

0
1
2