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 different volumes of manga lined up in a row, the of which belongs to the 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 : One integer , denoting the number of volumes of manga on display.

Line : space-separated integers , denoting the series number of the volume.

Line : One integer , denoting the number of queries Molly will give.

Next lines: Two space-separated integers denoting the left- and rightmost manga included in Molly's queried interval.

#### Output Specification

Your program should output 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:

Subtask | Points | ||
---|---|---|---|

1 | 30 | ||

2 | 70 |

#### Sample Input

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

#### Sample Output

```
0
1
2
```

## Comments