Description

给出一个数列(可以有重复数)，可以对数列进行一种操作，就是从数列中取出若干数，按顺序放到左边，把剩下的数按顺序放到右边。

比如数列 1 3 2 4，可以取出数1 2放至左边，剩下3 4放至右边，形成新数列 1 2 3 4 问最少需要几次操作，可以使数列单调非降。

Inputs: 输入包含多组测试数据。

每组数据第一行为一个正整数n(n<=100000)，表示数列长度，接下来有n行，每行一个整数Ai，代表数列的第i项。

Output

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

Sample

Input

4
1
3
2
4

Output

1

Source: DK