QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[-22]

# 5173. 染色

Statistics

题目描述

给定一张纸条,纸条上依次有 n 个格子,第 i 个格子的颜色是 ai

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

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

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

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

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

输入格式

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

接下来一行 n 个正整数,第 i 个数表示纸条上第 i 个格子的颜色 ai

接下来 Q 行,每行两个正整数 ui,vi,表示询问从 uivi 的最少时间秒数。

输出格式

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

样例输入 #1

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

样例输出 #1

6
4
5
0

数据范围与约定

对于 100% 的数据,保证 1ui,vin106,1Q106,1aimn

对于子任务 13分),保证 n104,Q,m100

对于子任务 213 分),保证 n,Q105,m3

对于子任务 318 分),保证 n,Q5000

对于子任务 466 分),无特殊限制。