#include<iostream>

using namespace std;


#define MAX	10000

//入力配列
int h_input[MAX] = {0};


//k * (k + 1) / 2で表される数かどうか
bool f_check(int);

//答え出力変数
int ans = 0;



//ループで答えを求める関数
void f_ans(int);


//合否判定関数
bool f_ok(int);



//配列をずらす関数
int f_zurasu(int);




int main(void)
{
	//入力変数
	int n = 0;

	while (cin >> n && n != 0)
	{
		//答え変数初期化
		ans = 0;

		//値を入力
		for (int i = 0; i < n; i++)
		{
			cin >> h_input[i];
		}

		//まず作れるかどうか
		if (f_check(n) == false)
		{
			cout << "-1" << endl;
			continue;
		}

		//関数で求める
		f_ans(n);

		//関数で成功かどうか判断する
		cout << ans << endl;
	}

	return 0;
}




bool f_check(int n)
{
	//合計値を計算
	int sum = 0;
	//ｋを算出する変数
	int count = 2;

	for (int i = 0; i < n; i++)
	{
		sum += h_input[i];
	}

	//k * (k + 1)を計算
	int k = 1;

	//割り切れるか、値が大きくなるまで
	while (1)
	{
		//割り切れる
		if (k == sum)
		{
			return true;
		}
		//値を超えた
		if (k > sum)
		{
			return false;
		}

		k = (count * (count + 1)) / 2;

		count++;
	}
}



//ループで答えを求める関数
void f_ans(int n)
{

	//回数カウント変数
	int count = 0;

	//いくつのブロックを動かしたかを記憶する
	int move = 0;

	//成功flag
	bool flag_ok = false;

	//配列の末尾を表す
	int end = n;

	//最高回数
	while (count < 10000)
	{
		move = 0;

		//できているかのチェック
		if (f_ok(n) == true)
		{
			//flagをtrueにして抜ける
			flag_ok = true;
			break;
		}

		//番兵まで回す
		for (int i = 0; i < end; i++)
		{
			//0でないならデクリメントをして、動かしたブロックの個数を記憶する変数をインクリメント
			if (h_input[i] != 0)
			{
				h_input[i]--;
				move++;
			}
		}

		//関数でずらして戻り値を利用する
		end = f_zurasu(end);
		h_input[end] = move;
		end++;

		//1回動かした
		count++;
	}

	ans = -1;
	//okならば上書き
	if (flag_ok == true)
	{
		ans = count;
	}
}



//合否判定関数
bool f_ok(int n)
{
	//最初は1段
	int dan = 1;

	for (int i = 0; h_input[i] != 0; i++)
	{
		if (h_input[i] != dan)
		{
			return false;
		}
		dan++;
	}

	return true;
}



//配列をずらす関数
int f_zurasu(int n)
{
	//別な配列を使ったほうが楽
	int h_copy[MAX] = {0};

	//カウント変数
	int count = 0;

	for (int i = 0; i < n; i++)
	{
		if (h_input[i] != 0)
		{
			h_copy[count++] = h_input[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		h_input[i] = h_copy[i];
	}

	//配列の最後尾を表す
	return count;
}
### Prompt

In CPP, your task is to solve 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<iostream>

using namespace std;


#define MAX	10000

//入力配列
int h_input[MAX] = {0};


//k * (k + 1) / 2で表される数かどうか
bool f_check(int);

//答え出力変数
int ans = 0;



//ループで答えを求める関数
void f_ans(int);


//合否判定関数
bool f_ok(int);



//配列をずらす関数
int f_zurasu(int);




int main(void)
{
	//入力変数
	int n = 0;

	while (cin >> n && n != 0)
	{
		//答え変数初期化
		ans = 0;

		//値を入力
		for (int i = 0; i < n; i++)
		{
			cin >> h_input[i];
		}

		//まず作れるかどうか
		if (f_check(n) == false)
		{
			cout << "-1" << endl;
			continue;
		}

		//関数で求める
		f_ans(n);

		//関数で成功かどうか判断する
		cout << ans << endl;
	}

	return 0;
}




bool f_check(int n)
{
	//合計値を計算
	int sum = 0;
	//ｋを算出する変数
	int count = 2;

	for (int i = 0; i < n; i++)
	{
		sum += h_input[i];
	}

	//k * (k + 1)を計算
	int k = 1;

	//割り切れるか、値が大きくなるまで
	while (1)
	{
		//割り切れる
		if (k == sum)
		{
			return true;
		}
		//値を超えた
		if (k > sum)
		{
			return false;
		}

		k = (count * (count + 1)) / 2;

		count++;
	}
}



//ループで答えを求める関数
void f_ans(int n)
{

	//回数カウント変数
	int count = 0;

	//いくつのブロックを動かしたかを記憶する
	int move = 0;

	//成功flag
	bool flag_ok = false;

	//配列の末尾を表す
	int end = n;

	//最高回数
	while (count < 10000)
	{
		move = 0;

		//できているかのチェック
		if (f_ok(n) == true)
		{
			//flagをtrueにして抜ける
			flag_ok = true;
			break;
		}

		//番兵まで回す
		for (int i = 0; i < end; i++)
		{
			//0でないならデクリメントをして、動かしたブロックの個数を記憶する変数をインクリメント
			if (h_input[i] != 0)
			{
				h_input[i]--;
				move++;
			}
		}

		//関数でずらして戻り値を利用する
		end = f_zurasu(end);
		h_input[end] = move;
		end++;

		//1回動かした
		count++;
	}

	ans = -1;
	//okならば上書き
	if (flag_ok == true)
	{
		ans = count;
	}
}



//合否判定関数
bool f_ok(int n)
{
	//最初は1段
	int dan = 1;

	for (int i = 0; h_input[i] != 0; i++)
	{
		if (h_input[i] != dan)
		{
			return false;
		}
		dan++;
	}

	return true;
}



//配列をずらす関数
int f_zurasu(int n)
{
	//別な配列を使ったほうが楽
	int h_copy[MAX] = {0};

	//カウント変数
	int count = 0;

	for (int i = 0; i < n; i++)
	{
		if (h_input[i] != 0)
		{
			h_copy[count++] = h_input[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		h_input[i] = h_copy[i];
	}

	//配列の最後尾を表す
	return count;
}
```