#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < n; i++)
const int inf9 = 1e9; const lint inf18 = 1e18;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ double y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); } double euclidean(double first, double second){ return sqrt(first * first + second * second); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + ","; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
inline int at(lint i, int j){ return (i >> j) & 1; }

void testcase(){
    int N;
    cin >> N;
    if(N == 0){
        exit(0);
    }
    vector<int> block(N);
    cins(all(block));
    int sum = accumulate(all(block), 0);
    int height = -1;
    for(int i = 0; i < 10000; i++){
        if(i * (i + 1) / 2 == sum){
            height = i;
            break;
        }
    }
    if(height == -1){
        cout << -1 << endl;
        return;
    }
    for(int i = 0; i <= 10000; i++){
        if(height != block.size()){
            goto pass;
        }
        for(int j = 0; j < height; j++){
            if(block[j] != j + 1){
                goto pass;
            }
        }
        cout << i << endl;
        return;
    pass:
        int right = int(block.size());
        vector<int> new_block;
        for(int j: block){
            if(j >= 2){
                new_block.push_back(j - 1);
            }
        }
        new_block.push_back(right);
        block = new_block;
    }
    cout << -1 << endl;
}

int main(){
    while(true) testcase();
}





### Prompt

Your task is to create a Cpp solution to the following problem:

The following sorting operation is repeated for the stacked blocks as shown in Fig. A.

1. Stack all the bottom blocks (white blocks in Figure a) on the right edge (the remaining blocks will automatically drop one step down, as shown in Figure b).
2. If there is a gap between the blocks, pack it to the left to eliminate the gap (from Fig. B to Fig. C).



For an integer k greater than or equal to 1, a number represented by k × (k + 1) / 2 (example: 1, 3, 6, 10, ...) is called a triangular number. If the total number of blocks is a triangular number, it is expected that if the above sorting is repeated, the height of the left end will be 1 and the total number will increase by 1 toward the right (Fig. D shows the total number). For 15).

<image>


When the first sequence of blocks is given, when the triangle of the block as explained above is created by the operation less than the predetermined number of times, create a program that outputs the minimum number of operations until the triangle is obtained. please.



input

The input consists of multiple datasets. The end of the input is indicated by a single zero line. Each dataset is given in the following format.


N
b1 b2 ... bN


Each dataset has two rows and represents the first sequence of blocks. N (1 ≤ N ≤ 100) indicates the number of blocks in the bottom row. bi (1 ≤ bi ≤ 10000) indicates the number of blocks stacked in the i-th position from the left. bi and bi + 1 are separated by a single space. The total number of blocks is 3 or more.

The number of datasets does not exceed 20.

output

For each data set, the number of sorting operations performed until the triangle is formed is output on one line. However, if a triangle cannot be created or the number of operations exceeds 10000, -1 is output.

Example

Input

6
1 4 1 3 2 4
5
1 2 3 4 5
10
1 1 1 1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 1 1
12
1 4 1 3 2 4 3 3 2 1 2 2
1
5050
3
10000 10000 100
0


Output

24
0
10
-1
48
5049
-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < n; i++)
const int inf9 = 1e9; const lint inf18 = 1e18;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ double y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); } double euclidean(double first, double second){ return sqrt(first * first + second * second); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + ","; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
inline int at(lint i, int j){ return (i >> j) & 1; }

void testcase(){
    int N;
    cin >> N;
    if(N == 0){
        exit(0);
    }
    vector<int> block(N);
    cins(all(block));
    int sum = accumulate(all(block), 0);
    int height = -1;
    for(int i = 0; i < 10000; i++){
        if(i * (i + 1) / 2 == sum){
            height = i;
            break;
        }
    }
    if(height == -1){
        cout << -1 << endl;
        return;
    }
    for(int i = 0; i <= 10000; i++){
        if(height != block.size()){
            goto pass;
        }
        for(int j = 0; j < height; j++){
            if(block[j] != j + 1){
                goto pass;
            }
        }
        cout << i << endl;
        return;
    pass:
        int right = int(block.size());
        vector<int> new_block;
        for(int j: block){
            if(j >= 2){
                new_block.push_back(j - 1);
            }
        }
        new_block.push_back(right);
        block = new_block;
    }
    cout << -1 << endl;
}

int main(){
    while(true) testcase();
}





```