Suppose we want to replicate a file over a collection of n servers, labeled S₁, S₂ ... S_n. To place a copy of the file at server S_i results in a placement cost of c_i, for an integer c_i > 0. Now, if a user requests the file from server S_i, and no copy of the file is present at S_i, then the servers S_{i + 1}, S_{i + 2}, S_{i + 3} ... are searched in order until a copy of the file is finally found, say at server S_j, where j > i. This results in an access cost of j−i. (Note that the lower-indexed servers S_i−1, S_i−2, ... are not consulted in this search.) The access cost is 0 if S_i holds a copy of the file. We will require that a copy of the file be placed at server S_n, so that all such searches will terminate, at the latest, at S_n.

We’d like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server S_i with i = 1, 2 ... n−1, of whether to place a copy of the file at S_i or not. (Recall that a copy is always placed at S_n.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers.

Write a program which reads from the standard input the placement costs and writes a single number, the minimum cost of a configuration. First line of the input consists of the number n of servers (1 ≤ n ≤ 1000). In the next n lines you are given the placement costs, in line i + 1 you are given the placement cost c_i of server S_i.

Example

Input:
4
1
1
1
9

Output:
12

Input:
4
4
3
2
1

Output:
6