hanzch   8달 전

Breakout

시간 제한 메모리 제한
1 초 2048 MB

문제

이런! 멀린의 수수께끼 중 하나에 낮은 평점을 매긴 당신에게, 멀린이 복수로 자신의 마법 던전에 가둬버렸습니다! 이 던전은 원형으로 모델링할 수 있으며, 원의 둘레를 따라 $n$개의 방이 배치되어 있습니다. 방들은 시계 방향으로 $1$부터 $n$까지 번호가 매겨져 있습니다.

당신은 방 $1$에서 시작하며, 어떤 방에 출구가 있다는 것을 알고 있습니다. 출구가 있는 방에 도달하기 위해, 인접한 방으로 시계 방향 또는 반시계 방향으로 이동할 수 있습니다. 하지만 멀린은 영리합니다. 당신의 탈출을 방해하기 위해, 멀린은 인접한 두 방을 연결하는 여러 복도에 나무 상자를 놓아 두었습니다. 복도를 지나가려면, 그 복도를 막고 있는 나무 상자를 모두 부숴야 합니다.

당신은 최대한 빨리 출구가 있는 방에 도달하고 싶습니다. 탈출하기 위해 부숴야 하는 상자의 최소 개수는 얼마입니까?

preview그림 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

8 4 5
2
6
3
2
8
복사

예제 출력 1

2
복사

댓글을 작성하려면 로그인해야 합니다.