Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mickey the Magician

By kitorp · Limits 1s, 512 MB

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]potions[i] is the amount of potion in city ii. Mickey will go from a city ii to a city jj only if i<ji < j, and he will go in two ways.

During the day: Mickey can go from ii to the city jj such that potions[i]potions[j]potions[i] \leq potions[j] and potions[j]potions[j] is the smallest possible value. If there are multiple such indices jj, Mickey can only go to the smallest such index jj.

During the night: Mickey can go from i to the city j such that potions[i]potions[j]potions[i] \geq potions[j] and potions[j]potions[j] is the largest possible value. If there are multiple such indices jj, Mickey can only go to the smallest such index jj.

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 KK is the number of good cities.

To calculate the effect of the potions Mickey first need to modify the potion array by repeating it KK times.
For example, if potion array = [2,1][2,1] and K=4K= 4 then the modified potion array will be [2,1,2,1,2,1,2,1][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 TT, denoting the number of testcases.

Each testcase will contain an integer NN, denoting the number of cities in Megaland.
Then for each city ii, there will be an integer potionsi(104potionsi104)potions_i (-10^4 \leq potions_i \leq 10^4), denoting the amount of potions available in that city.

Subtask

  • Subtask 1 (25 points): 1N1001 \leq N \leq 100
  • Subtask 2 (75 points): 1N1051 \leq N \leq 10^5

In subtask 11, sum of NN over all testcases will not exceed 10510^5.

In subtask 22, sum of NN over all testcases will not exceed 2×1062 \times 10^6.

Output

Output one integer denoting the effect of the vaccine.

Sample

InputOutput
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,
[5, 1, 3, 4, 2, 5, 1, 3, 4, 2, 5, 1, 3, 4, 2]

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.

    Discussion

    Statistics


    80% Solution Ratio

    NirjhorEarliest, 1M ago

    Deshi_TouristFastest, 0.2s

    Deshi_TouristLightest, 3.0 MB

    lelbabaShortest, 1564B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.