No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一 $n$ 个整数的序列，若能够找到一组三个数，满足 $i<j<k$ 且 $a_i>a_j$​ 且 $a_j<a_k$​ ，这三个数字按大小组成的形状就像字母 "V"，那么称该数对为 V 形数对

对于所有 V 形数对中，问最大的总和是多少。

Format

Input

输入一个数 $n$ ($3 ≤ n ≤ 300$)

接下来一行 $n$ 个数，第 $i$ 个数表示刻在石碑上的数字 $a_i$ ($1≤a_i≤10^9$)

保证至少存在一组三元组满足 "V" 形。

Output

输出所有满足条件的三元组中和最大的一组的和。

Samples

3
3 1 3

7

Limitation

1s, 1024KiB for each test case.