题目描述
给定一张纸条，纸条上依次有 $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$ 分），无特殊限制。