#include <stdio.h>

int N;
int pole[100000];
int sort[100000];
int step;
int last_min, last_index;
int last_value;
int steps = 0;

int find_min(int i) {
  int j;
  int min = 100001;
  int index = 0;
  last_min = min;
  last_index = 0;
  for (j = N-1; j >= i; j--) {
    steps++;
    if (min > pole[j]) {      
      last_min = min;
      last_index = index;
      min = pole[j];
      index = j;
      if (last_value > -1 && min == last_value) break;
    }
    if (min == pole[j]) {
      if (step % 2 == 0) {
	min = pole[j];
	index = j;
      }
    }
  }
  last_value = min;
  return index;
}

void reverse(int a, int b) {
  int j, tmp;
  int x = b;

  for (j = a; j <= b; j++, x--) {
    if (x < j) break;
    tmp = pole[j];
    pole[j] = pole[x];
    pole[x] = tmp;
    }
  /*  int rev[b-a];
  int x = a;
  for (j = b-a; j >= 0; j--, a++) {
    rev[j] = pole[a];
  }  
  for (j = 0; j < b-a; j++) {
    pole[j+a] = rev[j];
    }*/
}

int main() {
  while(1) {  
    steps = 0;
    scanf("%d", &N);
    if (N == 0) break;
    int i;
    for (i = 0; i < N; i++) {
      scanf("%d", &pole[i]);
      sort[i] = pole[i];
    }
    step = 0;
    last_value = -1;
    for (i = 0; i < N; i++) {
      step++;
      int idx = find_min(i);

      /*      int y;
      for (y = 0; y < N; y++) {
	printf("%d ", pole[y]);
      }    
      putchar('\n');
      */
      reverse(i, idx);      
      printf("%d(%d) ", idx+1, last_index+1);
      /*      printf("%d ", idx+1);*/
    }   
    printf(" | %d", steps);
    putchar('\n');
  }

  return 0;
}