D. Running Milestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere is a street with n sights, with sight number i being i miles from the beginning of the street. Sight number i has beauty b_i. 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 3 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 3 sights you run by, and the sum of beauties of the 3 most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose l and r, such that b_{i_1} + b_{i_2} + b_{i_3} - (r - l) is maximum possible, where i_1, i_2, i_3 are the indices of the three maximum elements in range [l, r].InputThe first line contains a single integer t (1 \leq t \leq 10^5) — the number of test cases.The first line of each test case contains a single integer n (3 \leq n \leq 10^5).The second line of each test case contains n integers b_i (1 \leq b_i \leq 10^8) — beauties of sights i miles from the beginning of the street.It's guaranteed that the sum of all n does not exceed 10^5.OutputFor each test case output a single integer equal to the maximum value b_{i_1} + b_{i_2} + b_{i_3} - (r - l) for some running range [l, r].ExampleInput
455 1 4 2 341 1 1 169 8 7 6 5 47100000000 1 100000000 1 100000000 1 100000000Output
8
1
22
299999996
NoteIn the first example, we can choose l and r to be 1 and 5. So we visit all the sights and the three sights with the maximum beauty are the sights with indices 1, 3, and 5 with beauties 5, 4, and 3, respectively. So the total value is 5 + 4 + 3 - (5 - 1) = 8.In the second example, the range [l, r] can be [1, 3] or [2, 4], the total value is 1 + 1 + 1 - (3 - 1) = 1.
455 1 4 2 341 1 1 169 8 7 6 5 47100000000 1 100000000 1 100000000 1 100000000
8 1 22 299999996 
['brute force', 'dp', 'greedy', '*1700']