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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <chrono>
#include <functional>
#include <cstdlib>
#include <cassert>
using namespace std;

struct Transpozition
{
  int first;
  int second;
};

void print(std::vector<Transpozition>& trans)
{
  std::cout << (trans.size() * 2) << "\n";
  for (int i = 0; i < trans.size(); ++i)
  {
    std::cout << (trans[i].first + 1) << " ";
  }
  for (int i = trans.size()-1; i>=0; --i)
  {
    std::cout << (trans[i].second + 1) << " ";
  }
  std::cout << "\n";
}
struct Cycle
{
  std::vector<int> numbers;
};

int main()
{
  const clock_t begin_time = clock();
  ios::sync_with_stdio(false);
  int n;
  std::cin >> n;
  std::vector<int> numbers;
  for (int i = 0; i < n; ++i)
  {
    int number;
    std::cin >> number;
    numbers.push_back(number);
  }

  std::vector<int> sortedNumbers = numbers;
  std::sort(sortedNumbers.begin(), sortedNumbers.end());
  std::vector<int> numbersNormalized(sortedNumbers.size());
  for (int i = 0; i < numbers.size(); ++i)
  {
    numbersNormalized[i] = std::lower_bound(sortedNumbers.begin(), sortedNumbers.end(), numbers[i])
        -sortedNumbers.begin();
  }
  std::vector<Cycle> sets;
  std::map<int, int> toSetNumber;
  for (int i = 0; i < numbersNormalized.size(); ++i)
  {
    if (toSetNumber.find(i) != toSetNumber.end())
      continue;
    sets.push_back(Cycle());
    int setNumber = sets.size() - 1;
    int current = i;
    do
    {
      current = numbersNormalized[current];
      sets[setNumber].numbers.push_back(current);
      toSetNumber[current] = setNumber;
    } while (current != i);
  }
  std::vector<Transpozition> trans1;
  std::vector<Transpozition> trans2;
  for (int i = 0; i < sets.size(); ++i)
  {
    std::vector<int> cycle = sets[i].numbers;
    if (cycle.size() == 1)
      continue;
    if (cycle.size() == 2)
    {
      trans1.push_back({cycle[0], cycle[1]});
      continue;
    }
    for (int j = 1; j < cycle.size() - j; ++j)
    {
      trans1.push_back({ cycle[j], cycle[cycle.size()-j]});
    }
    trans2.push_back({cycle[0], cycle[1]});
    for (int j = 2; j < cycle.size() + 1 - j; ++j)
    {
      trans2.push_back({ cycle[j], cycle[cycle.size()+1 - j] });
    }
  }
  if (trans1.empty())
  {
    std::cout << "0\n";
    return 0;
  }
  if (trans2.empty())
  {
    std::cout << "1\n";
    print(trans1);
    return 0;
  }
  std::cout << "2\n";
  print(trans1);
  print(trans2);
  return 0;
  //std::cout << float(clock() - begin_time) / CLOCKS_PER_SEC << "\n";
};