이런! 멀린의 수수께끼 중 하나에 낮은 평점을 매긴 당신에게, 멀린이 복수로 자신의 마법 던전에 가둬버렸습니다! 이 던전은 원형으로 모델링할 수 있으며, 원의 둘레를 따라 $n$개의 방이 배치되어 있습니다. 방들은 시계 방향으로 $1$부터 $n$까지 번호가 매겨져 있습니다.
당신은 방 $1$에서 시작하며, 어떤 방에 출구가 있다는 것을 알고 있습니다. 출구가 있는 방에 도달하기 위해, 인접한 방으로 시계 방향 또는 반시계 방향으로 이동할 수 있습니다. 하지만 멀린은 영리합니다. 당신의 탈출을 방해하기 위해, 멀린은 인접한 두 방을 연결하는 여러 복도에 나무 상자를 놓아 두었습니다. 복도를 지나가려면, 그 복도를 막고 있는 나무 상자를 모두 부숴야 합니다.
당신은 최대한 빨리 출구가 있는 방에 도달하고 싶습니다. 탈출하기 위해 부숴야 하는 상자의 최소 개수는 얼마입니까?
그림 1: 예제의 설명.
입력
첫째 줄에 세 정수 $n$, $x$, $m$ ($2 \le n \le 1\,000$, $1 \le x \le n$, $0 \le m \le 1\,000$)이 주어진다. 이는 $n$개의 방이 있고 방 $x$가 출구이며, 상자가 $m$개 있음을 의미한다.
다음 $m$개의 줄 각각에는 정수 $r$ ($1 \le r \le n$)이 하나씩 주어지며, 이는 방 $r$에서 원의 둘레를 따라 시계 방향으로 다음 방 사이의 복도에 상자가 하나 있음을 나타낸다. $r = n$인 경우, 방 $n$과 방 $1$ 사이의 복도에 상자가 있음을 의미한다. 이 정수들은 중복될 수 있으며, 이는 같은 복도에 여러 상자가 놓여 있음을 뜻한다.
hanzch 8달 전 3
Breakout
문제
이런! 멀린의 수수께끼 중 하나에 낮은 평점을 매긴 당신에게, 멀린이 복수로 자신의 마법 던전에 가둬버렸습니다! 이 던전은 원형으로 모델링할 수 있으며, 원의 둘레를 따라 $n$개의 방이 배치되어 있습니다. 방들은 시계 방향으로 $1$부터 $n$까지 번호가 매겨져 있습니다.
당신은 방 $1$에서 시작하며, 어떤 방에 출구가 있다는 것을 알고 있습니다. 출구가 있는 방에 도달하기 위해, 인접한 방으로 시계 방향 또는 반시계 방향으로 이동할 수 있습니다. 하지만 멀린은 영리합니다. 당신의 탈출을 방해하기 위해, 멀린은 인접한 두 방을 연결하는 여러 복도에 나무 상자를 놓아 두었습니다. 복도를 지나가려면, 그 복도를 막고 있는 나무 상자를 모두 부숴야 합니다.
당신은 최대한 빨리 출구가 있는 방에 도달하고 싶습니다. 탈출하기 위해 부숴야 하는 상자의 최소 개수는 얼마입니까?
입력
첫째 줄에 세 정수 $n$, $x$, $m$ ($2 \le n \le 1\,000$, $1 \le x \le n$, $0 \le m \le 1\,000$)이 주어진다. 이는 $n$개의 방이 있고 방 $x$가 출구이며, 상자가 $m$개 있음을 의미한다.
다음 $m$개의 줄 각각에는 정수 $r$ ($1 \le r \le n$)이 하나씩 주어지며, 이는 방 $r$에서 원의 둘레를 따라 시계 방향으로 다음 방 사이의 복도에 상자가 하나 있음을 나타낸다. $r = n$인 경우, 방 $n$과 방 $1$ 사이의 복도에 상자가 있음을 의미한다. 이 정수들은 중복될 수 있으며, 이는 같은 복도에 여러 상자가 놓여 있음을 뜻한다.
출력
탈출하기 위해 부숴야 하는 상자의 최소 개수를 하나의 정수로 출력한다.
예제
예제 입력 1
예제 출력 1