//ABcDexter
#include<bits/stdc++.h>
using namespace std;
 
int count=0; //count function calls
 
int MedianOf3P(int a[],int p, int r) 
{
    int x=a[p],y=a[(r-p)/2+p],z=a[r-1],i=p-1,j=r;
    if (y>x && y<z || y>z && y<x ) x=y;
    else if (z>x && z<y || z>y && z<x ) x=z;
    while (true) 
    {
        do  {j--;} while (a[j] > x);
        do  {i++;} while (a[i] < x);
        if  (i < j) std::swap(a[i],a[j]);
        else return j+1;
    }
}
void QuickSort_Median(int a[],int start,int end) 
{
    int pivot;
    if (end-start<2) return;
    pivot=MedianOf3P(a,start,end);
    ::count++; /*function call*/ QuickSort_Median(a,start,pivot);
    ::count++; /*function call*/ QuickSort_Median(a,pivot,end);
}
 
int i,n,t;
int main(){
	n=15; int A[n];
	for(i=0,t=1048576;i<n;i++)
	{	A[i]=(rand()%t);
	}
	for(i=0;i<n;i++)
		cout<<A[i]<<",";
 
	QuickSort_Median(A,0,n); cout<<"\nsorted:\n";
	for(i=0;i<n;i++)
		cout<<A[i]<<",";
	cout<<"Ans : "<<::count<<endl;
 
}

Ly9BQmNEZXh0ZXIKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBjb3VudD0wOyAvL2NvdW50IGZ1bmN0aW9uIGNhbGxzCgppbnQgTWVkaWFuT2YzUChpbnQgYVtdLGludCBwLCBpbnQgcikgCnsKICAgIGludCB4PWFbcF0seT1hWyhyLXApLzIrcF0sej1hW3ItMV0saT1wLTEsaj1yOwogICAgaWYgKHk+eCAmJiB5PHogfHwgeT56ICYmIHk8eCApIHg9eTsKICAgIGVsc2UgaWYgKHo+eCAmJiB6PHkgfHwgej55ICYmIHo8eCApIHg9ejsKICAgIHdoaWxlICh0cnVlKSAKICAgIHsKICAgICAgICBkbyAge2otLTt9IHdoaWxlIChhW2pdID4geCk7CiAgICAgICAgZG8gIHtpKys7fSB3aGlsZSAoYVtpXSA8IHgpOwogICAgICAgIGlmICAoaSA8IGopIHN0ZDo6c3dhcChhW2ldLGFbal0pOwogICAgICAgIGVsc2UgcmV0dXJuIGorMTsKICAgIH0KfQp2b2lkIFF1aWNrU29ydF9NZWRpYW4oaW50IGFbXSxpbnQgc3RhcnQsaW50IGVuZCkgCnsKICAgIGludCBwaXZvdDsKICAgIGlmIChlbmQtc3RhcnQ8MikgcmV0dXJuOwogICAgcGl2b3Q9TWVkaWFuT2YzUChhLHN0YXJ0LGVuZCk7CiAgICA6OmNvdW50Kys7IC8qZnVuY3Rpb24gY2FsbCovIFF1aWNrU29ydF9NZWRpYW4oYSxzdGFydCxwaXZvdCk7CiAgICA6OmNvdW50Kys7IC8qZnVuY3Rpb24gY2FsbCovIFF1aWNrU29ydF9NZWRpYW4oYSxwaXZvdCxlbmQpOwp9CgppbnQgaSxuLHQ7CmludCBtYWluKCl7CgluPTE1OyBpbnQgQVtuXTsKCWZvcihpPTAsdD0xMDQ4NTc2O2k8bjtpKyspCgl7CUFbaV09KHJhbmQoKSV0KTsKCX0KCWZvcihpPTA7aTxuO2krKykKCQljb3V0PDxBW2ldPDwiLCI7CgkJCglRdWlja1NvcnRfTWVkaWFuKEEsMCxuKTsgY291dDw8Ilxuc29ydGVkOlxuIjsKCWZvcihpPTA7aTxuO2krKykKCQljb3V0PDxBW2ldPDwiLCI7Cgljb3V0PDwiQW5zIDogIjw8Ojpjb3VudDw8ZW5kbDsKCQp9