1 #include <cstdio> 2 #include <cstring> 3  4 const int maxn = 9; 5  6 int n, a[maxn]; 7  8 bool is_sorted() { 9     for (int i = 0; i < n - 1; i++)10         if (a[i] >= a[i + 1]) return false;11     return true;12 }13 14 int h() {15     int cnt = 0;16     for (int i = 0; i < n - 1; i++)17         if (a[i] + 1 != a[i + 1]) cnt++;18     if (a[n - 1] != n) cnt++;19     return cnt;20 }21 22 bool dfs(int d, int maxd) {23     if (d * 3 + h() > maxd * 3) return false;24     if (is_sorted()) return true;25     int b[maxn], olda[maxn];26     memcpy(olda, a, sizeof(a));27     for (int i = 0; i < n; i++)28         for (int j = i; j < n; j++) {29             int cnt = 0;30             for (int k = 0; k < n; k++)31                 if (k < i || k > j) b[cnt++] = olda[k];32             for (int k = 0; k <= cnt; k++) {33                 int cnt2 = 0;34                 for (int p = 0; p < k; p++) a[cnt2++] = b[p];35                 for (int p = i; p <= j; p++) a[cnt2++] = olda[p];36                 for (int p = k; p < cnt; p++) a[cnt2++] = b[p];37                 if (dfs(d + 1, maxd)) return true;38             }39         }40     return false;41 }42 43 int solve() {44     for (int maxd = 0; ; maxd++)45         if (dfs(0, maxd)) return maxd;46 }47 48 int main() {49     int kase = 0;50     while (scanf("%d", &n) == 1 && n) {51         for (int i = 0; i < n; i++) scanf("%d", &a[i]);52         printf("Case %d: %d\n", ++kase, solve());53     }54     return 0;55 }