## Sherlock and Watson

After a long series of jobless days, Sherlock and Watson frustated by the lack of new cases, decide to turn their minds toward something interesting like solving few logical problems. One of the problems they have to solve now is as follows:

Given an A array of size and a list of queries, where each query has two L and R numbers, find for each query the number of investments in the subarray located between the L and R positions (both inclusive) of the A array. Settlement indices begin at 1 and . For an A array, two elements and form an inversion if and . Help them solve this problem.

#### Input

The first line contains a single integer, the length of the array. The second line contains N integers separated by a space. The third line has a single integer Q. The following Q lines contain 2 integers L and R separated by a space and represent the query information.

#### Output

Output Q lines, ith line having a single integer, the answer to the ith query

#### Example Input:

```
7
7 9 3 5 1 6 4
4
1 4
3 5
1 2
1 7
```

#### Output:

```
4
2
0
14
```

## Comments

This comment is hidden due to too much negative feedback. Show it anyway.

Alguien me dice q algoritmo c utiliza para este problema? Puede ser una DP, o lo otro podría ser Segment-tree???

Mo's algorithm con ABI