#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
 
struct Timer {
    std::chrono::high_resolution_clock::time_point start;
    Timer() : start(std::chrono::high_resolution_clock::now()) {}
    ~Timer() {
        auto stop = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
        std::cout << "Time: " << duration.count() << " ms\n";
    }
};
template<typename T>
 
void Firstalg(T x[], int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=0;i<n;i++){
		for(int j=0; j<n-i-1; j++){
			a+=1;
			if(x[j]>x[j+1]){
				swap(x[j],x[j+1]);
				b+=1;
			}
		}
	}
}
 
template<typename T>
void Secondalg(T &x, int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=1; i<n; i++){
		int key = x[i];
		int j=i-1;
		while(j>=0){
			a+=1;
			if(x[j]>key){
			x[j+1]=x[j];
			b+=1;
			j--;
			}else{break;}
		}
		x[j+1]=key;
	}
}
 
int main() {
	int sort, comp;
	int n = 10000;
	int x[n];
	for (int i=0; i<n; i++){
		x[i]=rand() % 10001;
	};
 
	for (int i=0; i<100; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	{
		Timer t;
		Firstalg(x,sort,comp,n);
	}
 
}		
/*	Secondalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
 
	Firstalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;*/

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2hyb25vPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IFRpbWVyIHsKICAgIHN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6OnRpbWVfcG9pbnQgc3RhcnQ7CiAgICBUaW1lcigpIDogc3RhcnQoc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCkpIHt9CiAgICB+VGltZXIoKSB7CiAgICAgICAgYXV0byBzdG9wID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CiAgICAgICAgYXV0byBkdXJhdGlvbiA9IHN0ZDo6Y2hyb25vOjpkdXJhdGlvbl9jYXN0PHN0ZDo6Y2hyb25vOjptaWxsaXNlY29uZHM+KHN0b3AgLSBzdGFydCk7CiAgICAgICAgc3RkOjpjb3V0IDw8ICJUaW1lOiAiIDw8IGR1cmF0aW9uLmNvdW50KCkgPDwgIiBtc1xuIjsKICAgIH0KfTsKdGVtcGxhdGU8dHlwZW5hbWUgVD4KCnZvaWQgRmlyc3RhbGcoVCB4W10sIGludCAmYSwgaW50ICZiLCBpbnQgbil7CglhPTA7CgliPTA7Cglmb3IoaW50IGk9MDtpPG47aSsrKXsKCQlmb3IoaW50IGo9MDsgajxuLWktMTsgaisrKXsKCQkJYSs9MTsKCQkJaWYoeFtqXT54W2orMV0pewoJCQkJc3dhcCh4W2pdLHhbaisxXSk7CgkJCQliKz0xOwoJCQl9CgkJfQoJfQp9Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgp2b2lkIFNlY29uZGFsZyhUICZ4LCBpbnQgJmEsIGludCAmYiwgaW50IG4pewoJYT0wOwoJYj0wOwoJZm9yKGludCBpPTE7IGk8bjsgaSsrKXsKCQlpbnQga2V5ID0geFtpXTsKCQlpbnQgaj1pLTE7CgkJd2hpbGUoaj49MCl7CgkJCWErPTE7CgkJCWlmKHhbal0+a2V5KXsKCQkJeFtqKzFdPXhbal07CgkJCWIrPTE7CgkJCWotLTsKCQkJfWVsc2V7YnJlYWs7fQoJCX0KCQl4W2orMV09a2V5OwoJfQp9CgppbnQgbWFpbigpIHsKCWludCBzb3J0LCBjb21wOwoJaW50IG4gPSAxMDAwMDsKCWludCB4W25dOwoJZm9yIChpbnQgaT0wOyBpPG47IGkrKyl7CgkJeFtpXT1yYW5kKCkgJSAxMDAwMTsKCX07CgkKCWZvciAoaW50IGk9MDsgaTwxMDA7IGkrKyl7CgkJY291dDw8eFtpXTw8IiAiOwoJfTsKCWNvdXQ8PGVuZGw7Cgl7CgkJVGltZXIgdDsKCQlGaXJzdGFsZyh4LHNvcnQsY29tcCxuKTsKCX0KCQp9CQkKLyoJU2Vjb25kYWxnKHgsc29ydCxjb21wLG4pOwoJZm9yIChpbnQgaT0wOyBpPG47IGkrKyl7CgkJY291dDw8eFtpXTw8IiAiOwoJfTsKCWNvdXQ8PGVuZGw7Cgljb3V0PDwi0JrRltC70YzQutGW0YHRgtGMINC/0L7RgNGW0LLQvdGP0L3RjCAiPDxzb3J0PDxlbmRsPDwi0JrRltC70YzQutGW0YHRgtGMINC/0LXRgNC10YHRgtCw0L3QvtCy0L7QuiAiPDxjb21wOwoJCglGaXJzdGFsZyh4LHNvcnQsY29tcCxuKTsKCWZvciAoaW50IGk9MDsgaTxuOyBpKyspewoJCWNvdXQ8PHhbaV08PCIgIjsKCX07Cgljb3V0PDxlbmRsOwoJY291dDw8ItCa0ZbQu9GM0LrRltGB0YLRjCDQv9C+0YDRltCy0L3Rj9C90YwgIjw8c29ydDw8ZW5kbDw8ItCa0ZbQu9GM0LrRltGB0YLRjCDQv9C10YDQtdGB0YLQsNC90L7QstC+0LogIjw8Y29tcDsqLw==