Problem G. Greedy replacement

Author:M. Sporyshev   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Let we have array of integers ai. You can select in it no more than one number and replace it to other. Cost of this replacement is absolute difference new and old numbers.

It is required to find replacement with a minimum cost, so that a pair of same elements appears in the array of prefix sums of this array.

Input format

First line of input data contains single number N — length of the array.

Second line contains the N integers ai.

Output format

Output data must contains two integer numbers — index of element for replacement (starting by zero) and signed difference between new and old its values.

If there are many solutions, than output any from them.

Constraints

2 < N < 100000

|ai| ≤ 109

Sample tests

No. Standard input Standard output
1
2
1 1
1 -1
2
3
1 2 -3
2 1

0.209s 0.033s 13