Nicolina is actually sort of a district of Iași, so Little IR12660 still had time to appreciate the Ieșean skyline. However, he can't really figure out whether some buildings belong to Nicolina or Iași, so he naturally comes up with the following problem:
You are given a function $$$f(a)$$$ that represents the maximum skyline achievable by permuting the elements of an array $$$a$$$.
The skyline of an array $$$a$$$ is defined as: $$$$$$\text{skyline} = \max \left( \min(a_i, a_{i+1},..., a_j) \cdot (j - i + 1) \right), \text{where } 1 \leq i \leq j \leq n$$$$$$
Given an array $$$a$$$ of size $$$n$$$, partition its elements into two non-empty subsequences $$$X$$$ and $$$Y$$$ such that: $$$f(X) + f(Y)$$$ is maximized.
A subsequence of $$$a$$$ is a sequence that can be derived from $$$a$$$ by deleting some (or no) elements without changing the order of the remaining elements.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The description of each test case is as follows:
- The first line of a test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the size of the array.
- The second line of a test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$
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 non-empty subsequences $$$X$$$ and $$$Y$$$.
253 1 4 1 5410 20 30 40
11 80
In the first testcase, we choose subsequences $$$X = [3,4,5]$$$, $$$Y = [1,1]$$$ and achieve a cost of $$$9+2=11$$$.
