#include <iostream>
using namespace std;


void DutchNationalFlag4(int * arr , int n )
{
	int low = 0 , mid1 = 0 , mid2 = n- 1 , high = n-1 ;
	int temp;
	
	// This type of problems are best solved by using invariants 
	
	// arr[ 0 .. low -1 ] conatins 0
	// arr[ low .. mid1 -1 ] contains 1
	// arr[ mid1 .. mid2 ] is unknown
	// arr[ mid2 + 1 ... high - 1 ] contains 2
	// arr[ high .. n-1 ] contains 3
	
	// termination condition : Evert Iteration unkown length decreases so eventually will be Zero
	while( mid1 <= mid2 )
	{
		switch( arr[ mid1 ])
		{
			case 0 :
			{
				std::swap( arr[ low ] , arr [ mid1 ] );
				low ++ ;
				mid1 ++;
				break;
			}
			
			case 1 :
			{
				mid1 ++;
				break;
			}
			
			case 2 :
			{
				std::swap( arr[ mid1 ] , arr[ mid2 ]);
				mid2 -- ;
				break;
			}
			
			case 3 :
			{
				std::swap( arr[ mid1 ] , arr[ mid2 ]);
				std::swap( arr[ mid2 ] , arr[ high ]);
				mid2 --;
				high --;
				break;
			}
				
		}
	}
	
	for( int i =0 ; i < n ; i++)
	{
		cout << arr[ i ] << " " ;
	}
}

int main() {
	int arr[] = {1,2,3,0,2,1,3,0,2,1,0,1,3,1,0,2,1,0};
	int n = sizeof(arr) / sizeof(arr[0]) ;
	DutchNationalFlag4(arr , n );
	return 0;
}