题目描述

对于一个序列 $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$。