|Codeforces Round #693 (Div. 3)|
Polycarp found under the Christmas tree an array $$$a$$$ of $$$n$$$ elements and instructions for playing with it:
For example, if $$$n = 5$$$ and $$$a = [7, 3, 1, 2, 3]$$$, then the following game options are possible:
Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.
The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from $$$1$$$ to $$$n$$$ in such a way as to maximize his result.
4 5 7 3 1 2 3 3 2 1 4 6 2 1000 2 3 995 1 5 1 1 1 1 1
7 6 1000 5
The first test case is explained in the statement.
In the second test case, the maximum score can be achieved by choosing $$$i = 1$$$.
In the third test case, the maximum score can be achieved by choosing $$$i = 2$$$.
In the fourth test case, the maximum score can be achieved by choosing $$$i = 1$$$.