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

---

hide comments

	smso: 2024-03-23 05:18:23 Do divide and conquer on range of unassigned servers. More testcases: 2 3 10 output: 11 10 5 10 1 2 4 9 8 6 4 9 output: 28 mask: 0010100001 10 8 5 7 4 3 1 3 4 1 5 output: 21 mask: 0001010011
	Ashwini: 2013-12-31 07:05:41 @groopy: its not 19th test case. even if your 1st test case output is wrong then also judge will run it till 19th test case.after that it checks for wrong answer. so just check your logic
	Ashwini: 2013-12-31 06:19:27 what are the constraints for ci?
	raunakrocks: 2013-12-15 18:27:32 AC!! Last edit: 2013-12-30 12:57:47