#P1720B. Interesting Sum
Interesting Sum
No submission language available for this problem.
Description
You are given an array that contains integers. You can choose any proper subsegment of this array, meaning you can choose any two integers , where . We define the beauty of a given subsegment as the value of the following expression:
Please find the maximum beauty among all proper subsegments.
The first line contains one integer () — the number of test cases. Then follow the descriptions of each test case.
The first line of each test case contains a single integer — the length of the array.
The second line of each test case contains integers () — the elements of the given array.
It is guaranteed that the sum of over all test cases does not exceed .
For each testcase print a single integer — the maximum beauty of a proper subsegment.
Input
The first line contains one integer () — the number of test cases. Then follow the descriptions of each test case.
The first line of each test case contains a single integer — the length of the array.
The second line of each test case contains integers () — the elements of the given array.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each testcase print a single integer — the maximum beauty of a proper subsegment.
Samples
Note
In the first test case, the optimal segment is , . The beauty of this segment equals to .
In the second test case, the optimal segment is , . The beauty of this segment equals .