Athena on Zanzibar Island

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.9s
Java 8 1.5s
Memory limit: 256M

Author:
Problem type

In a far far away land called the island of Zanzibar, Athena the Software Engineer is typing away on another problem. Earlier that day, her boss gave her N pizzas with tanginess values of a1,a2,,aN, tasking her with finding two pizzas i and j such that ij and |ai+aj| is minimized. But lately, Athena has been very swamped with physics lab work from the University of Waterloo writing boring business reports, and doesn't have time to complete the job. Can you help her finish it before the deadline?

Constraints

2N106

109ai109

Subtask 1 [10%]

2N100

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains the integer N.

The second line contains the space-separated integers a1,a2,,aN.

Output Specification

Let A be the minimum possible value of |ai+aj| with the given input.

The first line should contain A.

The second line should contain the space separated integers i,j such that |ai+aj|=A. If there are multiple possible answers, output the one that minimizes 107×i+j.

Sample Input

Copy
10
-5 8 2 1 7 -3 -5 0 5 5

Sample Output

Copy
0
1 9

Sample Explanation

Taking the 1st and 9th pizzas results in the best possible sum of 0.


Comments

There are no comments at the moment.