Mickey the magician is working on a vaccine for COVID-19. But he is not sure if the vaccine which is made of potions will pass the high test standards set by our IUT medical system.
Megaland has many cities. Mickey the Magician is travelling from one city to another collecting magic potions. His goal is to travel to the farthest city in Megaland collecting all potions. Every city in Megaland has some amount of magic potions. He travels day and night.
Amount of potions in city is represented by an array Potions where $potions[i]$ is the amount of potion in city $i$. Mickey will go from a city $i$ to a city $j$ only if $i < j$, and he will go in two ways.
During the day: Mickey can go from $i$ to the city $j$ such that $potions[i] \leq potions[j]$ and $potions[j]$ is the smallest possible value. If there are multiple such indices $j$, Mickey can only go to the smallest such index $j$.
During the night: Mickey can go from i to the city j such that $potions[i] \geq potions[j]$ and $potions[j]$ is the largest possible value. If there are multiple such indices $j$, Mickey can only go to the smallest such index $j$.
Starting in the day Mickey will continuously go from one city to another travelling alternatively in day and night. He will not take rest because, come on, we are in the middle of a global pandemic. Who got time for rest? But Mickey wants to know in advance if the vaccine made by potions will work or not.
A good city is a city by which you can go to the end of Megaland (the last indexed city) by moving some number of times (possibly 0 or more than once). Let's say $K$ is the number of good cities.
To calculate the effect of the potions Mickey first need to modify the potion array by repeating it $K$ times.
For example, if potion array = $[2,1]$ and $K= 4$ then the modified potion array will be $[2, 1, 2, 1, 2, 1, 2, 1]$.
The effect of the vaccine made by potions is the maximum sub-array sum in the modified array.
Input
First line contain an integer $T$, denoting the number of testcases.
Each testcase will contain an integer $N$, denoting the number of cities in Megaland.
Then for each city $i$, there will be an integer $potions_i (-10^4 \leq potions_i \leq 10^4)$, denoting the amount of potions available in that city.
Subtask
- Subtask 1 (25 points):
$1 \leq N \leq 100$ - Subtask 2 (75 points):
$1 \leq N \leq 10^5$
In subtask $1$, sum of $N$ over all testcases will not exceed $10^5$.
In subtask $2$, sum of $N$ over all testcases will not exceed $2 \times 10^6$.
Output
Output one integer denoting the effect of the vaccine.
Sample
| Input | Output |
|---|---|
1 5 5 1 3 4 2 | 45 |
We can reach the end city from cities indexed 1, 2, and 4. So The number of good cities K = 3. Modifing the potions array by repeating it 3 times will look like, The Maximum Sub-Array sum for this array is 45. | |
Notes
Sub- array is any continuous part of an array. The length of the sub-array can be 0 and its sum in that case is 0.
