Challenge: Dutch National Flag Problem

Problem statement

Implement a function that sorts a list of $0s$, $1s$ and $2s$. This is called the Dutch National Flag Problem. Since the number $O$ can be represented by the blue color, $1$ by the white color, and $2$ as the red color, the task is to transform the list input to the Dutch flag.

Try solving this problem in-place and in linear time without using any extra space.

Input

An array of $0s$, $1s$, and $2s$

Output

An array where the numbers $0$, $1$, and $2$ are sorted

Sample input

lst = [2, 0, 0, 1, 2, 1, 0]

Sample output

result = [0, 0, 0, 1, 1, 2, 2]