Background

.

Problem Description

For a sequence $p$, we define $\mathrm{W}(p)$ as the number of inversion pairs in $p$.

Note: An inversion pair here means a pair that satisfies $p_i > p_j$ and $i < j$.

Now you are given a sequence $a$, which is a permutation of the integers $1 \sim n$. That is, for any $1 \le i \le n$, we have $1 \le a_i \le n$, all $a_i$ are integers, and they are all distinct.

There is a graph with $n$ nodes, numbered $1 \sim n$. For any two nodes with indices $i, j \ (1 \le i < j \le n)$, we add an undirected edge between them with weight $\mathrm{W}([a_i, a_{i+1}, \dots, a_{j-1}, a_j])$.

There are $q$ queries. Each query gives two nodes numbered $x, y$, and you need to find the shortest path between them.

Input Format

The first line contains two integers $n, q$.

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

The next $q$ lines each contain two integers, representing one query $x, y$.

Output Format

For each query:

Output one integer, the length of the required shortest path.

3 2
3 1 2
1 3
2 2

1
0

Hint

For all testdata, it is guaranteed that: $2 \le n \le 3 \times 10^5$, $1 \le q \le 3 \times 10^5$, $1 \le x, y \le n$.

Translated by ChatGPT 5