Given a sequence $a$ of length $n$.

There are $m$ queries. Each query provides an interval $[l, r]$, and you are asked to find $|\{(a_i, a_j) : l \le i < j \le r \wedge a_i > a_j\}|$.

$1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, where the $i$-th number $a_i$ represents the value at the $i$-th position of the sequence. It is guaranteed that $1 \le a_i \le n$.

The third line contains a positive integer $m$.

The following $m$ lines each contain two space-separated positive integers $l$ and $r$, representing a query. It is guaranteed that $1 \le l \le r \le n$.

Output

Output $m$ lines, where the $i$-th line contains a single integer representing the answer to the $i$-th query.

Examples

Input 1

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

Output 1

1
3
3
0

Note 1

For the first query, the set is $\{(3, 1)\}$.

For the second and third queries, the set is $\{(2, 1), (3, 1), (3, 2)\}$.

For the fourth query, the set is empty.