题目描述

给定一张纸条，纸条上依次有 $n$ 个格子，第 $i$ 个格子的颜色是 $a_i$。

现在小 A 每秒钟可以进行以下两种操作之一。

将某个格子染成一种颜色。

移动到相邻的格子，前提要求移动前和移动后的两个格子的颜色相同。

现在小 A 想在纸条上移动，但是他不想花费太多时间，所以他会询问你 $Q$ 个问题。第 $i$ 个问题是从格子 $u_i$ 移动到 $v_i$ 最少需要的时间。

注意，每个问题之间是独立的，意味着不需要真正对纸条进行染色。

输入格式

第一行两个正整数 $n, Q$ 分别表示纸条长度和询问次数。

接下来一行 $n$ 个正整数，第 $i$ 个数表示纸条上第 $i$ 个格子的颜色 $a_i$。

接下来 $Q$ 行，每行两个正整数 $u_i,v_i$，表示询问从 $u_i$ 到 $v_i$ 的最少时间秒数。

输出格式

输出 $Q$ 行，每行一个整数表示对应询问的答案。

样例输入 #1

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

样例输出 #1

6
4
5
0

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le u_i,v_i\le n\le 10^6,1\le Q\le 10^6,1\le a_i\le m\le n$。

对于子任务 $1$（$3 $分），保证 $n\le 10^4,Q,m\le 100$。

对于子任务 $2$（$13$ 分），保证 $n,Q\le 10^5,m\le 3$。

对于子任务 $3$（$18$ 分），保证 $n,Q\le 5000$。

对于子任务 $4$（$66$ 分），无特殊限制。