题目描述
给定一张纸条,纸条上依次有 n 个格子,第 i 个格子的颜色是 ai。
现在小 A 每秒钟可以进行以下两种操作之一。
将某个格子染成一种颜色。
移动到相邻的格子,前提要求移动前和移动后的两个格子的颜色相同。
现在小 A 想在纸条上移动,但是他不想花费太多时间,所以他会询问你 Q 个问题。第 i 个问题是从格子 ui 移动到 vi 最少需要的时间。
注意,每个问题之间是独立的,意味着不需要真正对纸条进行染色。
输入格式
第一行两个正整数 n,Q 分别表示纸条长度和询问次数。
接下来一行 n 个正整数,第 i 个数表示纸条上第 i 个格子的颜色 ai。
接下来 Q 行,每行两个正整数 ui,vi,表示询问从 ui 到 vi 的最少时间秒数。
输出格式
输出 Q 行,每行一个整数表示对应询问的答案。
样例输入 #1
5 4 2 2 3 1 3 1 5 2 4 5 2 3 3
样例输出 #1
6 4 5 0
数据范围与约定
对于 100% 的数据,保证 1≤ui,vi≤n≤106,1≤Q≤106,1≤ai≤m≤n。
对于子任务 1(3分),保证 n≤104,Q,m≤100。
对于子任务 2(13 分),保证 n,Q≤105,m≤3。
对于子任务 3(18 分),保证 n,Q≤5000。
对于子任务 4(66 分),无特殊限制。