题目描述

观者找到了很多尖塔 mod，现在她有很多种姿态！

有一个长度为 $n$ 的姿态序列 $a_1,a_2,\cdots,a_n$（$1\leqslant a_i\leqslant n$），观者可以在这个姿态序列上行走，每次在 $i$ 可以走到 $i-1$（若 $i>1$）或者 $i+1$（若 $i<n$），

但行走是有条件的。假设是从 $i$ 走到 $i+1$ 她必须保证 $i$ 与 $i+1$ 的姿态相同，$i$ 走到 $i-1$ 同理要保证 $i$ 与 $i-1$ 的姿态相同。观者可以使用一单位的能量来将姿态序列某个位置改为一种任意的姿态，行走也需要一单位的能量。

她设想了 $m$ 个问题，每次给定起点终点 $x,y$（$x$ 可以大于 $y$），她想知道从 $x$ 走到 $y$ 最少需要多少单位的能量？由于这只是观者的设想，事实上她不会真正地修改这个姿态序列。

输入格式

第一行两个正整数 $n,m$，表示序列长度与询问个数。

第二行 $n$ 个正整数，表示姿态序列上每个位置的姿态。

接下来 $m$ 行，每行两个正整数 $x,y$ 表示起点与终点，注意 $x$ 可以大于 $y$。

输出格式

$m$ 行每行一个非负整数表示答案。

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

6
5
4
0

数据范围

对于 $100\%$ 的数据，保证 $2\leqslant n,m\leqslant 10^6,1\leqslant x_i,y_i,a_i\leqslant n$。

特殊性质 A：保证姿态数量不超过 $20$。

特殊性质 B：保证姿态数量不超过 $3$。

样例

样例

样例$1$第$1$问解释：

从$1$走到$2$，代价$1$单位能量，总代价为$1$；

从$2$走到$3$，把$a[2]$改成$2$，代价$2$单位能量，总代价为$3$；

从$3$走到$4$，把$a[4]$改成$2$，代价$2$单位能量，总代价为$5$；

从$4$走到$5$，代价$1$单位能量，总代价为$6$；