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

public class lock_vd {
	int[] fenv = new int[1000005];

	int get(int x) {
		int res = 0;
		while (x > 0) {
			res = Math.max(res, fenv[x]);
			x = x & (x - 1);
		}
		return res;
	}

	void update(int pos, int val) {
		while (pos <= 100000) {
			fenv[pos] = Math.max(fenv[pos], val);
			pos = 2 * pos - (pos & (pos - 1));
		}
	}

	public void solve() throws IOException {
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		int[] res = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = 1 + get(a[i]);
			update(a[i], res[i]);
		}
		out.println(n - res[n - 1]);

	}

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

	FastScanner in;
	PrintWriter out;

	void run() {
		Locale.setDefault(Locale.US);
		try {
			in = new FastScanner("lock".toLowerCase() + ".in");
			out = new PrintWriter("lock".toLowerCase() + ".out");
			solve();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}

	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer str;

		public FastScanner(String file) throws FileNotFoundException {
			if (file == null) {
				br = new BufferedReader(new InputStreamReader(System.in));
			} else {
				br = new BufferedReader(new FileReader(file));
			}
		}

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

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

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

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

	}
}
