자리 배치하기

학생 n명이 일렬로 놓인 책상에 앉아 있고, 각 학생에게는 점수가 있다. 자리 배치가 올바르려면 점수를 오름차순으로 나열한 뒤 그 배열을 원형으로 회전한 형태여야 한다. 점수가 같은 학생들은 서로 이웃해 있으면 되며, 같은 점수의 학생끼리는 순서를 구분하지 않는다.

예를 들어 점수 배열이 {10 20 20 30}일 때 {10 20 20 30}, {20 20 30 10}, {20 30 10 20}, {30 10 20 20}은 모두 올바른 자리 배치이다. 그러나 {30 20 20 10}은 오름차순 배열의 회전이 아니므로 올바른 자리 배치가 아니다.

채점 결과가 늦게 나와 학생들이 모두 자러 간 뒤에야 다음 날의 자리 배치를 정할 수 있게 되었다. 조교는 학생들이 쓰는 컴퓨터를 옮겨 올바른 자리 배치를 만들려고 한다.

조교는 팔이 두 개뿐이므로 한 번에 최대 두 대의 컴퓨터를 들 수 있다. 컴퓨터를 들고 한 칸 이동할 때 드는 힘은 들고 있는 컴퓨터의 대수와 같다. 또한 컴퓨터 한 대를 자리에서 들어 올릴 때 10, 자리에 내려놓을 때 10의 힘이 든다.

현재 자리의 점수가 주어질 때, 올바른 자리 배치를 만들기 위해 필요한 최소 힘을 구하시오.

첫째 줄에 학생의 수 n이 주어진다. (2 <= n <= 400)

둘째 줄에 현재 자리 순서대로 각 학생의 점수가 주어진다. 각 점수는 2,000,000 이하의 양의 정수이다.

올바른 자리 배치를 만들기 위해 필요한 최소 힘을 출력한다.