Given a permutation of n elements.
Answer m queries about the number of inversions for a permutation subsegment from l to r.
An inversion is a pair of indices i, j such that i < j and a
i > a
j, where a
i is the i-th element of the permutation.
Input:
The first line contains the number n (1 <= n <= 10
5).
The second line contains a permutation of n elements (the elements of the permutation are pairwise distinct integers from 1 to n).
The third line contains number m (1 <= m <= 10
5).
The next m lines contain two integers l and r - the bounds of the query (1 <= l, r <= n).
Output:
Print m lines - the answers to these queries.
Examples:
| Input |
Output |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |