Make Different

원형 게임판에 $N$개의 스프링이 있다. 스프링은 시계 방향으로 $1$번 부터 $N$번 까지 번호가 붙어 있다. 각 스프링은 빨간색 또는 파란색으로 칠해져 있는데, 빨간 스프링을 밟으면 바로 양옆에 있는 스프링으로 점프할 수 있으며 파란 스프링을 밟으면 양옆으로 두 칸 거리에 있는 스프링으로 점프할 수 있다.

그림 L.1: 두 로봇이 1번과 6번 스프링에 있고, 반시계 방향 점프 명령을 한 경우 로봇의 움직임

당신은 두 로봇을 이용하여 게임을 할 것이다. 우선 게임판에 두 로봇을 서로 다른 번호의 스프링 위에 놓는다. 당신은 로봇들에게 시계 방향 또는 반시계 방향으로 움직이라고 명령할 수 있다. 명령을 내리면 두 로봇이 동시에 당신이 명령한 방향으로 점프한다. 즉 로봇을 하나만 움직이거나 두 로봇이 다른 방향으로 점프하도록 할 수는 없다.

게임은 두 로봇이 서로 다른 색깔 스프링을 밟으면 끝난다. 로봇의 시작 위치가 주어지면 게임을 끝내기 위해 필요한 최소 명령 수를 구하여라.

첫 번째 줄에 스프링의 수 $N$($3 \leq N \leq 100\ 000$)과 질문의 수 $Q$($1 \leq Q \leq 100\ 000$)가 주어진다.

두 번째 줄에 스프링의 종류가 $1$번 스프링부터 $N$번 스프링까지 순서대로 주어진다. 빨간 스프링은 $1$, 파란 스프링은 $2$이다.

세 번째 줄부터 $Q$개의 줄에는 두 로봇이 게임을 시작할 스프링의 번호 $R1$, $R2$가 주어진다. ($1 \leq R1, R2 \leq N$, $R1 \neq R2$)

$Q$개의 줄에 걸쳐 두 로봇이 다른 색깔 스프링에 위치하기 위해 필요한 최소 명령 수를 출력한다. 처음부터 두 로봇이 다른 색깔 스프링에 있었으면 0을, 아무리 명령하더라도 두 로봇이 다른 색깔 스프링에 있게 할 수 없다면 -1을 출력한다.