409929: GYM103855 L Make Different

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Make Differenttime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

There are $$$N$$$ springs on a circular game board. There are two types of springs: red springs and blue springs. When the robot steps on a red spring, it can jump one spring left or right. When the robot steps on a blue spring, it can jump two springs left or right.

The case when the two robots are on springs 1 and 6 respectively, and a counterclockwise jump command is given.

You will play a game using two robots. In the beginning, you will place the two robots on different springs on the board. You can then issue a direction - either clockwise or counterclockwise. Both robots will jump simultaneously in the direction you command. The game ends when the robots step on springs of different colors.

You are given $$$Q$$$ queries. Each query contains the starting springs of the two robots. For each query, find the minimum number of commands needed to finish the game.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$3 \leq N \leq 100\,000$$$, $$$1 \leq Q \leq 100\,000 $$$).

The next line contains $$$N$$$ integers, the $$$i$$$-th integer denoting the type of spring $$$i$$$. Red springs are denoted by a $$$1$$$ and blue springs are denoted by a $$$2$$$.

The next $$$Q$$$ lines each contain two integers $$$p_1$$$ and $$$p_2$$$ denoting the positions at which the two robots will start the game ($$$1 \leq p_1, p_2 \leq N$$$, $$$p_1 \neq p_2$$$).

Output

Output $$$Q$$$ lines. On the $$$i$$$-th line, output a single integer denoting the minimum number of commands required to get the two robots to land on different colored springs for the $$$i$$$-th query. If it is impossible to get the robots to land on different colored springs, output -1.

ExampleInput
8 3
1 2 2 2 1 2 1 2
1 2
1 5
3 6
Output
0
-1
1

加入题单

上一题 下一题 算法标签: