main.cpp

#include    <iostream>
#include    <fstream>
using namespace std;
ifstream  fin("pachete_multe.in");
ofstream  fout("pachete_multe.out");

//Strategie 1 O(N^2)
//Cat timp sirul nu e completat 1,2,...n
//1)Iau elementul curent, il mut intr-o casuta goala (n+1)
//2)Iau acel sir[j] pa_int care sir[j] == pozitie_curent index
//3)pe pozitia elementului curent pun pe sir[j]
//4)Pe fosta pozitie a lui sir[j] pun elementul de pe casuta goala(n+1)
//Gata

//Nu functioneaza strategia 1. Gandeste alta

//Strategie 2 ? - Discord

int N,a[100000], nr_mutari = 0,pozitii[100000];
pair <int,int> mutari[100000];


void citeste()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
        fin>>a[i];
    a[N+1] = 0;//casuta goala
}

void initializare_pozitii()
{
	for(int i = 1; i <= N; i++)
	{
		pozitii[a[i]] = i;
	}
	pozitii[0] = N+1;
}

void rezolvare()
{
    int i = 1;
    int index_casuta_goala = N+1;
	//initializez array-ul de pozitii . pozitii[i] = indexul la care se afla valoarea i in sirul data
	initializare_pozitii();
	//for(int i = 0; i <= N; i++)
	//{
	//	cout << pozitii[i] << " ";
	//}
	//cout << endl;
    while(i <= N)
    {
        //punem conditiile astea pt ca in cazul in care a[i] == i
        //sau a[i] == 0 , nu mai e nevoie sa facem mutari aiurea
        //daca a[i] == 0 singura mutare ce trebuie facuta e sa
        if(a[i] != i && a[i] != 0)
        {
            //se muta de pe pozitia i pe pozitia casutei goale
            a[index_casuta_goala] = a[i];
            mutari[nr_mutari++] = make_pair(i,index_casuta_goala);
            //vedem care e pozitia reala in sir unde a[j] == i
            pozitii[a[index_casuta_goala]] = index_casuta_goala;
            //adaugam inca o mutare in sirul de mutari .
            //mutarea j - i
			index_casuta_goala = pozitii[i];
			a[pozitii[i]] = 0;
            mutari[nr_mutari++] = make_pair(index_casuta_goala,i);
            a[i] = i;
			pozitii[0] = pozitii[i];
			pozitii[i] = i;
        }
        else
        {
            //in cazul asta e nevoie de o mutare mai simpla
            //direct de pe pozitia pe care se afla valoarea i
            //pe pozitia asta goala si prafuita
            if(a[i] == 0)
            {
				mutari[nr_mutari++] = make_pair(pozitii[i],i);
				a[i] = i;
				index_casuta_goala = pozitii[i];
				pozitii[i] = i;
				pozitii[0] = index_casuta_goala;
				a[index_casuta_goala] = 0;
				/*
                for(int j = 1; j <= N+1; j++)
                {
                    if(a[j] == i)
                    {
                        mutari[nr_mutari++] = make_pair(j,i);
                        a[i] = i;
                        index_casuta_goala = j;
                        a[j] = 0;
                        break;
                    }
                }
				*/
            }
        }
		//for(int p = 0; p <= N; p++)
		//{
		//	cout << pozitii[p] << " ";
		//}
		//cout << endl;
        i++;
    }

    fout << nr_mutari<<endl;
    for(int i = 0; i < nr_mutari; i++)
    {
        fout << mutari[i].first << " " << mutari[i].second << endl;
    }
}

int main()
{
    citeste();
    rezolvare();
    fin.close();
    fout.close();
    return 0;
}