题目描述

这是一道经典题。

一个环上有$n$堆石子，每堆石子分别有$a_1,a_2,…,a_n$个石子，进行$n-1$次合并操作，每次合并会将相邻的两堆合并为一堆（第$i$堆与第$i+1$堆相邻，第$n$堆与第$1$堆也是相邻的），这次合并的得分为合并之后这堆石子的石子个数。问最后最大的总得分。

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

4
4 5 9 4

样例输出 #1

54

说明/提示

$1\leq n\leq 100,0\leq a_i\leq 20$。