atcoder#AGC059B. [AGC059B] Arrange Your Balls
[AGC059B] Arrange Your Balls
Score : points
Problem Statement
You have balls of colors . Here, all colors are represented by an integer between and inclusive. You want to arrange the balls on a circle. After you do that, you will count the number of pairs of colors such that and there exist two adjacent balls of colors and .
Find an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.
For example, for balls of colors , if we arrange them as , we get pairs: . If we arrange them as , we get only pairs: .
Solve test cases for each input file.
Constraints
- The sum of in one input file doesn't exceed .
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
Each case is in the following format:
Output
For each test case, output your answer in the following format:
Here, is the color of the -th ball (in clockwise order) on the circle in your arrangement.
should be a permutation of , and the number of pairs of colors such that and there exist two adjacent balls of colors and , should be minimized.
If multiple solutions exist, any of them will be accepted.
3
3
1 2 3
4
1 2 1 3
5
2 2 5 3 3
1 2 3
2 1 3 1
3 3 2 5 2