Card Gym - 101257H-白红宇

Card Gym - 101257H

阅读量：4204 次

发布时间：2019-05-26

本文共 2780 字，大约阅读时间需要 9 分钟。

After Hasan ruined the Worm puzzle, Rula brought a new game to the office, the Card game.

The game has a group of cards, each card has an integer value V_i written on it.

$\text{[math]}$

Initially, N cards are placed side by side in a straight line (refer to the picture above). In each turn you will pick two adjacent card sets (a single card is also considered a card set) and merge the cards of the two sets together to form one new set.

After each turn, you will add the maximum card value in each card set to your score. The game is over when no more merges could be performed.

What is the maximum score you can get at the end of the game, given that your initial score is 0?

Input

The first line of input contains a single integer N (2 ≤ N ≤ 10⁵), the number of cards in the game.

The second line contains N space-separated integers, each integer is V_i (1 ≤ V_i ≤ 5000), which represents the number written on the i^th card.

Output

On a single line, print the maximum score you can get.

Example

Input

51 2 3 2 1

Output

Input

67 9 7 5 4 3

Output

Note

One of the possible solutions for the first sample is as follows:

Initially, each set will contain a single card: {1} {2} {3} {2} {1}.

Merge {1} with {2}, the resulting sets are: {1 2} {3} {2} {1}, which will add (2 + 3 + 2 + 1 = 8) to your score.

Merge {2} with {1}, the resulting sets are: {1 2} {3} {2 1}, which will add (2 + 3 + 2 = 7) to your score.

Merge {1 2} with {3}, the resulting sets are: {1 2 3} {2 1}, which will add (3 + 2 = 5) to your score.

Merge {1 2 3} with {2 1}, the resulting sets are: {1 2 3 2 1}, which will add 3 to your score.

Final score is 8 + 7 + 5 + 3 = 23.

哈桑破坏了Worm拼图，Rula带来了一个新的游戏到办公室，卡牌游戏。

游戏有一组牌，每张牌都有一个整数值Vi写在它上面。

最初，N张卡并排放置在一条直线上（参见上图）。在每个回合，你会选择两个相邻的卡集（一个卡也被认为是一个卡集），并将两个集合的卡合并成一个新集。

每回合后，您将在每个卡组中将最大卡值添加到您的总谱。游戏结束时，没有更多的合并可以执行。

考虑到你的初始分数是0，你在游戏结束时可以获得的最高分数是多少？

输入

第一行输入包含单个整数N（2≤N≤105），游戏中的牌数。

第二行包含N个空格分隔的整数，每个整数为Vi（1≤Vi≤5000），表示写在第i张卡上的数字。

输出

在一行上，打印你可以得到的最大得分。

例

输入

1 2 3 2 1

输出

输入

7 9 7 5 4 3

输出

108

注意

第一个样本的可能解决方案之一如下：

最初，每个集合将包含一张牌：{1} {2} {3} {2} {1}。

将{1}与{2}合并，得到的集合为：{1 2} {3} {2} {1}，它将为您的总分添加（2 + 3 + 2 + 1 = 8）。

将{2}与{1}合并，生成的集合为：{1 2} {3} {2 1}，它将为您的总分添加（2 + 3 + 2 = 7）。

将{1 2}与{3}合并，生成的集合为：{1 2 3} {2 1}，它将为您的总分添加（3 + 2 = 5）。

将{1 2 3}与{2 1}合并，结果集为：{1 2 3 2 1}，它将为您的分数增加3。

最终得分为8 + 7 + 5 + 3 = 23。

////  main.cpp//  160929////  Created by liuzhe on 16/9/29.//  Copyright © 2016年 my_code. All rights reserved.////#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 using namespace std;int a[100010];int n;int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); scanf("%d",&n); long long sum=0; for(int i=0;i