class Solution{
public:	

	void segregateEvenOdd(int arr[], int n) {
	    // code here
	    multiset<int>s1;
	    multiset<int>s2;
	    vector<int>v;
	    for(int i=0;i<n;i++)
	    {
	        if(arr[i]%2==0) s1.insert(arr[i]);
	        else s2.insert(arr[i]);
	    }
	   
	    for(auto i:s1)
	    {
	        v.push_back(i);
	    }
	    for(auto i:s2)
	    {
	        v.push_back(i);
	    }
	    
	    for(int i=0;i<n;i++)
	    {
	        arr[i]=v[i];
	    }
	    
	}
};