import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Max_Transform {
	static int sum = 0;

	public static void solve(Integer[] A, int flag) {
		if (flag != 0) {
			List<Integer> B = new LinkedList<Integer>();
			for (int k = 0; k < A.length; k++) {
				for (int i = 0; i < (A.length - k); i++) {
					B.add(IntStream.rangeClosed(i, i + k).map(idx -> A[idx])
							.max().getAsInt());
				}
			}
			if (flag == 1) {
				sum = B.stream().map(s -> s).reduce((a, b) -> a + b).get();
			} else {
				Integer[] b = B.toArray(new Integer[B.size()]);
				solve(b, --flag);
			}
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		Integer[] a = new Integer[n];
		for (int a_i = 0; a_i < n; a_i++) {
			a[a_i] = in.nextInt();
		}
		solve(a, 2);
		System.out.println(sum);
		in.close();
	}

}