#include <iostream>
#include <set>
#include <map>
#include <list>
#include <algorithm>
#include <stdexcept>
#include <sstream>

using namespace std;

class Transposition {
  private:
    int n, k;

  public:
    Transposition(int n_, int k_): n(n_), k(k_) {
      if (n == k) {
        ostringstream os;
        os << "Transposition(" << n_ << ", " << k_ << ")";
        throw invalid_argument(os.str());
      }
    }

    int operator()(int i) const {
      if (i == k)
        return n;
      else if (i == n)
        return k;
      else
        return i;
    }

    friend ostream& operator<<(ostream& stream, const Transposition& t) {
      return stream << "(" << t.n << " " << t.k << ")";
    }
};

class Permutation {
  private:
    list<Transposition> perm;

  public:
    Permutation(): perm() {}
    Permutation(int n_, int k_): perm({Transposition(n_, k_)}) {}
    Permutation(const Transposition& t): perm({t}) {}
    Permutation(const map<int, int>& pi) {
      set<int> seen{};
      for (auto p: pi) {
        if (seen.find(p.first) != seen.end())
          continue;
    
        list<int> cycle{p.first};
        while (pi.at(cycle.back()) != p.first)
          cycle.push_back(pi.at(cycle.back()));
        seen.insert(cycle.begin(), cycle.end());
    
        if (cycle.size() <= 1)
          continue;
    
        list<int>::const_iterator curr = cycle.begin(),
          next = ++(cycle.begin());
        for (; next != cycle.end(); curr++, next++)
          perm.push_back(Transposition{*curr, *next});
      }
    }

    int operator()(int i) const {
      for (list<Transposition>::const_reverse_iterator it = perm.rbegin();
        it != perm.rend();
        it++)
        i = (*it)(i);
      return i;
    }

    const list<Transposition>& getPerm() const {
      return perm;
    }

    Permutation& operator*=(Permutation o) {
      perm.splice(perm.begin(), o.perm);
      return *this;
    }
    friend Permutation operator*(Permutation a, const Permutation& b) {
      return a *= b;
    }

    friend ostream& operator<<(ostream& stream, const Permutation& p) {
      list<Transposition>::const_iterator curr = p.perm.begin(),
        next = ++(p.perm.begin());
    
      for (; curr != p.perm.end(); curr++, next++) {
        stream << *curr;
        if (next != p.perm.end())
          stream << " ";
      }
      return stream;
    }
};

void ausgeben(ostream& stream, const string& c, const Permutation& p, int n) {
  for (int i = 0; i < n; i++) {
    cout << c << "[" << i << "]: " << p(i);
    if (i != n - 1)
      cout << "  ";
  }
  cout << endl;
}

int main() {
  int n;
  cout << "n: "; cin >> n;
  map<int, int> pi;
  for (int i = 0; i < n; i++) {
    cout << "pi[" << i << "]: ";
    cin >> pi[i];
  }

  Permutation p{pi};
  cout << p << endl;
  ausgeben(cout, "p", p, n);

  Permutation q{};
  for (Transposition t: p.getPerm())
    q = Permutation{t} * q;
  ausgeben(cout, "q", q, n);

  return 0;
}