Sort colours

Problem

Orders have a priority of 0, 1 or 2. Sort them so all 0s come first, then 1s, then 2s. Do it in one pass without calling a sort function.

Example

Input

6
2 0 2 1 1 0

Output

0 0 1 1 2 2

0 0 1 1 2 2.

Try the problem first. Open one hint at a time.

Hint 1

Keep three pointers: low for the next 0, high for the next 2, and mid that scans.

Hint 2

After swapping with high, do not move mid: the new item has not been looked at.

Write your Python code, run it on the examples and submit it to hidden tests.