Cerinţa

Într-un depozit există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

Date de intrare

Fişierul de intrare pachete.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii. Al i-lea număr reprezintă numărul pachetului aflat în spațiul de depozitare i.

Date de ieşire

Fişierul de ieşire pachete.out va conţine pe prima linie numărul M, reprezentând numărul de manevre efectuate. Pe fiecare dintre următoarele M linii se descrie o manevră, prin două numere i j, cu semnificația: se ia pachetul din spațiul i și se mută în spațiul j.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• pentru fiecare manevră i j efectuată, 1 ≤ i,j ≤ n+1, i ≠ j, iar spațiul j trebuie să fie gol
• numărul de manevre realizate nu trebuie să fie minim

Exemplu

pachete.in

5
2 5 4 3 1 

pachete.out

7
1 6
5 1
2 5
6 2
3 6
4 3
6 4

Explicație

Pachetele se vor muta în felul urmator.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("pachete.in");
ofstream cout("pachete.out");

int n , p , cnt , v[1005];

struct poz
{
    int i , j;
} a[1005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    p = n + 1;
    v[p] = 0;
    for(int i = 1; i <= n ; i++)
        if(v[i] != i)
        {
            if(i != p)
            {
                cnt++;
                swap(v[i],v[p]);
                a[cnt].i = i;
                a[cnt].j = p;
                p = i;
            }
            for(int j = 1; j <= n + 1; j++)
                if(v[j] == i)
                {
                    cnt++;
                    a[cnt].i = j;
                    a[cnt].j = p;
                    swap(v[p],v[j]);
                    p = j;
                    break;
                }
        }
    cout << cnt << '\n';
    for (int i = 1; i<=cnt; i++)
        cout << a[i].i << " " << a[i].j << '\n';
}