Maximal Sum

Interview

Time limit1sMemory limit64 MB

Summary

Find the contiguous block of edge weights with the largest sum and print its endpoints, or print no good path when the best sum is not positive.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

Example 1

Input

4
3 -1 6
6 1 -2 1 6 -3
10 4 -5 4 -3 4 4 -4 4 -5
4 -2 -3 -4

Expected output

2 3
3 5
3 9
no good path

Example 2
Input
```
2
2 5
2 -5
```
Expected output
```
1 2
no good path
```