Inversion Pair

对于一个序列 $p$，我们定义：$p$ 中的逆序对个数为 $\mathrm{W}(p)$。 注：这里的逆序对即为满足 $p_i>p_j$ 且 $i<j$ 的一对数。 现在，给定一个序列 $a$，其为整数 $1\sim n$ 的排列。也就是说，对于任意的 $1\le i\le n$，都有 $1\le a_i\le n$，$a_i$ 均为整数且互不相同。 现有一张图，上有 $n$ 个节点，编号为整数 $1\sim n$。对于任意的两个编号为 $i,j(1\le i< j\le n)$ 的节点，我们将在它们之间连一条权值为 $\mathrm{W}([a_i,a_{i+1},\dots,a_{j-1},a_j])$ 的无向边。 现有 $q$ 次询问。每次询问给出两个编号为 $x,y$ 节点，求它们之间的最短路径。

第一行两个整数 $n,q$。 第二行 $n$ 整数表示序列 $a$。 接下来 $q$ 行，每行两个整数表示一次询问的 $x,y$。

对于每一次询问： 一个整数表示所求的最短路径。

3 2
3 1 2
1 3
2 2

1
0

对于全部数据，保证：$2\le n\le 3\times 10^5$，$1\le q\le 3\times 10^5$，$1\le x,y\le n$。 | $\text{Subtask}$ | $n\le$ | $q\le$ | 分数 | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | $0$ | $100$ | $100$ | $30$ | 无 | | $1$ | $3\times 10^5$ | $3\times 10^5$ | $70$ | 无 |