## DMOPC '20 Contest 7 P1 - Bob and Balance

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 256M
Python 512M

Author:
Problem type

Bob is sitting through another session of physics class, with a topic regarding the force of gravity on an object. Bob thinks that the force of gravity is the same for all objects, regardless of their mass. However, his teacher Dr. Henri knows better. To convince Bob that he is wrong, Dr. Henri dug up weights (the -th weight having mass grams) and balance scales (the traditional kind with plates to the left and right of the fulcrum).

Dr. Henri knows that the scales will tip to the plate holding a higher mass, or remain balanced if the masses on both sides are equal. To be as convincing as possible, Dr. Henri would like to arrange the weights on the scales with exactly one weight on each plate of each scale such that the maximum number of scales are tipped to either side. Please find an arrangement of the weights satisfying this requirement.

#### Input Specification

The first line contains an integer .

The second line contains space-separated integers , the masses of the weights.

#### Output Specification

On the first line output an integer , the maximum possible number of tipped scales.

On the -th of the next lines, output space-separated integers and , representing that the -th scale holds the -th weight on the left plate and the -th weight on the right plate.

Each weight must be placed on a plate, and one plate may only hold one weight. The number of tipped scales in your arrangement must be exactly . If there are multiple possible outputs satisfying these requirements, any of them will be accepted.

#### Sample Input

3
1 2 1 2 1 1

#### Sample Output

2
1 4
2 3
6 5

#### Explanation

The first scale will tip to the right, and the second scale will tip to the left. The third scale remains balanced. It can be proven that this is the maximum possible number of tipped scales, so this is a valid arrangement of the weights.