Under construction

Still being built. Things may change

Array Not Divisible by Three

Interview

Time limit1sMemory limit128 MB

Summary
Rearrange an array so no two adjacent elements sum to a multiple of 3, or report impossibility.
Level

Medium5 of 10

Topics
Greedy, Math, Array
Solved
No attempts yet

Problem

Given an array of positive integers, reorder all numbers so that the sum of every pair of adjacent numbers is not divisible by 3.

If several valid orders exist, print any one of them. Every given number must be used exactly once.

Input

The first line contains the size of the array, N. (1 <= N <= 10000)

The second line contains N positive integers separated by spaces. Each integer is at most 1000000.

Output

If the array can be reordered as required, print one valid reordered array on one line.

If it is impossible, print -1.

Examples4

  1. Example 1

    Input
    3
1 2 3
    Expected output
    1 3 2

  2. Example 2

    Input
    5
4 6 3 9 8
    Expected output
    6 4 3 8 9

  3. Example 3

    Input
    6
3 7 6 4 2 8
    Expected output
    3 4 7 6 8 2

  4. Example 4

    Input
    3
3 12 9
    Expected output
    -1