Editing a Book

给定一个 $1\sim N$ 的全排列，希望你用 Windows 中的剪切和粘贴操作，将这个排列变成 $1, 2, \dots, N$ 的形式。

这里的操作就和大家在 Windows 中使用的一样：每次可以剪切走一段连续的元素，再把它整段粘贴到剩余序列的某个位置上。

输入格式

本题有多组数据。

每组数据第一行给出数字 $N$，下面一行给出一个 $1\sim N$ 的全排列。

以一个 $0$ 来结束输入。

输出格式

针对每组数据，输出最少的操作次数。

样例输入

6
2 4 1 5 3 6
5
3 4 5 1 2
0

样例输出

2
1

样例解释

第二组数据只需一次操作：剪切 $3\ 4\ 5$，粘贴到 $2$ 的后面，即得到 $1\ 2\ 3\ 4\ 5$。

第一组数据无法通过一次操作完成，最少需要两次。

数据范围

• $N\le 9$；
• 数据组数 $\le 50$。

来源与许可

本题题面与测试数据整理自 BZOJ 1330（原题来自 UVa）。

样例 1

输入

6
2 4 1 5 3 6
5
3 4 5 1 2
0

输出

2
1