交换
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

ljl最近对数组十分感兴趣。给定一个由n个整数构成的数组a,ljl将进行n次操作。

初始状态下ljl的分数为0。对于第i次操作,ljl可以对数组中相邻的两个元素进行交换并且将其中一个元素置为0,也可以对数组不进行任何操作。第i次操作完成后,ljl的分数需要加上a_i

请问,n次操作后,ljl最多可以得到多少分?

输入描述:

第一行为一个整数n(2 \le n \le 500)

第二行包含n个整数a_1,a_2,\cdots, a_n(1 \le a_i \le 10^6)

输出描述:

输出一个整数,表示ljl最多可以得到的分数。
示例1

输入

复制
2
5 1

输出

复制
10
示例2

输入

复制
6
1000 1 2 3 4 5

输出

复制
6000

备注:

对于第一个样例,第一次操作选择对数组不进行任何操作,然后分数加5。第二次操作对第一个元素和第二个元素进行交换,然后把元素1置为0,于是分数再加上5。所以最后能得到的最多分数是10