http://59.23.113.171/pool/koi_align/koi_align.php?pname=koi_align

Koi_Align.java

import java.util.Scanner;

public class Koi_Align {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = in.nextInt();
		}
		in.close();
		
		// 테스트용 데이
//		 int[] array = { 5, 2, 4, 1, 3 };
//		 int[] array = { 5, 2, 3, 4, 7, 1, 6 };

		int maxSequence = 0;

		int[] sequence = new int[array.length + 1];
		sequence[array[0]] = 1;
		
		for (int i = 1; i < array.length; i++) {

			int pivot = array[i];
			sequence[pivot] = sequence[pivot - 1] + 1;
			maxSequence = Math.max(maxSequence, sequence[pivot - 1] + 1);
		}

		System.out.println(array.length - maxSequence);
	}
}