32946번 - 오코노미야키 만들기

문제

일본어 시험이 끝난 뒤 요리 고수 대곽이는 친구들과 같이 오코노미야키를 만들고 있다.

대곽이가 요리에 쓰는 프라이팬은 $N$개의 정사각형 모양의 칸이 한 줄로 붙어 있는 모양이며, 맨 왼쪽 1ドル$번 칸부터 맨 오른쪽 $N$번 칸까지 번호가 붙어 있다. 오코노미야키 반죽은 두 면이 있는 원판 모양이며, 한쪽 면은 잘 익은 면이고, 반대쪽 면은 덜 익은 면이다. 처음에는 오코노미야키 반죽 2ドル$개가 프라이팬의 서로 다른 칸에 놓여 있으며, 각 반죽의 잘 익은 면이 바닥에 닿아 있고 덜 익은 면이 위로 향해 있다. 그리고 오코노미야키 반죽이 놓여 있지 않은 1ドル$개의 칸에 고기 한 덩이가 놓여 있다.

대곽이는 오코노미야키 반죽 하나를 선택한 뒤, 선택한 반죽이 위치한 칸에 인접한 칸 중 하나를 선택한 후 선택한 칸으로 반죽을 뒤집는다. 양의 정수 $x (1 \leq x \leq N)$에 대하여, $x$번 칸에 인접한 칸은 $x = 1$인 경우 2ドル$번 칸, $x = N$인 경우 $N - 1$번 칸, 2ドル \leq x \leq N-1$인 경우 $x-1$번과 $x+1$번 칸을 의미한다. 이때, 다른 반죽이 이미 자리 잡고 있는 칸은 선택할 수 없다. 뒤집을 때마다 다음과 같은 변화가 일어난다:

• 선택한 반죽의 위치가 선택한 칸으로 옮겨진다.
• 선택한 반죽의 바닥에 닿은 면과 위로 향해 있는 면이 바뀐다.
• 선택한 칸에 고기가 있었을 경우 프라이팬과 반죽의 덜 익은 면이 맞닿게 된다면, 반죽에 고기가 붙게 되며, 다음에 이 반죽을 뒤집을 때 고기는 계속 반죽과 함께 이동하게 된다.
• 선택한 칸에 고기가 있었을 경우 프라이팬과 반죽의 잘 익은 면이 맞닿는다면 반죽에 고기가 붙지 않고, 다음에 이 반죽을 뒤집을 때 고기는 반죽과 함께 이동하지 않고 원래 자리에 그대로 있는다.

대곽이의 목표는 반죽 2ドル$개 중 하나에 고기가 붙어 있으며, 고기가 붙은 반죽이 자신이 원하는 칸에 위치하도록 하는 것이다. 이때, 고기가 붙지 않은 반죽은 어느 칸에 있어도 관계가 없으며, 두 반죽의 어떤 면이 위로 올라와 있든지 관계없다. 대곽이가 목표를 달성할 수 있는지, 그리고 그러기 위해 최소 몇 번의 뒤집기가 필요한지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 프라이팬의 칸의 개수를 나타내는 정수 $N$이 주어진다. $(3 \leq N \leq 1 ,円 000 ,円 000)$

둘째 줄에 오코노미야키 반죽들이 처음에 존재하는 칸의 번호를 나타내는 양의 정수 $p_1$과 $p_2$가 공백으로 구분되어 주어진다. $(1 \leq p_1 < p_2 \leq N)$

셋째 줄에 고기가 처음에 존재하는 칸의 번호를 나타내는 양의 정수 $M$이 주어진다. $(1 \leq M \leq N;$ $M \ne p_1;$ $M \ne p_2)$

넷째 줄에 뒤집기가 모두 끝난 후 고기가 붙은 오코노미야키 반죽이 위치해야 하는 칸의 번호를 나타내는 정수 $S$가 주어진다. $(1 \leq S \leq N)$

출력

대곽이가 목표를 달성할 수 있으면 필요한 최소 뒤집기 횟수를 한 줄에 출력한다. 만약 불가능하다면 그 대신 -1을 한 줄에 출력한다.

제한

노트