## Problem C. Circular coverage ≡

 Author: А. Жихарева Time limit: 2 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

There are N points on a circle, represented by numbers ai, where ai — 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 ai — 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 ≤ ai < 36000

### Sample tests

No. Standard input Standard output
1
4
1 2 18000 18001

35998 2
2 3 4 1 
2
6
100 200 12000 12100 24000 24100
35700 3
2 3 4 5 6 1 

0.165s 0.019s 15