Halloween town just expanded, to a size of around 100,000 households. With the expansion, Bob now has more friends then he can count. So, this year Bob decided to create his own trick-or-treating route, and invite his friends to join him. Once again, Bob did a careful survey on which house gives which kinds of candy. To avoid suspicion of the fact that he hates licorice, Bob needs to choose a conventional route like everyone else. I.E. They choose a start and end household, and visit all the houses in between. What route should Bob take?
There will be multiple test cases. First there will be an integer C on its own line, that determines how many test cases there are.
Each test case starts with a line with an integer n (1 <= n <= 100,000), equal to the number of houses in Halloween Town. Then, the next line will have n numbers (seperated by spaces) corresponding to the values of the candies these households give (between -100 to 100). At least one household will be giving out non-licorice flavoured candy, and have a positive value (Note: Halloween Town is a civilized town, and everyone counts from 0. i.e. the first number is for the 0th house, the last number for the (n-1)th house)
For each test case, output a line of the following format:
Start at house a and end at house b will give the best net benefit of c.
Where a, b, c are numbers corresponding to the start house, end house, and the net benefit. If more than one route gives the best net benefit, output the one with earlier starting house (smaller a). If more than one route with the same starting house gives the best net benefit, output the one with the earlier ending house (smaller b).
3
8
1 -2 4 9 -10 -10 13 0
7
1 -2 4 9 -10 13 0
1
10
Start at house 2 and end at house 3 will give the best net benefit of 13.
Start at house 2 and end at house 5 will give the best net benefit of 16.
Start at house 0 and end at house 0 will give the best net benefit of 10.