관측 자료 묶음 청구

문제

한 날씨 관측소는 외부 사용자가 요청한 관측 자료를 시간 구간별 파일로 제공한다. 백엔드 담당자는 한 사용자의 자료 이용 내역을 받아 최종 청구액을 계산해야 한다. 이용 내역에는 시간순으로 정렬된 N개의 항목이 있으며, i번째 항목의 기본요금은 A_i원이다. 모든 항목은 반드시 제공해야 하므로, 요금을 줄이기 위해 항목을 삭제하거나 순서를 바꿀 수는 없다. 관측소는 인접한 두 항목을 하나의 묶음으로 처리할 때 할인을 제공한다. 원래 이용 내역에서 번호가 연속한 i번 항목과 i+1번 항목을 묶으면, 두 기본요금 중 작은 금액만큼 할인받는다. 따라서 이 묶음의 할인 후 요금은 두 기본요금 중 큰 금액과 같다. 두 기본요금이 같아도 같은 규칙을 적용하며, 기본요금이 0원인 항목도 묶음에 넣을 수 있다. 하나의 항목은 최대 하나의 묶음에만 포함될 수 있다. 예를 들어 2번과 3번을 묶었다면 1번과 2번 또는 3번과 4번을 추가로 묶을 수 없다. 다만 4번과 5번을 추가로 묶는 것은 가능하다. 묶음을 여러 개 선택하거나 하나도 선택하지 않을 수 있으며, 묶음에 포함되지 않은 항목에는 기본요금이 그대로 부과된다. 다른 묶음을 선택한 뒤 남은 항목들이 서로 이웃하게 되더라도, 원래 번호가 연속하지 않았다면 새 묶음으로 만들 수 없다. 세금은 항목별이나 묶음별로 계산하지 않는다. 먼저 모든 기본요금의 합에서 선택한 묶음들의 할인액을 뺀 금액을 B원이라고 한다. 전체 이용 내역에 대한 세금은 B를 10으로 나눈 몫이며, 나머지는 버린다. 최종 청구액은 B와 이 세금의 합이다. 이 문제에서는 이 규칙 외의 할인이나 추가 요금은 없다. 이용 내역이 주어졌을 때 가능한 최종 청구액 중 최솟값을 구한다. 최솟값을 만드는 묶음 선택이 여러 가지여도 청구액만 출력한다.

입력

첫째 줄에 항목의 개수 N이 주어진다.
둘째 줄에 기본요금 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 200,000, 0 ≤ A_i ≤ 1,000,000이다.

출력

가능한 최종 청구액의 최솟값을 원 단위의 정수 하나로 출력한다. 묶음을 선택할 수 없는 경우에도 같은 계산 규칙을 적용한다.

4
8 5 7 9

18

3
6 10 10

17

1
0

0

출처: Devin.KR 자체 제작