描述

小番茄面试落选，和学姐去吃小火锅，感到前途一片黑暗，叹气道“他们都不看好我，偏偏我也不争气”。

给定一个数轴，数轴上有n个隔板，第i个隔板的高度为a[i]，在数轴上的位置为i。

定义一个水槽为两个隔板以及中间的区域，水槽的容积为两个隔板的高度中较小的值乘以两个隔板的距离。

现在你需要找出三个隔板，使得其构成两个水槽（位于中间的隔板将被共用），使得两个水槽的容积和最大，求此容积和。

输入

第一行输入一个整数t,表示有t组数据，每组数据的第一行输入一个整数n。接下来一行输入n个数，表示 a[i]。 1<=t<=100

3≤n≤5000

1≤a[i]≤1000000000 所有n和不超过5000

输出

每组数据输出一行 一个整数，表示三个隔板所组成两个水槽的最大容积和。

样例

1
5
1 2 3 4 5

8

限制

1s, 1024KiB for each test case.