Fizz, the tidal trickster, is not only a fisherman, he is also a fish-man. While he catches fish for a living, he still largely empathise with them, and tries to save as many of them as possible. One day, he chanced upon Rar the cat fishing by the riverbank. Rar the cat has cast a huge net along the river, and had caught some fish at each section along the river bank, labelled from 0 to N-1. Rar the cat evaluates the quality of the fish by using a machine. It is not known how the machine works, but the machine maps each fish to a quality (an integer), and has already labelled each section with the sum of the qualities of its fish. When there's more than one fish in the machine, it will output the sum of the qualities.
Rar the cat is currently taking a afternoon nap, so Fizz is trying to take this opportunity to free as many fish as possible. He knows that Rar the cat is lazy, and will only check for missing fish by putting all the fish into the machine, and comparing the sum with the sum of all the fish' qualities calculated previously. Rar is unable to tell if there are missing fish if the change in quality is small enough. Hence, to minimize the risk of detection, Fizz must minimize the absolute value of the sum of the qualities of the fish he free.
Furthermore, Fizz doesn't have much time before Rar wakes up from his nap, so he can only free a contiguous section of fish. Help Fizz decide which segment to free!
The first line will be the integer N.
The following N lines will contain one number, Qi
, which is the quality of the section i;
Print two integers, A and B, denoting the starting section and the ending section of the net that he should free. The sections should be inclusive of A and B. If there are multiple answers of A and B, you are free to output any one of them.
Subtask 1 (30%): 1 ≤ N ≤ 100
Subtask 2 (30%): 1 ≤ N ≤ 1000
Subtask 3 (40%): 1 ≤ N ≤ 1000000
The two fishes chosen to be freed are [-40, 42]. This gives an absolute sum of 2, which is the minimum.
Fishes [-10, -40] gives a minimum sum of -50 but it's absolute sum is 50, which is not desired.