import java.io.*;
import java.util.*;

public class lock_pk_60 {

	void solve() throws IOException {
		int n = nextInt();
		if (n > 1000)
			throw new AssertionError();
		
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

		int[] max = new int[n + 1];
		Arrays.fill(max, Integer.MAX_VALUE);

		max[0] = 0;
		int last = 0;
		for (int i = 0; i < n; i++) {
			int l = 0;
			int r = n;
			while (l < r - 1) {
				int c = (l + r) / 2;
				if (max[c] > a[i])
					r = c;
				else
					l = c;
			}
			max[l + 1] = a[i];
			last = l + 1;

		}

		out.println(n - last);
	}

	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;

	void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			br = new BufferedReader(new FileReader(new File("lock.in")));
			out = new PrintWriter("lock.out");
			
			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		new lock_pk_60().run();
	}

	String nextToken() throws IOException {
		while ((st == null) || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}
}
