#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <time.h>

using namespace std;

//#define VIDEOGAME

#define MAX_N 100

int n;
int instance[MAX_N +1];
     // nelle posizioni [1..n] contiene una permutazione di {1,...,n}
int opt_dist, best_so_far_dist;
int history[MAX_N +1][MAX_N +1];
int best_so_far_sol[MAX_N +1][MAX_N +1];
int num_fairies;


inline int max(int a, int b){ return (a<b) ? b : a; }
inline int min(int a, int b){ return (a<b) ? a : b; }
inline void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
inline void prompt() {
#ifdef VIDEOGAME
  cout << " ... press RETURN to continue ...";
  getchar(); cout << endl;
#endif
}

void displayPerm(int perm[], bool with_n, ostream &out) {
#ifdef VIDEOGAME
  if(with_n) out << n << endl;
   for(int i=1; i<= n; i++)
 	out << perm[i] << " ";
   out << endl;
#endif
}

void displayHistory(int length, ostream &out) {
  out << "BEGIN - An history of " << length << " steps:" << endl;
   for(int i=0; i<= length; i++)
     displayPerm(history[i], false, out);
   out << "END history" << endl;
}

void readInput() {
   ifstream fin( "input.txt" ); assert( fin );
   fin >> n;
   for(int i=1; i<= n; i++)  fin >> instance[i];
   fin.close();
}

void writeOutput() {
   ofstream fout( "output.txt" ); assert( fout );
   fout << opt_dist << endl;
   for(int i=0; i <= best_so_far_dist; i++)
     displayPerm( best_so_far_sol[i], false, fout );
   fout.close();
}


bool isSorted(int perm[]) {
   for(int i = 1; i <= n; i++)
       if(perm[i] != i) return false;
   return true;
}

bool reverse(int perm[], int first, int last) {
   while(first < last)   swap( perm[first++], perm[last--] );
}

void copyPerm(int perm1[], int perm2[] ) { for(int i=1; i <= n; i++)  perm2[i] = perm1[i]; }


int lowerBound(int perm[]) {
  int dislikes = 0;
  if(perm[1] != 1) dislikes++; if(perm[n] != n) dislikes++;
  for(int i = 2; i <= n; i++)
    if(perm[i] != perm[i-1])  dislikes++;
  return (dislikes/2) + (dislikes % 2);
}

void generaPerm_random_uniform(int perm[]) {
   for(int i=n; i > 1; i--)
     swap( perm[i], perm[ (rand() % i) + 1 ] );
}

void generaPerm_random_realistic_bio_model(int perm[], int k) {
  for(int i=1; i <= n; i++)  perm[i] = i;
  for(int i=1; i <= k; i++)  {
     int width = (rand() % n) + 1;
     int first = (rand() % (n-width) ) + 1;
     reverse(perm, first, first+width);
  }
}




void bestSol(int perm[], int steps_done) {
   num_fairies++;
   cout << "chiamato con steps_done = " << steps_done << endl;
   cout << "best_so_far_dist = " << best_so_far_dist << endl;
   displayPerm(perm, true, cout);
   copyPerm(perm, history[steps_done]);
   displayHistory(steps_done, cout);
   prompt();
   //   if( steps_done >= best_so_far_dist) return;
   if( steps_done + lowerBound(perm) >= best_so_far_dist) return;
   if( isSorted(perm) ) {
      best_so_far_dist = steps_done;
      for(int i=0; i <= best_so_far_dist; i++)
         copyPerm(history[i], best_so_far_sol[i]);
      return;
   }
   for(int first = 1; first < n; first++)
      for(int last = first+1; last <= n; last++) {
           reverse(perm, first, last);
           bestSol(perm, steps_done +1);
           reverse(perm, first, last);
      }
}

int main() {
   srand(time(NULL));
   readInput();
   best_so_far_dist = n+1; // idea! esiste sempre una soluzione in al piu' n passi.
   num_fairies = 0;
   bestSol(instance, 0);
   opt_dist = best_so_far_dist;
   writeOutput();
   cout << "Fatine ricorsine impiegate: " << num_fairies << endl;
   return 0;
}