L. Skyline
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Busch is actually sort of a campus of New Brunswick, so Little Keshstein had time to appreciate the Busch skyline. However, he can't really figure out whether some buildings belong to Busch or Livingston, so he naturally comes up with the following problem.

You are given a function $$$f(b)$$$ that represents the maximum skyline achievable for an array $$$b$$$ of length $$$m$$$, defined as:

$$$$$$f(b) = \max(\min(b_i, b_{i+1}, \ldots, b_j) \cdot (j-i+1))\text{, where } 1 \leq i \leq j \leq m.$$$$$$

Given an array $$$a$$$ of length $$$n$$$, partition its elements into two nonempty subsequences $$$x$$$ and $$$y$$$ such that each element is contained in exactly one of $$$x$$$ or $$$y$$$, and $$$f(x)+f(y)$$$ is maximized.

A sequence $$$x$$$ is a subsequence of a sequence $$$a$$$ if $$$x$$$ can be obtained from $$$a$$$ by the deletion of several (possibly zero or all) elements from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 7500)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$7500^2$$$.

Output

For each test case, output a single integer — the maximum value of $$$f(x)+f(y)$$$ that can be achieved by partitioning $$$a$$$ into two nonempty subsequences $$$x$$$ and $$$y$$$.

Example
Input
6
5
3 1 4 1 5
4
1 2 3 4
4
2 1 2 4
4
2 1 4 2
5
2 3 1 2 3
6
4 1 3 6 2 3
Output
11
8
8
8
9
15
Note

In the third test case, one optimal partition is $$$x = [a_1, a_3] = [2, 2]$$$ and $$$y = [a_2, a_4] = [1, 4]$$$. We can show that $$$f(x) + f(y) = 2\cdot(2-1+1) + 4\cdot(2-2+1) = 8$$$. We illustrate below.