C-丢手绢_牛客练习赛145

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

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，这些元素围成一个圆，第 $i$ 个元素与第 $i+1$ 个元素相邻，且第 $n$ 个元素与第 $1$ 个元素相邻。

$\hspace{15pt}$ 我们从圆上任意选择四个两两不同的位置 $i,j,k,l$ ，分别连线 $(i,j)$ 和 $(k,l)$ ，若这两条线恰好在圆内部相交（交点不在圆上），则每条线的权值定义为其两个端点元素之和，记这两条相交线权值的乘积为该对相交线的价值。

$\hspace{15pt}$ 求所有可能的两条相交的线中，价值的最大值。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示数组的长度； 
第二行输入  个整数 ，表示数组元素。 
除此之外，保证所有测试数据中  的总和不超过 。

对于每组测试数据，输出一个整数，表示该圆的最大价值。

示例1

复制

复制

48
100

对于第一组测试数据，选择  连线、 连线即可。