“It’s Black, It’s White, It’s Tough For You To Get By”
Michael Jackson (1958-2009)

You have a sequence of integers. You can paint each of the integers black or white, or leave it unpainted. The black integers must appear in ascending order and the white integers must appear in descending order. The ascending/descending order must be strict, that is, two integers painted with the same color cannot be equal. Paint the sequence so as to minimize the number of unpainted integers.

Input

The input contains several test cases, each one described in exactly two lines. The first line contains an integer N indicating the number of elements in the sequence (1 ≤ N ≤ 200). The second line contains N integers Xi separated by single spaces, representing the sequence to paint (1 ≤ Xi ≤ 10⁶ for 1 ≤ i ≤ N ). The last line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the minimum number of unpainted elements of the sequence, when the sequence is painted optimally following the rules described above.

Example

Input:
8
1 4 2 3 3 2 4 1
12
7 8 1 2 4 6 3 5 2 1 8 7
-1

Output:
0
2