TopCoder

User's AC Ratio

100.0% (29/29)

Submission's AC Ratio

31.5% (76/241)

Tags

Description

Dice Wars是一款兼具謀略和運氣的遊戲。

遊戲中你扮演紫色的骰子,要攻下其他顏色的骰子的城池,進而統一全地圖。

如今你選到了一張看起來不錯的地圖--整張地圖呈一條直線,每個位置都有一個顏色勢力佔領。

由於每次移動到相鄰異色的城池都必須經歷一場鏖戰,你想先經過程式計算後再進行遊戲。

你想要每次詢問一個顏色對(S, T),問從任何一個S的城池到任一個T的城池至少要經過幾場戰鬥。

如果S或T已經滅亡(地圖中沒有任何一個該勢力),就輸出-1。

Input Format

輸入第一行有兩個數字N, M。表示地圖共有N格、接下來有M個詢問。

接下來一行有N個以空白隔開的數字Ci表示佔領第i個位置的顏色勢力。

接下來會有M行,每行兩個正整數S, T,表示每次詢問。

1 <= N, M <= 60000
1 <= Ci, S, T <= N

Output Format

輸出會有M行,每行包含一個整數Ai表示對第i個詢問的回答。

Sample Input

7 4
2 2 1 1 2 2 3
1 2
1 3
1 1
2 4

Sample Output

1
3
0
-1

Hints

第一個詢問是問從勢力1到勢力2要經過幾次戰鬥。
最近的就是從位置3的勢力1到位置2的勢力2,經過1場戰鬥(打下位置2)

第二個詢問是問從1到3要經過幾次戰鬥。
最近的就是從位置4的勢力1到位置7的勢力3,經過3場戰鬥(打下位置5、6、7)

第三個詢問是問從1到1要經過幾次戰鬥。
所以是0場。

第四個詢問中,因為地圖上沒有4所以輸出-1。

Problem Source

原TIOJ1726 / Problem Setter : ATP

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10