#include <iostream>
#include <math.h>>
#include <fstream>

using namespace std;


template <class G>
				class Nodo{
					private:
						Nodo<G>* left;
						Nodo<G>* right;
						Nodo<G>* parent;
						G *key;
					public:
						Nodo(G k){
							this->key=new G(k);
							left=right=parent=NULL;



						}


						Nodo<G>* getParent(){
							return parent;
						}
						Nodo<G>* getLeft(){
							return left;
						}
						Nodo<G>* getRight(){
							return right;
						}

						G getKey(){
							return *key;
						}


						void setLeft(Nodo<G>* left){
							this->left=left;
						}
						void setRight(Nodo<G>* right){
							this->right=right;
						}

						void setParent(Nodo<G>* parent){
							this->parent=parent;
						}
						void setKey(G item){
							this->key=new G(item);
						}

				};



template <class H>
			class Albero{
				private:
					Nodo<H>* root;

				public:
					Albero(){
						root=NULL;
					}
					Albero<H>* insert(H item){
						Nodo<H>* nuovo=new Nodo<H>(item);
						if(root==NULL){
							root=nuovo;
							return this;
						}


						Nodo<H>* iter=root;
						Nodo<H>* par=NULL;
						while(iter!=NULL){
							par=iter;
							if(iter->getKey()<item){
								iter=iter->getRight();
							}else{
								iter=iter->getLeft();
							}



						}

						if(par==NULL){
							return NULL;
						}
						else{
							if(par->getKey()<item){
								par->setRight(nuovo);
							}else
								par->setLeft(nuovo);
						}

						nuovo->setParent(par);
						return this;
					}








					void inorder(){
						_inorder(root);
					}

					void _inorder(Nodo<H>* start){
						if(start!=NULL){
							_inorder(start->getLeft());
							cout<<start->getKey()<<" ";
							_inorder(start->getRight());
						}

					}





					void ricerca(H item){
						_ricerca(root,item);
					}


					Nodo<H>* _ricerca(Nodo<H>* start,H item){
						while(start!=NULL && start->getKey()!=item){
							if(start->getKey()<item){
								start=start->getRight();
							}else{
								start=start->getLeft();
							}


						}
							if(start==NULL){

								return NULL;
							}else{
						//		cout<<start->getKey();
								return start;
							}


					}


					void mini(){
						return _mini(root);

					}

					Nodo<H>* _mini(Nodo<H>* start){
						if(start->getLeft()!=NULL){

							start=start->getLeft();
						}

						return start;


					}


					H* successore(H item){
						Nodo<H>* ric=_ricerca(root,item);
						if(ric==NULL){
							return NULL;
						}
						Nodo<H>* succ=_successore(ric);
						if(succ==NULL){
							return NULL;
						}
						cout<<succ->getKey();
						return new H(succ->getKey());
					}

					Nodo<H>* _successore(Nodo<H>* start){
							if(start->getRight()!=NULL){
								return _mini(start->getRight());
							}

							Nodo<H>* par=start->getParent();

							while(par!=NULL && par->getKey()<start->getKey()){

								par=par->getParent();
							}



							return par;





					}




					void cancella(H item){
						_cancella(root,item);
					}



					void _cancella(Nodo<H>* start,H item){
	Nodo<H>* ric=_ricerca(start,item);

	if(ric==NULL){
		return;
	}

	Nodo<H>* par=ric->getParent();


	if(!ric->getLeft() || !ric->getRight()){
		Nodo<H>* under=ric->getRight();
		if(ric->getLeft()){
			under=ric->getLeft();
		}

		if(par==NULL){
			root=under;
		}
		else{
			if(par->getLeft()==ric){
				par->setLeft(under);
			}else{
				par->setRight(under);
			}

		}

		if(under!=NULL){
			under->setParent(par);
		}



	}else{
		Nodo<H>* succ=_successore(ric);
		ric->setKey(succ->getKey());
		_cancella(ric->getRight(),succ->getKey());

	}

	return;

}



					int bilanciamento(H item){
						return _bilanciamento(root,item);
					}

					int _bilanciamento(Nodo<H>* start, H item){
						Nodo<H>* ric=_ricerca(start,item);
						int i=0;
						Nodo<H>* sinistra=ric;
						while(sinistra->getLeft()!=NULL){

							sinistra=sinistra->getLeft();

							i++;
						}
						int j=0;
						while(ric->getRight()!=NULL){
							ric=ric->getRight();
							j++;
						}
						cout<<i<<j;

						i=abs(i-j);
						cout<<"   "<<i;
					}



					void peso(H item){
						Nodo<H>* ric=_ricerca(root,item);
						int sx=0;
						int dx=0;
					//	int bal=ric->getKey();
						int lb=_peso(ric->getLeft(),sx);
						int rb=_peso(ric->getRight(),dx);
						cout<<abs(lb-rb);
						// bal += abs(lb + rb);
						//cout<<bal;
					}


					int _peso(Nodo<H>* start,int &num){
						if(start!=NULL){
							num++;
							_peso(start->getLeft(),num);
							_peso(start->getRight(),num);
						}

						return num;




					}
					void leaf(){
						int c=0;
						c= _leaf(c,root);
						cout<<c;
					}


					int _leaf(int &c,Nodo<H>* start){

						if(start->getRight()==NULL && start->getLeft()==NULL){
							c++;



						}



						if(start->getRight()!=NULL){
							_leaf(c,start->getRight());
						}
						if(start->getLeft()!=NULL){
							_leaf(c,start->getLeft());
						}

						return c;
					}


			};




int main(){

	Albero<int>* bst=new Albero<int>();

	bst->insert(3);
	bst->insert(48);
	bst->insert(158);
	bst->insert(6);
	bst->insert(224);
	bst->insert(273);
	bst->insert(297);
	bst->insert(150);
	bst->insert(280);
	bst->insert(200);
//	bst->cancella(127);
	bst->inorder();
//	bst->predecessore(230);
//	bst->successore(223);
//	bst->ricerca(4);
	bst->bilanciamento(158);
//	bst->peso(158);
//	bst->leaf();
}
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int selectionsort(int* vett, int n){
    int min;
    int sum = 0;
    for(int i = 0; i < n; i++){
        min = i;
        for(int j = i+1; j < n; j++)
            if(vett[j] < vett[min])
                min = j;
        sum += min -i;
        swap(vett[i], vett[min]);

    }

    return sum;
}


int main(){

    ifstream in("input.txt");
    ofstream out("output.txt");

    for(int i = 0; i < 100; i++){
        int n;
        in >> n;
        int* vett = new int[n];
        for(int j = 0; j < n; j++)
            in >> vett[j];
        out << selectionsort(vett, n) << endl;

        delete [] vett;
    }



    return 0;
}
#include <iostream>
#include <fstream>
using namespace std;

int insertionsort(int* vett, int n){
    int i, j, tmp;
    int contatore = 0;
    for(int i = 1; i < n; i++){
        j = i;
        while(j > 0 && vett[j-1] > vett[j]){
            tmp = vett[j];
            vett[j] = vett[j-1];
            vett[j-1] = tmp;
            j--;
            contatore++;
        }
    }


    return contatore;
}


int main(){

    ifstream in("input.txt");

    ofstream out("output.txt");

    for(int i = 0; i < 10; i++){
        int n;
        in >> n;
        int* vett = new int[n];
        for(int j = 0; j < n; j++)
            in >> vett[j];
        int contatore = insertionsort(vett, n);
        out << contatore << endl;

    }


    return 0;
}
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

void Merge(int* vett, int sx, int c, int dx){
    int i = sx;
    int j = c+1;
    int k = 0;
    int tmp[dx-sx+1];

    while(i <= c && j <= dx){
        if(vett[i] < vett[j]){
            tmp[k] = vett[i];
            i++;
        }
        else{
            tmp[k] = vett[j];
            j++;
        }
        k++;
    }

    while(i <= c){
        tmp[k] = vett[i];
        i++; k++;
    }

    while(j <= dx){
        tmp[k] = vett[j];
        j++; k++;
    }

    for(int i =  sx; i <= dx; i++)
        vett[i] = tmp[i - sx];
}

void MergeSort(int* vett, int sx, int dx, int &contatore){
    if(sx < dx){
        int c = (sx+dx)/2;
        contatore += vett[sx];
        MergeSort(vett, sx, c, contatore);
        MergeSort(vett, c+1, dx, contatore);
        Merge(vett, sx, c, dx);

    }
}




int main(){

    ifstream in("input.txt");
    ofstream out("output.txt");

    for(int i = 0; i < 100; i++){
        int n; in >> n;
        int* vett = new int[n];
        for(int j = 0; j < n; j++){
            int tmp; in >> tmp;
            vett[j] = tmp;
        }
        int contatore = 0;
        MergeSort(vett, 0, n-1, contatore);
        out << contatore << endl;
        delete vett;
    }

}