t3

【题目描述】

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

有一个长度为n 的姿态序列 a_1,a_2,……,a_n（1⩽ a_i⩽ 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

【样例说明】

样例1第1问解释：

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

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

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

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

【数据规模与约定】

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

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

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

大样例

【来源】

核桃编程