void insert_sort(int v[],int l,int r){

	int i,j,temp;
	
	for (i = l;i <= r;i++){
	    
		temp = v[i];
		for (j = i - 1;j >= l && temp < v[j];j--) v[j + 1] = v[j];
		v[j + 1] = temp;
		
	}
}

void quik_sort(int v[],int l,int r){
    
    std::stack <std::pair <int,int> > s;
    
    s.push({l,r});
    while (!s.empty()){
        
        int L = s.top().first,R = s.top().second;
        int i = L,j = R,flag = v[rand() % (R - L + 1) + L];
        
        s.pop();
        if (R - L <= 32) insert_sort(v,L,R);
        do{
            
            while (v[i] < flag) i++;
            while (v[j] > flag) j--;
            if (i <= j)
                std::swap(v[i],v[j]),i++,j--;
            
        }while (i <= j);
        if (L < j) s.push({L,j});
        if (i < R) s.push({i,R});
        
    }
    
}