1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <iostream>
#include <vector>

using namespace std;

string move_output(int move[], int n) {
    string out = "";
    int moves = 0;
    for(int i=1; i<=n; i++) {
        if(move[i] > 0) {
            moves+=2;
            move[move[i]] = 0;
        }
    }
    out += to_string(moves) + '\n';
    for (int i=1; i<=n; i++) {
        if(move[i] > 0) out += to_string(i) + " ";
    }
    for (int i=n; i>0; i--) {
        if(move[i] > 0) out += to_string(move[i]) + " ";
    }
    out += '\n';
    return out;
}

int main() {
    vector<string> results;
    int N;
    cin >> N;

    int row[N+1];
    int possible[3001] = {0};
    for(int i=1; i<=N; i++) {
        cin >> row[i];
        possible[row[i]] = i;
    }

    int turns = 0;
    int goal[N+1];
    int j = 1;
    for(int i=0; i<3001; i++) {
        if(possible[i] > 0) {
            goal[j++] = possible[i];
        }
    }

    // cout << "goal" << endl;    
    // for(int i=1; i<=N; i++)
    //     cout << i << ": " << goal[i] << ": " << row[goal[i]] << endl;

    //turns
    bool sorted;
    do {
        turns++;
        int move[N+1];
        //zero
        for(int i = 0; i<=N; i++) move[i] = 0;
        //new move
        sorted = true;
        for(int i = 1; i<=N; i++) {
            //zamieniają się wzajemnie na właściwe miejsca?
            if (move[i] > 0) continue;
            if (i == goal[i]) continue;
            sorted = false;
            if (goal[goal[i]]==i) {
                move[i] = goal[i];
                move[goal[i]] = i;
            } else {
                if (move[goal[i]] == 0){
                    move[i] = goal[i];
                    move[goal[i]] = i;
                }
            }
        }
        if (sorted) break;

        // cout << "move\n";
        // for(int i=1; i<=N; i++)
        //     cout << i << ": " << move[i] << endl;
        
        //adapt move to goal
        for(int i = 1; i <= N; i++) {
            int g = goal[i];
            int new_g = move[g];
            if (new_g > 0)
                goal[i] = new_g;
        }

        // cout << "updated goal\n";
        // for(int i=1; i<=N; i++)
        //     cout << i << ": " << goal[i] << endl;
        // cout << endl;
                
        results.push_back (move_output(move, N));

    } while(!sorted); 
    cout << --turns << endl;
    for(int i=0; i<results.size(); i++)
        cout << results[i];
}