스카이라인

도시에 멋진 스카이라인을 만들려고 한다. 일직선 위에 고층 건물 $N$개를 세우기로 했고, $i$번 건물은 층수가 정확히 $h_i$가 되어야 한다.

건설 회사 세 곳에서 서로 다른 조건을 제시했다. 첫째 회사는 원하는 건물 하나에 한 층을 올려 주고 300만 유로를 받는다. 둘째 회사는 이웃한 두 건물을 골라 각각 한 층씩, 모두 두 층을 올려 주고 500만 유로를 받는다. 이때 두 층의 높이가 같을 필요는 없다. 셋째 회사는 연속한 세 건물을 골라 각각 한 층씩, 모두 세 층을 올려 주고 700만 유로를 받는다.

공사 순서는 마음대로 정할 수 있다. 모든 건물을 목표 층수로 완성하는 데 드는 최소 비용을 구하시오.

첫째 줄에 건물의 개수 $N$이 주어진다. ($1 \le N \le 300$)

둘째 줄에 $h_1, h_2, \dots, h_N$이 공백으로 구분되어 주어진다. ($1 \le h_i \le 200$)

최소 비용을 백만 유로 단위의 정수 하나로 출력한다.