#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

template <class T, class BinaryPredicate>
int LIS(T* pi, T* d, int p, BinaryPredicate comp)
{
	int ans = 1;
	d[0] = pi[0];
	for (int i = 1; i < p; i++)
	{
		if (!comp(pi[i], d[ans - 1]))
		{
			d[ans] = pi[i];
			ans++;
		}
		else
		{
			int idx = upper_bound(d, d + ans, pi[i], comp) - d;
			d[idx] = pi[i];
		}
	}
	return ans;
}

int main()
{
	int n = 0;
	while (scanf("%d", &n) == 1 && n > 0)
	{
		int* a = new int[n];
		int* d = new int[n];
		for (int i = 0; i < n; ++i)
		{
			scanf("%d", &a[i]);
		}
		// 考虑升序
		int ans1 = n - LIS(a, d, n, less<int>());
		// 考虑降序
		int ans2 = n - LIS(a, d, n, greater<int>());
		printf("%d\n", min(ans1, ans2));
		delete[] d;
		delete[] a;
	}
	return 0;
}