12861번 - 죄수에게 주는 뇌물

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

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

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

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

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

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