Chuan the Qi Shen, being a Chess God, finds normal chess too easy. Hence, he has recently indulged himself into forming armies made up of his favourite chess piece - the pawn! Chuan basically divides the N pawns into A groups (called armies) and labels the pawns in each army using consecutive integers starting with 1. For an army with P pawns (P ≥ 1), Chuan will label the pieces from 1 to P.
Of course, Chuan does the army formations and labellings in his head, and remembers them well. However, Barr the bear suddenly walks in with a plate of free food. Chuan, being Chuan, is distracted by the food and suddenly forgets which pawn is in which army!
Chuan does remember the labels of the pawns though (or so he thinks). He wonders if he is able to repartition the pawns into different armies such that the pawns in each army are labelled correctly. Help Chuan to recover his pawn armies!
The first line contains an integer N.
The next line contains the integer labels of the N pawns in a row, separated by spaces. Each label is in the range 1 to N.
If a grouping of the pawns into armies is possible, output on the first line A, the number of armies. The second line should contain N space-separated integers. The ith of these should be the army ID of the ith pawn in the row. There should be a total of A army IDs, from 1 to A. If several solutions are possible, print any one of them.
Otherwise, Chuan might have forgotten the labels of some pawns. In this case, output "-1".
For 50% of test data, 1 ≤ N ≤ 5,000.
For 100% of test data, 1 ≤ N ≤ 1,000,000.
Sample Input 1
1 2 3 1 2 1 4 2 5
Sample Output 1
3 1 2 1 2 2 2 3 2
Explanation for Sample Output 1
The 3 armies are:
- Pawns 2 and 4, with labels 2, 1
- Pawns 3, 5, 6, 7 and 9, with labels 3, 2, 1, 4, 5
- Pawns 1 and 8, with labels 1, 2
Sample Input 2
1 2 2 3
Sample Output 2
Explanation for Sample Output 2
There is no possible division of the pawns into armies such that each army has correct labelling. Chuan might have remembered the 2nd pawn's label wrongly, recalling it as 2 when it should be 1.