#include <iostream>
#include <ctime>
using namespace std;
int pris=0,srav=0;
void qsort(int a[], int n) {
int i=0;
int j=n-1;
int mid=a[n/2];
++pris;
while (i<=j) {
++srav;
while(a[i]<mid) {
i++;
++srav;
}
++srav;
while(a[j]>mid) {
j--;
++srav;
}
if (i<=j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
pris+=3;
i++;
j--;
}
}
if(j>0) {
qsort(a,j+1);
}
if (i<n) {
qsort(a,n-i);
}
}
int main() {
int n,f=0,sumpris=0,sumsrav=0,i=0;
cin>>n;
srand(time(NULL));
int a[n];
for (f=0;f<7;++f) {
i=0;
srav=0;
pris=0;
while (i<n) {
a[i]=rand()%150;
++i;
}
qsort(a,n);
sumsrav+=srav;
sumpris+=pris;
cout<<"сравнений="<<srav<<" "<<"присваиваний="<<pris<<endl;
}
cout<<"среднее сравнений="<<sumsrav/7<<" "<<"среднее присваиваний="<<sumpris/7;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3RpbWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgcHJpcz0wLHNyYXY9MDsKCnZvaWQgcXNvcnQoaW50IGFbXSwgaW50IG4pIHsKICAgIGludCBpPTA7CiAgICBpbnQgaj1uLTE7CiAgICBpbnQgbWlkPWFbbi8yXTsKICAgICsrcHJpczsKICAgIHdoaWxlIChpPD1qKSB7CiAgICAgICAgKytzcmF2OwogICAgICAgIHdoaWxlKGFbaV08bWlkKSB7CiAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgKytzcmF2OwogICAgICAgIH0KICAgICAgICArK3NyYXY7CiAgICAgICAgd2hpbGUoYVtqXT5taWQpIHsKICAgICAgICAgICAgai0tOwogICAgICAgICAgICArK3NyYXY7CiAgICAgICAgfQogICAgICAgIGlmIChpPD1qKSB7CiAgICAgICAgICAgIGludCB0PWFbaV07CiAgICAgICAgICAgIGFbaV09YVtqXTsKICAgICAgICAgICAgYVtqXT10OwogICAgICAgICAgICBwcmlzKz0zOwogICAgICAgICAgICBpKys7CiAgICAgICAgICAgIGotLTsKICAgICAgICB9CiAgICB9CiAgICBpZihqPjApIHsKICAgICAgICBxc29ydChhLGorMSk7CiAgICB9CiAgICBpZiAoaTxuKSB7CiAgICAgICAgcXNvcnQoYSxuLWkpOwogICAgfQp9CgppbnQgbWFpbigpIHsKCWludCBuLGY9MCxzdW1wcmlzPTAsc3Vtc3Jhdj0wLGk9MDsKCWNpbj4+bjsKCXNyYW5kKHRpbWUoTlVMTCkpOwoJaW50IGFbbl07Cglmb3IgKGY9MDtmPDc7KytmKSB7CglpPTA7CglzcmF2PTA7CglwcmlzPTA7Cgl3aGlsZSAoaTxuKSB7CgkJYVtpXT1yYW5kKCklMTUwOwoJCSsraTsKCX0KCXFzb3J0KGEsbik7CglzdW1zcmF2Kz1zcmF2OwoJc3VtcHJpcys9cHJpczsKICAgIGNvdXQ8PCLRgdGA0LDQstC90LXQvdC40Lk9Ijw8c3Jhdjw8IiAiPDwi0L/RgNC40YHQstCw0LjQstCw0L3QuNC5PSI8PHByaXM8PGVuZGw7Cgl9Cgljb3V0PDwi0YHRgNC10LTQvdC10LUg0YHRgNCw0LLQvdC10L3QuNC5PSI8PHN1bXNyYXYvNzw8IiAiPDwi0YHRgNC10LTQvdC10LUg0L/RgNC40YHQstCw0LjQstCw0L3QuNC5PSI8PHN1bXByaXMvNzsKCXJldHVybiAwOwp9