Stock Market

A bank has collected day-to-day data of the daily profit (or loss) of the shares it holds. Using these numbers, it wants to determine on which single day it should have bought and on which single day it should have sold in order to maximize its profit, so it can compare that ideal outcome with its actual performance.

Given the sequence of daily profits, write a program that finds the contiguous run whose total profit is largest. The run is described by the 1-based indices of its first and last elements (indices start at 1). Exactly one buy day and one sell day must be chosen. (Otherwise the task would be trivial: simply hold the shares on every day whose profit is non-negative.)

The first line contains the number of test cases. Each test case has the following format.

• One line with the length of the sequence $N$ ($1 \le N \le 10^6$).
• One line with $N$ integers $p_i$ separated by single spaces ($-10^3 \le p_i \le 10^3$), where $p_i$ is the profit (or loss) on day $i$. At least one of the integers is positive.

For each test case, print on a single line two integers $i$ and $j$ ($1 \le i \le j \le N$) such that the sum of the $i$-th through $j$-th integers (inclusive) is maximized. If several pairs achieve the maximum, print the one with the smallest $i$; if there is still a tie, print the one with the smallest $j$.