/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Fevrier 2005                   */

import java.io.*;

public class Complexite {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
  
  /* Fonction de creation d'un tableau d'entiers          */
  /* tires au hasard dans l'intervalle [0,99]             */
  /* n : nombre d'entiers du tableau                      */
  /* Resultat fonction : Tableau de n entiers             */
  
  public static int [] creationTableauAleatoire(int n) {
    int [] m = new int[n];
    for ( int i = 0 ; i < n ; i++ )
      m[i] =(int) (Math.random()*(100));
    return(m);
  }

  /* Fonction d'affichage d'un tableau d'entiers          */
  /* t : Tableau d'entier a afficher                      */
  
  public static void affichageTableau(int [] t) {
    for ( int i = 0 ; i < t.length ; i++ )
      System.out.print(" "+t[i]);
    System.out.println();
  }

  /* Fonction de traitement d'un tableau d'entiers vis    */
  /* a vis d'une valeur v de maniere a regrouper dans     */
  /* la partie gauche toutes les valeurs plus petite      */
  /* que v et dans la partie droite toutes les valeurs    */
  /* plus grandes que v                                   */
  /* t : Tableau d'entiers a traiter                      */
  /* v : Valeur de borne a traiter sur le tableau t       */
  
  public static void traitement(int [] t,int v) {
    int nba = 2;
    int nbt = 0;
    int g = 0;
    int d = t.length-1;
    nbt++;
    while ( g < d ) {
      nbt++;
      nbt += 2;
      while ( ( g < t.length ) && ( t[g] <= v ) ) {
        nbt += 2;
        nba++;
        g++; }
      nbt += 2;
      while ( ( d >= 0 ) && ( t[d] > v ) ) {
        nbt += 2;
        nba++;
        d--; }
      nbt++;
      if ( g < d ) {
      System.out.println("Permutation "+g+" "+d);
        nba += 3;
        int temp = t[g]; 
        t[g] = t[d];
        t[d] = temp; } }
    int N = t.length;
    System.out.println("Nombre de tests minimum          : "+(2*N+7));
    System.out.println("Nombre d'affectations minimum    : "+(N+2));
    System.out.println("Nombre de tests maximum          : "+(6*(N/2)+2*N+7));
    System.out.println("Nombre d'affectations maximum    : "+(3*(N/2)+N+2));
    System.out.println("Nombre de tests effectifs        : "+nbt);
    System.out.println("Nombre d'affectations effectives : "+nba);
  }

  /* Fonction principale                                  */

  public static void main(String [] args) throws IOException {
  /* Initialisation du tableau de l'examen et de val      */
    int [] tab = { 7,8,2,3,6 };
    int val = 4;
  /* Affichage du tableau tab                             */
    System.out.println("Le tableau initial est :");
    affichageTableau(tab);
  /* Traitement                                           */
    traitement(tab,val);
  /* Affichage du resultat de l'execution de l'algorithme */
    System.out.println("Apres traitement :");
    affichageTableau(tab);
  /* Lecture au clavier de la taille du tableau           */
//    System.out.print("Taille du tableau : ");
//    int n = Integer.valueOf(flux.readLine()).intValue();
  /* Lecture au clavier de la valeur de traitement        */
//    System.out.print("Valeur            : ");
//    int v = Integer.valueOf(flux.readLine()).intValue();
  /* Creation d'un tableau de n entiers aleatoires        */
//    int [] m = creationTableauAleatoire(n);
  /* Affichage de ma matice m                             */
//    System.out.println("Le tableau initial est :");
//    affichageTableau(m);
  /* Traitement                                           */
//    traitement(m,v);
  /* Affichage du resultat de l'execution de l'algorithme */
//    System.out.println("Apres traitement :");
//    affichageTableau(m);
  }
}