You are given a sequence $a$ of length $n$ and $m$ queries. For each query, you need to find the number of inversions in a given range.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence.

The following $m$ lines each contain two integers representing the query range.

Output

Output $m$ lines, each containing an integer representing the answer to the corresponding query.

Constraints

$1 \leq n, m \leq 10^5$, $0 \leq a_i \leq 10^9$.

Algorithms with complexity better than $O(n^{1.5})$ are expected.

By nzhtl1477

Examples

Input 1

4 1
1 4 2 3
2 4

Output 1

2