In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i]. Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.
Input Format
Array of size 'n'
Output Format
Array without adjacent duplicates
Constraints
1 <= barcodes.length <= 10000 1 <= barcodes[i] <= 10000
Notice
NA
Example
Input
6 1 1 1 2 2 2
Output
1 2 1 2 1 2