Denisson 是一位俄罗斯套娃的忠实爱好者。一套套娃由一个木制人偶组成，它可以从中间上下分开，露出里面一个同样种类但更小的套娃，而那个套娃里面又套着另一个套娃，以此类推。

最近他买了一套这样的玩具，并以某种顺序将它们摆放在桌子上。他的这套玩具中恰好有 $n$ 个大小不同的套娃，因此套娃当前的排列顺序可以用一个长度为 $n$ 的排列 $p$ 来表示，其中 $p_i$ 等于第 $i$ 个套娃的大小。

Denisson 平时的日程安排非常紧凑，但今天他想用这些玩具放松一下，并进行以下游戏：

• 首先，他会选择套娃排列中的某个区间 $[l, r]$；
• 然后，他会取出该区间内最小的套娃，并将其放入下一个大小的套娃中。执行此操作所需的时间等于 $|i - j|$，其中 $p_i$ 和 $p_j$ 是所选区间内两个最小套娃的大小；
• 他会重复此操作，直到区间内只剩下一个套娃。游戏所需的总时间是所有执行步骤所需时间之和。

突然，他意识到这个有趣的游戏可能会持续很长时间，但他非常在意自己的日程安排。他带着 $q$ 个不同的区间 $[l_i, r_i]$ 来找你，想知道在每个区间上进行游戏所需的时间。他希望你计算这些时间时不要花费太长时间。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 套娃的数量和询问的数量 ($1 \le n \le 10^5$, $1 \le q \le 5 \cdot 10^5$)。

第二行描述了套娃的排列顺序 $p$ ($1 \le p_i \le n$)。

接下来的 $q$ 行描述了收到的询问。每个询问由两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$) 描述，即第 $i$ 个区间的端点。

输出格式

对于第 $i$ 个询问，输出在区间 $[l_i, r_i]$ 上进行游戏所需的总时间。

样例

输入 1

5 5
1 5 2 4 3
1 5
1 4
1 3
1 2
1 1

输出 1

7
5
3
1
0