시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 46 25 19 55.882%

문제

세계적인 BOJ 감옥에는 방 P개가 1열로 늘어서 있다. 좌측 방부터 순서대로 1, 2, ... P란 번호가 붙어 있다. 모든 방은 독방으로, 각 방에 한명의 죄수가 수감되어 있다. 각각의 방 사이에는 창문이 있기 때문에, 옆방의 죄수와 이야기를 하는 것이 가능하다.

이 때 죄수가 석방이 되는 것에 대해 생각을 해 보자. 어떤 방의 죄수가 석방될 때, 그 방으로부터 정확히 한칸 떨어진 옆 방의 죄수는 그 사실을 알고 화를 내며 난동을 부린다. 따라서 어떤 방의 죄수를 석방시킬 때는 양쪽 방의 각 죄수에게 뇌물로 금화 1장을 주어야 한다. 또한 석방된 것에 대해 창문을 통해 옆방끼리 전달할 수 있기 때문에, 단지 옆방만이 아닌 전달할 수 있는 모든 죄수들에게 금화를 줄 필요가 있다.

오늘은 BOJ 캠프날. 특별히 A1A2A3...AQ 번 방에 있는 Q명의 죄수를 석방하고 싶다. 하지만 어떤 순서로 석방시켜 주냐에 따라 필요한 금화가 달라지게 된다. 가능한 방법 중 가장 금화를 적게 소비하는 경우를 찾아보자.

입력

첫 번째 줄에는 두 정수 P, Q (1 ≤ P ≤ 10,000, 1 ≤ Q ≤ 100, Q ≤ P가 공백을 구분으로 주어진다.

두 번째 줄에는 Q개의 정수 A1, A2, A3, ..., AQ가 공백을 구분으로 주어진다. 각각의 수는 석방시킬 죄수의 방 번호를 의미하며 중복되어 주어지는 경우는 없다.

출력

주어진 Q명의 죄수를 모두 석방시킬 때 드는 최소 비용을 구해 출력한다.

예제 입력 1

8 1
3

예제 출력 1

7

예제 입력 2

20 3
3 14 6

예제 출력 2

35