题目背景 酒是陈的香。一般酒是酿得越久越醇香，价值也越高。

题目描述 小T花了不少钱购买了酿酒的原材料。一开始小T用买来的材料封装了 坛酒，把这些酒按 编号后，都放到了酒窖中。而且这些酒分别放入的原材料是不同的，因此每坛酒的成本不一定相同。这个酒窖比较特殊，是一个长长的通道，首尾两端各有开口，每次拿酒只能从某一端取出最靠外面的一坛。

为了能维持生活开销，小T打算每年都从酒窖中拿出一坛酒卖掉。已知小T每年只会从首尾其中一端拿出最靠外的一坛酒，而且由于酒在酒窖中的时长不同，酒的售价也不同。每坛酒的 实际售价放入酒窖后的时长（年）这坛酒的成本价

已知每坛酒的成本价，请你帮小T算一下把这些酒卖掉后最多能收入多少钱？

输入格式 第一行一个整数 ，表示酒的总坛数。

接下来的 行，每行一个整数，依次对应每坛酒的成本 。

输出格式 输出卖掉所有的酒最多能有多少收入。

样例数据 样例输入 5 1 3 1 5 2 样例输出 43