시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)6996100.000%

문제

원형 게임판에 $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을 출력한다.

예제 입력 1

8 3
1 2 2 2 1 2 1 2
1 2
1 5
3 6

예제 출력 1

0
-1
1
W3sicHJvYmxlbV9pZCI6IjIyODg0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTWFrZSBEaWZmZXJlbnQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMFx1ZDYxNSBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzJhNFx1ZDUwNFx1YjljMVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzJhNFx1ZDUwNFx1YjljMVx1Yzc0MCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjICQxJFx1YmM4OCBcdWJkODBcdWQxMzAgJE4kXHViYzg4IFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzJhNFx1ZDUwNFx1YjljMVx1Yzc0MCBcdWJlNjhcdWFjMDRcdWMwYzkgXHViNjEwXHViMjk0IFx1ZDMwY1x1Yjc4MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWNlNjBcdWQ1NzRcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwLCBcdWJlNjhcdWFjMDQgXHVjMmE0XHVkNTA0XHViOWMxXHVjNzQ0IFx1YmMxZlx1YzczY1x1YmE3NCBcdWJjMTRcdWI4NWMgXHVjNTkxXHVjNjA2XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVkMzBjXHViNzgwIFx1YzJhNFx1ZDUwNFx1YjljMVx1Yzc0NCBcdWJjMWZcdWM3M2NcdWJhNzQgXHVjNTkxXHVjNjA2XHVjNzNjXHViODVjIFx1YjQ1MCBcdWNlNzggXHVhYzcwXHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjkyZGZlNmUtZmMyMC00ODBkLThjODYtZDAyZGRkYzdhNDhjXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0ODBweDsgaGVpZ2h0OiAyODVweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHVhZGY4XHViOWJjIEwuMTogXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc3NCAxXHViYzg4XHVhY2ZjIDZcdWJjODggXHVjMmE0XHVkNTA0XHViOWMxXHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViYzE4XHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNSBcdWM4MTBcdWQ1MDQgXHViYTg1XHViODM5XHVjNzQ0IFx1ZDU1YyBcdWFjYmRcdWM2YjAgXHViODVjXHViZDA3XHVjNzU4IFx1YzZjMFx1YzljMVx1Yzc4NDxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZiMFx1YzEyMCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWMyYTRcdWQ1MDRcdWI5YzEgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1Yjg1Y1x1YmQwN1x1YjRlNFx1YzVkMFx1YWM4YyBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YjYxMFx1YjI5NCBcdWJjMThcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJhODVcdWI4MzlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYTg1XHViODM5XHVjNzQ0IFx1YjBiNFx1YjlhY1x1YmE3NCBcdWI0NTAgXHViODVjXHViZDA3XHVjNzc0IDxzdHJvbmc+XHViM2Q5XHVjMmRjXHVjNWQwPFwvc3Ryb25nPiBcdWIyZjlcdWMyZTBcdWM3NzQgXHViYTg1XHViODM5XHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NWNcdWIyZTQuIFx1Yzk4OSBcdWI4NWNcdWJkMDdcdWM3NDQgXHVkNTU4XHViMDk4XHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWM3MFx1YjA5OCBcdWI0NTAgXHViODVjXHViZDA3XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTU4XHViM2M0XHViODVkIFx1ZDU2MCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzBjOVx1YWU1NCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3NDQgXHViYzFmXHVjNzNjXHViYTc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHViODVjXHViZDA3XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWIwNWRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHViYTg1XHViODM5IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3NTggXHVjMjE4ICROJCgkIDMgXFxsZXEgTiBcXGxlcSAxMDBcXCAwMDAgJClcdWFjZmMgXHVjOWM4XHViYjM4XHVjNzU4IFx1YzIxOCAkUSQoJCAxIFxcbGVxIFEgXFxsZXEgMTAwXFwgMDAwICQpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmE0XHVkNTA0XHViOWMxXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1YWMwMCAkMSRcdWJjODggXHVjMmE0XHVkNTA0XHViOWMxXHViZDgwXHVkMTMwICROJFx1YmM4OCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTY4XHVhYzA0IFx1YzJhNFx1ZDUwNFx1YjljMVx1Yzc0MCAkMSQsIFx1ZDMwY1x1Yjc4MCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3NDAgJDIkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWI4NWNcdWJkMDdcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM3NTggXHViYzg4XHVkNjM4ICRSMSQsICRSMiRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZXEgUjEsIFIyIFxcbGVxIE4kLCAkUjEgXFxuZXEgUjIkKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YjQ1MCBcdWI4NWNcdWJkMDdcdWM3NzQgXHViMmU0XHViOTc4IFx1YzBjOVx1YWU1NCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YmE4NVx1YjgzOSBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjOThcdWM3NGNcdWJkODBcdWQxMzAgXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWIyZTRcdWI5NzggXHVjMGM5XHVhZTU0IFx1YzJhNFx1ZDUwNFx1YjljMVx1YzVkMCBcdWM3ODhcdWM1YzhcdWM3M2NcdWJhNzQgPGNvZGU+MDxcL2NvZGU+XHVjNzQ0LCBcdWM1NDRcdWJiMzRcdWI5YWMgXHViYTg1XHViODM5XHVkNTU4XHViMzU0XHViNzdjXHViM2M0IFx1YjQ1MCBcdWI4NWNcdWJkMDdcdWM3NzQgXHViMmU0XHViOTc4IFx1YzBjOVx1YWU1NCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWM1ZDAgXHVjNzg4XHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IDxjb2RlPi0xPFwvY29kZT5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIyODg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFrZSBEaWZmZXJlbnQiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSZuYnNwOyROJCZuYnNwO3NwcmluZ3Mgb24gYSBjaXJjdWxhciBnYW1lIGJvYXJkLiBUaGVyZSBhcmUgdHdvIHR5cGVzIG9mIHNwcmluZ3M6IHJlZCBzcHJpbmdzIGFuZCBibHVlIHNwcmluZ3MuIFdoZW4gdGhlIHJvYm90IHN0ZXBzIG9uIGEgcmVkIHNwcmluZywgaXQgY2FuIGp1bXAgb25lIHNwcmluZyBsZWZ0IG9yIHJpZ2h0LiBXaGVuIHRoZSByb2JvdCBzdGVwcyBvbiBhIGJsdWUgc3ByaW5nLCBpdCBjYW4ganVtcCB0d28gc3ByaW5ncyBsZWZ0IG9yIHJpZ2h0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzI5MmRmZTZlLWZjMjAtNDgwZC04Yzg2LWQwMmRkZGM3YTQ4Y1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDgwcHg7IGhlaWdodDogMjg1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxlbT5UaGUgY2FzZSB3aGVuIHRoZSB0d28gcm9ib3RzIGFyZSBvbiBzcHJpbmdzIDEgYW5kIDYgcmVzcGVjdGl2ZWx5LCBhbmQgYSBjb3VudGVyY2xvY2t3aXNlIGp1bXAgY29tbWFuZCBpcyBnaXZlbi48XC9lbT48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgcGxheSBhIGdhbWUgdXNpbmcgdHdvIHJvYm90cy4gSW4gdGhlIGJlZ2lubmluZywgeW91IHdpbGwgcGxhY2UgdGhlIHR3byByb2JvdHMgb24gZGlmZmVyZW50IHNwcmluZ3Mgb24gdGhlIGJvYXJkLiBZb3UgY2FuIHRoZW4gaXNzdWUgYSBkaXJlY3Rpb24gLSBlaXRoZXIgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2UuIEJvdGggcm9ib3RzIHdpbGwganVtcCBzaW11bHRhbmVvdXNseSBpbiB0aGUgZGlyZWN0aW9uIHlvdSBjb21tYW5kLiBUaGUgZ2FtZSBlbmRzIHdoZW4gdGhlIHJvYm90cyBzdGVwIG9uIHNwcmluZ3Mgb2YgZGlmZmVyZW50IGNvbG9ycy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiZuYnNwOyRRJCZuYnNwO3F1ZXJpZXMuIEVhY2ggcXVlcnkgY29udGFpbnMgdGhlIHN0YXJ0aW5nIHNwcmluZ3Mgb2YgdGhlIHR3byByb2JvdHMuIEZvciBlYWNoIHF1ZXJ5LCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjb21tYW5kcyBuZWVkZWQgdG8gZmluaXNoIHRoZSBnYW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzJm5ic3A7JE4kJm5ic3A7YW5kJm5ic3A7JFEkJm5ic3A7KCQzIFxcbGVxIE4gXFxsZXEgMTAwXFwsMDAwJCwmbmJzcDskMSBcXGxlcSBRIFxcbGVxIDEwMFxcLDAwMCAkKS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyZuYnNwOyROJCZuYnNwO2ludGVnZXJzLCB0aGUmbmJzcDskaSQtdGggaW50ZWdlciBkZW5vdGluZyB0aGUgdHlwZSBvZiBzcHJpbmcmbmJzcDskaSQuIFJlZCBzcHJpbmdzIGFyZSBkZW5vdGVkIGJ5IGEmbmJzcDskMSQmbmJzcDthbmQgYmx1ZSBzcHJpbmdzIGFyZSBkZW5vdGVkIGJ5IGEmbmJzcDskMiQuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0Jm5ic3A7JFEkJm5ic3A7bGluZXMgZWFjaCBjb250YWluIHR3byBpbnRlZ2VycyZuYnNwOyRwXzEkJm5ic3A7YW5kJm5ic3A7JHBfMiQmbmJzcDtkZW5vdGluZyB0aGUgcG9zaXRpb25zIGF0IHdoaWNoIHRoZSB0d28gcm9ib3RzIHdpbGwgc3RhcnQgdGhlIGdhbWUgKCQxIFxcbGVxIHBfMSwgcF8yIFxcbGVxIE4kLCZuYnNwOyRwXzEgXFxuZXEgcF8yJCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0Jm5ic3A7JFEkJm5ic3A7bGluZXMuIE9uIHRoZSZuYnNwOyRpJC10aCBsaW5lLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBkZW5vdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgY29tbWFuZHMgcmVxdWlyZWQgdG8gZ2V0IHRoZSB0d28gcm9ib3RzIHRvIGxhbmQgb24gZGlmZmVyZW50IGNvbG9yZWQgc3ByaW5ncyBmb3IgdGhlJm5ic3A7JGkkLXRoIHF1ZXJ5LiBJZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGdldCB0aGUgcm9ib3RzIHRvIGxhbmQgb24gZGlmZmVyZW50IGNvbG9yZWQgc3ByaW5ncywgb3V0cHV0Jm5ic3A7PGNvZGU+LTE8XC9jb2RlPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d