Real problems.
Your next challenge.

Problem summary

Sort a permutation using adjacent swaps. A swap is legal only if neither chosen element is currently at its correct position. A legal sorting sequence is guaranteed to exist; its length need not be minimal.

Source clarification. The construction follows the official editorial: https://infos.infosbg.com/files/Contests/ETI/2015/C/analyses/swap_analysis.pdf. Different legal output sequences are accepted.

Constraints

1 ≤ N ≤ 100; the permutation is guaranteed sortable under the restriction.

Worked example

Original statement sample.

5
1 2 5 3 4

2
3 4
4 5

Solution analysis

1. Fix target values m=1…N in order. Find m at position j. Normally swap it left with its predecessor. Do not do that immediately when the predecessor equals j: moving that value to position j would freeze it and might block still-unsorted values.
2. In that special case scan left across the chain a[i]=i+1. If the chain reaches m, moving m all the way left sorts that entire chain safely. Otherwise the value just before the chain is larger than all chain positions; bubble that value right through the chain and m. This shifts m left without freezing a blocking value.
3. For1,2,5,3,4, target3 moves from position4 to3 by swap(3,4), yielding1,2,3,5,4. Target4 then moves by swap(4,5), completing the sort. For the more delicate6,5,3 pattern inside an unresolved block, blindly moving3 left would freeze5; the chain rotation avoids that trap.

Why it works

An element already at its own position can never move again; the promised sortable input therefore has no fixed barrier separating a value from its target. The construction preserves this property: an ordinary swap does not freeze the displaced larger value, while a special rotation either sorts an entire consecutive-value block or displaces a value larger than the block to its right. Thus every emitted swap has two unfixed endpoints, the fixed prefix never changes, and m moves left until its correct position. Every swap exchanges an inverted adjacent pair, so termination also follows from the decreasing inversion count.

Watch out. Ordinary bubble sort can freeze a value too early and make the remaining task impossible. Never swap a correct element. The guarantee of sortability is essential. Output positions, not the values occupying them.

An independently written complete program with standard headers.

#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>permutation(n+1);
    for(int i=1;i<=n;i++){
        cin>>permutation[i];
    }
    vector<pair<int,int>>operations;
    auto exchange=[&](int left){
        swap(permutation[left],permutation[left+1]);
        operations.push_back({left,left+1});
    };
    for(int target=1;target<=n;target++){
        int position=target;
        while(permutation[position]!=target){
            position++;
        }
        while(position>target){
            if(permutation[position-1]!=position){
                exchange(position-1);
                position--;
            }
            else{
                // Avoid freezing the right-shifted consecutive-value chain.
                int before=position-1;
                while(before>=target&&permutation[before]==before+1){
                    before--;
                }
                if(before<target){
                    for(int left=position-1;left>=target;left--){
                        exchange(left);
                    }
                    position=target;
                }
                else{
                    for(int left=before;left<position;left++){
                        exchange(left);
                    }
                    position--;
                }
            }
        }
    }
    cout<<operations.size()<<'\n';
    for(auto[left,right]:operations){
        cout<<left<<' '<<right<<'\n';
    }
}