Sorted Marbles

You are given a sequence of marbles, each colored either red, blue, or green. Your task is to sort this sequence so that all red marbles come first, followed by all blue marbles, and finally all green marbles.

The problem can be modeled using the classical Dutch National Flag algorithm. In mathematical terms, if we denote the positions as indices from 0 to \( n-1 \) and the list as \( A \), then the goal is to rearrange \( A \) such that all indices \( i \) with \( A[i]=\text{red}\) come before indices with \( A[i]=\text{blue}\), and those come before indices with \( A[i]=\text{green}\).

It is guaranteed that each color in the input will be one of the three aforementioned. The algorithm should run in a single pass over the input list.

inputFormat

The first line of the input contains an integer \( n \) representing the number of marbles. The second line contains \( n \) space-separated strings where each string is either red, blue, or green. For example:

6
green blue red green blue red

outputFormat

Output a single line containing the sorted sequence of marbles, separated by a single space. Following the example above, the expected output is:

red red blue blue green green

6
green blue red green blue red

red red blue blue green green