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
// fot: Fotografia | 2022-12-15 | Solution by Mikołaj Zabłocki (Dominik Korsa)
// https://sio2.mimuw.edu.pl/c/pa-2022-1/p/fot/

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;
  vector<pair<int, int>> heights(n);
  for (int i = 0; i < n; ++i) {
    auto &height = heights[i];
    cin >> height.first;
    height.second = i;
  }
  auto heightsSorted = heights;
  sort(heightsSorted.begin(), heightsSorted.end());
  for (int i = 0; i < n; ++i) heights[heightsSorted[i].second].second = i;

  vector<deque<int>> rounds;

  while (true) {
    vector<bool> isUsed(n, false);
    deque<int> changes;
    for (int i = 0; i < n; ++i) {
      int j = heights[i].second;
      if (j == i || isUsed[i] || isUsed[j]) continue;
      changes.push_front(i);
      changes.push_back(j);
      isUsed[i] = true;
      isUsed[j] = true;
      swap(heights[i], heights[j]);
    }
    if (changes.size() == 0) break;
    rounds.push_back(changes);
  }

  cout << rounds.size();
  for (auto &round: rounds) {
    cout << '\n' << round.size() << '\n';
    for (int i: round) cout << i + 1 << ' ';
  }

  cout << endl;
  return 0;
}