题目背景

昆卡船长发现了一排金币堆，但他不想和海盗们轮流拿，而是想直接分配：他每次只能从两端拿，但他可以连续拿多次，直到拿完所有金币。为了最大化自己的收益，他决定每次选择两端中较大的那堆拿。请你计算他最终能拿到多少金币。

题目描述

给定一个数组，表示一排金币堆。昆卡每次只能从数组的两端中选择一堆拿走，他每次都选择两端中较大的那堆。问最终他拿到的金币总数。

输入格式

第一行一个整数 N (1 ≤ N ≤ 1000000) 第二行 N 个整数，表示每堆金币的数量

输出格式

一个整数，表示昆卡能获得的金币总数。

样例输入

5
3 7 2 5 8

样例输出

18