Inversion Graph Shortest Path

You are given a permutation \(a = [a_1, a_2, \dots, a_n]\) of the integers from \(1\) to \(n\). For any sequence \(p\) (which in our problem is a contiguous subarray of \(a\)), define its inversion count \(\mathrm{W}(p)\) as the number of pairs \((i, j)\) with \(i p_j\). In other words, if \(p = [p_1,p_2,\dots,p_k]\), then \[ \mathrm{W}(p)=\#\{(i, j) \mid 1 \le i p_j\}\,. \]

Now, consider an undirected graph with \(n\) nodes labeled \(1\) to \(n\). For every two nodes with indices \(i\) and \(j\) (where \(1 \le i

There are (q) queries. Each query gives you two node indices (x) and (y), and you need to determine the shortest path between these nodes.

Observation: For any two indices \(ia_{k+1}\) and \(0\) otherwise, the optimal cost from node \(i\) to node \(j\) is exactly the number of descents in the subarray \(a[i\dots j]\). In other words, if we define \[ \text{descent}(k)=\begin{cases}1,&\text{if }a_k>a_{k+1}\\0,&\text{otherwise}\end{cases},\, \text{for } 1\leq k<n, \] then for any query with \(L=\min(x,y)\) and \(R=\max(x,y)\), the answer is \[ \sum_{k=L}^{R-1} \text{descent}(k) \,. \]

Your task is to answer all the queries efficiently.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (2 \le n \le 10^5,\; 1 \le q \le 10^5)\), representing the number of nodes (and the size of the permutation) and the number of queries, respectively.

The second line contains \(n\) distinct integers \(a_1, a_2, \dots, a_n\), which form a permutation of \(\{1, 2, \dots, n\}\).

Each of the next \(q\) lines contains two integers \(x\) and \(y\) \((1 \le x,y \le n)\) representing a query. Note that if \(x > y\), the subarray considered is \(a[y]\) through \(a[x]\).

outputFormat

For each query, output a single integer representing the shortest path (i.e. minimal sum of inversion counts along the chosen edges) between node \(x\) and node \(y\>.

sample

3 3
3 1 2
1 3
1 2
2 3

1
1
0