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:

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