439. Arrange the animals

0

Easy

You have been tasked with arranging animals in a zoo in a specific order. The animals are ants, rabbits, and 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. Your goal is to rearrange the array in non-decreasing order, with ants first, followed by rabbits, and then elephants. Can you accomplish this without using extra space?

Input Format

The first line of input 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