Problem C. Circular coverage ≡

Statement

There are N points on a circle, represented by numbers a_i, where a_i — direction from center to point i, measured in 1/100th parts of degree.

Your program must choose a set of pairs of points so that:

• Each pair of points defines an arc of a circle, shorter of two possible arcs.
• For a pair of points lying on the diameter, it is allowed to choose any of the arcs.
• Each point belongs to at most one pair.
• Arcs defined by different pairs do not have common points.
• The total length of all arcs, measured in 1/100th parts of degree, is as large as possible.

Input format

First line of input contains integer N.

Second line contains N integers a_i — directions from center to points, measured in 1/100th parts of degree.

Output format

Output must contain two integers S and M, where S — largest total arc length, M — number of selected pairs.

Next, output must contain M pairs of integers — pairs of point indices corresponding to the ends of each arc. Indices start with 1. The order of points in pair may be arbitrary.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ N ≤ 5000, 0 ≤ a_i < 36000

Sample tests

4
1 2 18000 18001

35998 2
2 3 4 1 

6
100 200 12000 12100 24000 24100

35700 3
2 3 4 5 6 1