Mainak has an array 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an of 𝑛n positive integers. He will do the following operation to this array exactly once:

- Pick a subsegment of this array and cyclically rotate it by any amount.

Formally, he can do the following exactly once:

- Pick two integers 𝑙l and 𝑟r, such that 1≤𝑙≤𝑟≤𝑛1≤l≤r≤n, and any positive integer 𝑘k.
- Repeat this 𝑘k times: set 𝑎𝑙=𝑎𝑙+1,𝑎𝑙+1=𝑎𝑙+2,…,𝑎𝑟−1=𝑎𝑟,𝑎𝑟=𝑎𝑙al=al+1,al+1=al+2,…,ar−1=ar,ar=al (all changes happen at the same time).

## Mainak and Array solution codeforces

Mainak wants to maximize the value of (𝑎𝑛−𝑎1)(an−a1) after exactly one such operation. Determine the maximum value of (𝑎𝑛−𝑎1)(an−a1) that he can obtain.

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1≤𝑡≤501≤t≤50) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1≤𝑛≤20001≤n≤2000).

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤9991≤ai≤999).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 20002000.

## Mainak and Array solution codeforces

For each test case, output a single integer — the maximum value of (𝑎𝑛−𝑎1)(an−a1) that Mainak can obtain by doing the operation exactly once.

10 0 990 7 4

## Mainak and Array solution codeforces

- In the first test case, we can rotate the subarray from index 33 to index 66 by an amount of 22 (i.e. choose 𝑙=3l=3, 𝑟=6r=6 and 𝑘=2k=2) to get the optimal array:
[1,3,9,11,5,7⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯]⟶[1,3,5,7,9,11⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯][1,3,9,11,5,7_]⟶[1,3,5,7,9,11_]
So the answer is 𝑎𝑛−𝑎1=11−1=10an−a1=11−1=10.

- In the second testcase, it is optimal to rotate the subarray starting and ending at index 11 and rotating it by an amount of 22.
- In the fourth testcase, it is optimal to rotate the subarray starting from index 11 to index 44 and rotating it by an amount of 33. So the answer is 8−1=78−1=7.