모자 걸이

모자를 여러 개 가지고 있는데, 어떤 모자는 다른 모자보다 더 자주 쓴다. n개를 한꺼번에 쓸 수는 없으니 남는 모자는 걸이가 n − 1개인 걸이대에 둔다. 첫 번째 걸이는 문에서 0.5미터, 두 번째는 1미터, 세 번째는 1.5미터 떨어져 있는 식이다. 따라서 문에서 i번째 걸이까지 걸어갔다 오려면 i미터를 걸어야 한다.

오늘 밤에는 여러 차례 공개적으로 등장하는데, 매번 역할에 맞는 모자를 쓴다. 한 번의 일정을 마치고 돌아오면 필요한 모자를 걸이에서 꺼내고, 그 전까지 쓰고 있던 모자와 바꿔 건다. 따라서 밤이 진행되는 동안 모자가 옮겨 다닐 수 있다.

오늘 밤의 계획이 주어지고, 이미 첫 번째 모자를 쓰고 있다고 할 때, 걸어야 하는 미터 수를 최소화하려면 출발 전에 모자를 걸이대에 어떻게 배치해야 하는가?

• 입력의 첫 줄에는 정수 c와 n (1 ≤ c, n ≤ 105)이 주어진다. 각각 모자의 총 개수와 일정의 길이이다.
• 입력의 둘째 줄에는 정수 n개 v1 … vn (1 ≤ v ≤ c; v[i] ≠ v[i − 1])이 주어진다. 써야 하는 모자의 순서이다. 첫 번째 모자는 이미 쓰고 있고, 같은 모자를 연달아 쓸 일은 없다.

걸이대를 최적으로 배치했을 때 걸어야 하는 최소 미터 수를 출력한다.

이어서, 최소 이동 거리를 주는 걸이대의 초기 배치를 1번 자리부터 시작해 c − 1개의 정수로 출력한다. 이 배치에는 첫 번째 모자를 제외한 모든 모자가 정확히 한 번씩 들어가야 한다.

정답이 여러 개라면 그중 아무거나 출력해도 된다.