시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 3 3 75.000%

문제

월드 학원 캠프 때에는 학생들의 성적순으로 자리를 배치한다. n명의 학생들은 직선으로 배치된 책상에 앉아 있는데, 각 학생들은 점수가 오름차순으로 배치되어 있다. 점수가 같은 학생들은 붙어 있다.

단, 자리를 배치할 때 전체적인 순서보다도 각 학생의 양옆에 앉게 되는 학생을 중요하게 따지기로 한다. 따라서 {10 20 20 30} 뿐만 아니라 {20 20 30 10}, {20 30 10 20}, {30 10 20 20}도 모두 학생들이 성적순으로 앉은 것이다. 하지만 성적이 오름차순으로 배열되므로 {30 20 20 10}과 같은 경우는 성적순으로 앉은 것이 아니다. 즉, 학생들을 성적으로 오름차순으로 배열하되, 이를 회전하는 경우도 허용하는 것이다.

오늘 하루도 학생들은 열심히 공부를 하였다. 그리고 성적에 따라 내일의 자리 배치를 하려 했는데, 그만 한 문제의 채점이 늦어지는 바람에 모든 학생들이 자러 간 뒤에야 채점 결과가 나왔다. 그래서 조교가 학생들의 자리를 배치해 주기로 했다.

조교는 물론 팔이 두 개밖에 없으므로 한 번에 최대 두 대까지의 컴퓨터만 들 수 있다. 컴퓨터를 들고 한 칸을 이동할 때에는 들고 있는 컴퓨터의 개수만큼 힘이 든다. 또, 컴퓨터 한 대를 자리에서 들어 올리거나, 자리에 놓을 때에는 10만큼의 힘이 든다.

학생들의 성적이 주어졌을 때, 성적순으로 자리배치 할 때 드는 최소의 힘을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 n(2≤n≤400)이 주어진다. 다음 줄에는 각 학생의 점수가 주어진다. 각 학생의 점수는 2,000,000을 넘지 않는 정수이다. 범위가 큰 이유는 소수로 나타나는 학생의 점수를 정수화하기 위해서 적당한 수를 곱했기 때문이다.

출력

첫째 줄에 드는 최소의 힘을 출력한다.

예제 입력

5
5 2 7 4 2

예제 출력

66

힌트