题目描述

有 $n$ 个点在圆上均匀分布，按顺时针顺序编号为 $1$ 到 $n$，第 $i$ 个点的权值为 $v_i$。

现要求将 $n$ 个点两两配对，用一条弦连接配对的两个点。一个配对方案是合法的，当且仅当每个点都恰好被配对一次，且所有连接的弦两两不相交。画出其中任意一条弦后整圆被该弦分为两个部分，其余每条弦的两个端点都位于它的同一侧。

一条弦的价值为它所连接的两个点 $i,j$ 的权值之积 $v_i v_j$。

求在所有合法的配对方案中，所有弦的价值之和最大为多少。

输入格式

从文件 chord.in 中读入数据。

第一行一个整数 $n$。

第二行 $n$ 个整数 $v_1,v_2,\dots,v_n$。

输出格式

输出到文件 chord.out 中。

输出一行一个整数，表示答案。

样例1输入

2
2 4

样例1输出

8

样例2输入

6
1 5 2 6 3 4

样例2输出

32

样例2解释

最优方案是连接 $(1,6),(2,3),(4,5)$，价值之和为 $1 \times 4+5 \times 2+6 \times 3=32$。

权值最大的两个点是 $2$ 号（权值为 $5$）和 $4$ 号（权值为 $6$），但它们之间只隔着一个 $3$ 号点。如果连接 $(2,4)$，$3$ 号点只能与弦另一侧的点配对，这条弦必然与 $(2,4)$ 相交，因此这种连法不合法。

样例3

见选手下发文件夹中的 chord3.in 与 chord3.ans。

样例4

见选手下发文件夹中的 chord4.in 与 chord4.ans。

样例5

见选手下发文件夹中的 chord5.in 与 chord5.ans。

数据范围

对于所有测试数据，保证 $2 \le n \le 500$，$n$ 为偶数，$1 \le v_i \le 10^6$。

本题共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。

测试点编号	$n \le$
$1 \sim 6$	10
$7 \sim 12$	100
$13 \sim 20$	500