Description

在一排n堆石子中，每堆的石子数量可能不同。每次操作可以选择其中两个相邻且包含石子数量相同的堆进行合并。 请设计一种合并方案，使得合并后最大的那堆石子包含的石子数量尽可能多。

例如：n=6，6堆石子的数量分别为：4 2 2 4 8 4 第一种合并方案如下： 1、合并2 2，得到4 4 4 8 4 2、合并第二个和第三个4，得到4 8 8 4 3、合并8 8，得到4 16 4 合并后最大的那堆石子包含的石子数量为16。 第二种合并方案如下： 1、合并2 2，得到4 4 4 8 4 2、合并第一个和第二个4，得到8 4 8 4 合并后最大的那堆石子包含的石子数量为8. 可以发现第一种合并方案最优，合并后最大的那对是自包含的石子数量为16.

Format

Input

第一行包含一个整数n，表示石子的堆数。 第二行包含n个整数x₁，x₂，...,x_n,分别表示每堆石子的数量，整数之间以一个空格隔开。

数据范围1~10：1<=n<=300,1<=x_i<=150。

Output

一个整数，表示最优的合并方案中，最大的那堆石子包含的石子数量。

Samples

6
4 2 2 4 8 4

16

5
4 4 3 4 4 

8

Limitation

1s, 1024KiB for each test case.