boj7570.java

package 그리디;
import java.util.*;
public class boj7076 {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int [] dp;

    static int solution(){
        n = sc.nextInt();
        dp = new int [n+1];

        for(int i=0; i < n ; i++){
            int tmp = sc.nextInt();
            dp[tmp] = dp[tmp-1] + 1;
        }
        Arrays.sort(dp);
        return n-dp[n];
    }
    public static void main(String[] args) throws Exception {
        System.out.print(solution());
    }
}