决战时刻

题目描述

兔子国和敌国的战争进入到最终时刻。经过长期的战争，双方都进入了体力疲劳期，预备发扬骑士精神。各选出三人进行决斗。 作为兔子国国王，制定了一个选人规则。每个士兵都有一个战斗值，当然了战斗值有正有负（因为士兵暂时受伤，战斗值就为负数），国王的选人规则是这样，所有士兵排成一列，每名士兵都有一个战斗值 $f_i$ ,选出 $f_i,f_j,f_k$ 三名士兵，并且 $i<j

输入格式

第 $1$ 行输入兔子士兵的数量 $n$。 第 $2$ 行 $n$ 个整数，表示兔子士兵的战斗力。

输出格式

输出为一个整数，题目所描述的公式的战斗力之和的最大和。

7
4 5 -3 20 17 -17 7

74

9
-19 17 7 16 -16 12 11 9 -14

72

10
-10 5 -6 -13 -1 -17 16 6 12 -14

66

提示

#### 数据范围与提示 对于 $10\%$ 的测试点，$3<n≤20$； 对于 $30\%$ 的测试点，$3<n≤300$； 对于 $50\%$ 的测试点，$3<n≤3000$； 对于 $100\%$ 的测试点，$3

来源

童程童美