# Running Miles solution codeforces

There is a street with n sights, with sight number i being i miles from the beginning of the street. Sight number i has beauty bi��. You want to start your morning jog l miles and end it r miles from the beginning of the street. By the time you run, you will see sights you run by (including sights at l and r miles from the start). You are interested in the 33 most beautiful sights along your jog, but every mile you run, you get more and more tired.

So choose l and r, such that there are at least 33 sights you run by, and the sum of beauties of the 33 most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose l and r, such that bi1+bi2+bi3(rl)��1+��2+��3−(�−�) is maximum possible, where i1,i2,i3�1,�2,�3 are the indices of the three maximum elements in range [l,r][�,�].

Running Miles solution codeforces

The first line contains a single integer t (1t1051≤�≤105) — the number of test cases.

The first line of each test case contains a single integer n (3n1053≤�≤105).

The second line of each test case contains n integers bi�� (1bi1081≤��≤108) — beauties of sights i miles from the beginning of the street.

It’s guaranteed that the sum of all n does not exceed 105105.

Running Miles solution codeforces

For each test case output a single integer equal to the maximum value bi1+bi2+bi3(rl)��1+��2+��3−(�−�) for some running range [l,r][�,�].

Example

4

5

5 1 4 2 3

4

1 1 1 1

6

9 8 7 6 5 4

7

100000000 1 100000000 1 100000000 1 100000000

Running Miles solution codeforces

In the first example, we can choose l and r to be 11 and 55. So we visit all the sights and the three sights with the maximum beauty are the sights with indices 1133, and 55 with beauties 5544, and 33, respectively. So the total value is 5+4+3(51)=85+4+3−(5−1)=8.

In the second example, the range [l,r][�,�] can be [1,3][1,3] or [2,4][2,4], the total value is 1+1+1(31)=11+1+1−(3−1)=1.