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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <cstdio>

#define ll long long

ll nt[45][45];

int main(int argc, char** argv) {
  int n;
  int a[42];
  ll res[42][2];
  int d[42];

  for(int i=0;i<45;i++) {
    nt[i][1] = 1;
    nt[1][i] = 1;
  }
  for(int i=2;i<45;i++) {
    for(int j=2;j<45;j++) {
      nt[i][j] = nt[i][j-1] + nt[i-1][j];
    }
  }
  scanf("%d", &n);
  for(int i=0;i<n;i++) {
    scanf("%d", &(a[i]));
    a[i]--;
  }
  res[0][1] = n;

  if(n <= 25) {
    for(int i=1;i<n;i++) {
      int mi = 123456;
      ll cnt = 0;
      for(int j=0;j<=i;j++) {
        d[j] = j;
      }
      for(;;) {
        int err = 0;
        for(int k=0;k<=i;k++) {
          for(int m=k+1;m<=i;m++) {
            if(a[d[k]] > a[d[m]]) {
              err++;
            }
          }
        }
        if(err < mi) {
          mi = err;
          cnt = 1;
        } else if(err == mi) {
          cnt++;
        }

        int j = i;
        if(d[j] < n-1) {
          d[j]++;
        } else {
          while (j > 0 && d[j - 1] + 1 == d[j]) {
            j--;
          }
          if (j == 0) {
            break;
          } else {
            d[j - 1]++;
            while (j <= i) {
              d[j] = d[j - 1] + 1;
              j++;
            }
          }
        }
      }
      res[i][0] = mi;
      res[i][1] = cnt;
    }
  } else {
    bool incr = true;
    for(int i=1;i<n;i++) {
      if(a[i-1] > a[i]) {
        incr = false;
        break;
      }
    }
    if(incr) {
      for(int i=0;i<n;i++) {
        res[i][0] = 0;
        res[i][1] = nt[n-i][i+2];
      }
    } else {
      bool incr = true;
      for(int i=1;i<n;i++) {
        if(a[i-1] < a[i]) {
          incr = false;
          break;
        }
      }
      if(incr) {
        for(int i=0;i<n;i++) {
          res[i][0] = nt[i][3];
          res[i][1] = nt[n-i][i+2];
        }
      }
    }
  }
  for(int i=0;i<n;i++) {
    printf("%lld %lld\n", res[i][0], res[i][1]);
  }
  return 0;
}