832. Animal Arrangement

0

Easy

In a zoo, there are three types of animals: ants, rabbits, and elephants. Your task is to arrange these animals in a row such that ants come first, followed by rabbits, and then elephants.

Ants are represented by 0, rabbits by 1, and elephants by 2.

You are given an array of size N containing values 0, 1, and 2. Rearrange the array in non-decreasing order.

Ants are represented by 0, rabbits by 1, and elephants by 2.

You are given an array of size N containing values 0, 1, and 2. Rearrange the array in non-decreasing order.

**Can you accomplish this without using additional space?**Input Format

The first line contains a single integer N, which represents the size of the array. The second line contains N integers representing the elements of the array.

Output Format

Print the array in non-decreasing order.

Example

Input

6
2 0 2 1 1 0

Output

0 0 1 1 2 2

Constraints

1<=N<=100005

A[i] can only be 0, 1, or 2.

A[i] can only be 0, 1, or 2.

Loading...

View Submissions

Console