우주 산책

우주 비행사 Gustav은(는) $n$개의 모듈이 원형으로 이어진 우주 정거장에서 근무한다. 모듈 $1$은(는) 모듈 $2$과(와), $2$은(는) $3$과(와) 연결되는 식이다(그리고 모듈 $n$은(는) 모듈 $1$과(와) 연결된다). 서로 이웃한 두 모듈 사이의 거리는 $1$이다. 일종의 인공 중력을 만들기 위해 우주 정거장은 원의 중심점을 기준으로 일정한 속도로 회전한다.

정거장은 꽤 오랫동안 우주에 있었으며, 이제 창문 바깥쪽을 닦을 때가 되었다. 제비뽑기 결과 Gustav이(가) 이 일을 맡게 되었다. 창문은 $1$부터 $m$까지 번호가 매겨진 $m$개이며, $i$번 창문은 $a_i$번 모듈에 있다. 어떤 이유에서인지 창문은 반드시 바로 이 순서대로 닦아야 한다. 정거장의 유일한 출입구는 모듈 $1$에 있다.

모듈 사이를 이동하기 위해 정거장 외부를 따라 움직이는 로켓 추진식 창문 승강기가 있다. 창문 승강기는 서로 이웃한 모듈 사이에서만 이동할 수 있으므로 지름길로 갈 수 없다. Gustav은(는) 모듈 $1$에서 출발해 모든 창문을 차례로 거친 뒤 모듈 $1$로 돌아오는 경로를 선택하려 한다. 안타깝게도 두 가지 문제가 있다. 우선 승강기의 연료가 제한되어 있으므로 Gustav은(는) 이동 거리를 최소화하는 경로를 선택해야 한다. 또한 승강기의 움직임은 우주 정거장의 회전에 영향을 주므로, 승강기는 시계 방향과 반시계 방향으로 같은 거리만큼 이동해야 한다.

Gustav이(가) 모듈 $1$에서 출발하여 모든 창문을 올바른 순서로 방문하고, 모듈 $1$로 돌아오며, 반시계 방향과 시계 방향으로 같은 거리만큼 이동할 때 가능한 최소 이동 거리를 구한다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$10$| $3 \le n \le 10$ , $1 \le m \le 10$

$2$ |$24$| $3 \le n \le 100$ , $1 \le m \le 100$

$3$ |$19$| $1 \le m \le 1000$

$4$ |$47$| 추가 제한 없음

첫째 줄에 모듈의 수와 창문의 수를 나타내는 두 정수 $n$와(과) $m$이(가) 주어진다($3 \leq n \leq 10^5$ , $1 \leq m \leq 10^5$). 둘째 줄에는 닦아야 할 창문의 인덱스를 나타내는 $m$개의 정수가 주어진다($1 \leq a_i \leq n$).

가능한 최소 거리를 나타내는 정수 하나를 출력한다.

여기서 최적의 이동 경로는 $1-2^*-3-4^*-3^*-4-5-6^*-5-4-3-2-1$이다(별표는 창문을 닦는다는 뜻이다).

이 예제에서는 먼저 모듈 $1$에 창문이 하나 있으며, Gustav은(는) 아무 데도 이동할 필요 없이 이 창문을 닦을 수 있다. 그런 다음 모듈 2로 이동하여 그곳에 있는 창문 세 개를 닦고 돌아온다.