Maximal Sum

A graph has $r$ nodes in a line, numbered 1 to $r$. The edge joining node $i$ and node $i+1$ has weight $w_i$, and a weight can be positive or negative.

For $i < j$, the value of the path from node $i$ to node $j$ is the sum of the weights the path crosses, $w_i + w_{i+1} + \dots + w_{j-1}$.

Write a program that finds the path with the largest value.

The first line contains the number of test cases $n$ ($1 \le n \le 100$).

Each test case starts with the number of nodes $r$ ($2 \le r \le 50$), followed by the integers $w_1, w_2, \dots, w_{r-1}$. Here $w_i$ is the weight of the edge joining node $i$ and node $i+1$, and $-10000 \le w_i \le 10000$. Numbers are separated by whitespace or line breaks.

For each test case, print on one line the starting node $i$ and the ending node $j$ of the path with the largest value, separated by a space.

If several paths reach the largest value, choose the longest one, the one whose $j-i$ is largest. If several paths share both the largest value and the same length, choose the one with the smallest $i$.

If the largest value is not positive, print no good path.