앤드루의 놀라운 건축

Aaron은 블록을 많이 가지고 있고, Andrew에게 블록으로 구조물을 만들라고 했다. 모든 블록은 여러 가지 값 k에 대해 k × 1 × 1 크기이다. 구조물은 n개의 비어 있지 않은 열이 순서대로 나열된 형태여야 하며, i번째 열의 모든 블록은 hi × 1 × 1 크기이고, 지면과 평행한 1 × 1 면을 가진다. 또한 구조물은 피라미드여야 한다. 피라미드는 꼭대기 열을 포함해야 하는데, 꼭대기 열 왼쪽의 각 열 j에 대해 열 j의 높이는 열 j + 1의 높이 이하이고, 꼭대기 열 오른쪽의 각 열 k에 대해 열 k의 높이는 열 k − 1의 높이 이하이다. 예를 들어, 그림 A.1의 왼쪽 구조물은 꼭대기 열이 없으므로 피라미드가 아니고, 오른쪽 구조물은 왼쪽에서 세 번째 열이 꼭대기 열이므로 피라미드이다(왼쪽에서 네 번째 열도 마찬가지이다).

그림 A.1: (왼쪽) 피라미드가 아닌 예. (오른쪽) 피라미드인 예. 두 경우 모두 n = 8이고, 왼쪽부터 오른쪽으로 각 열의 블록 크기는 6, 8, 4, 5, 6, 4, 2, 3이다. 이 수열은 샘플 입력 3에 나온다.

물론 피라미드를 만드는 것만으로는 쉽기 때문에, Aaron은 Andrew에게 사용할 블록 크기 수열이 주어졌을 때 부피가 가장 작은 피라미드를 찾으라고 했다. Andrew를 도와 가능한 가장 작은 부피를 구하라. 각 크기의 블록은 무한히 공급된다고 가정할 수 있다.

입력의 첫 줄에는 수열의 길이를 나타내는 정수 n (1 ≤ n ≤ 200 000)이 주어진다.

둘째 줄에는 블록을 설명하는 n개의 정수 h1, h2, . . . , hn (1 ≤ hi ≤ 100 000)이 주어진다. 이는 i번째 열에 사용되는 블록이 hi × 1 × 1 크기여야 함을 나타낸다.

피라미드의 가장 작은 부피를 출력한다.