LIS

O(n)

int n = sc.nextInt();

int[] dp = new int[n];
int[] array = new int[n];
int ans = 0;

for (int i = 0; i < n; i++) {
  array[i] = sc.nextInt();
}

dp[0] = 1;

for (int i = 1; i < n; i++) {
  dp[i] = 1;
  for (int j = 0; j < i; j++) {
    if (array[j] < array[i] && dp[j] + 1 > dp[i]) {
      dp[i] = dp[j] + 1;
    }
  }

}

for(int i=1;i<n;i++) {
  if (ans < dp[i]) {
    ans = dp[i];
  }
}
System.out.println(n - ans);

O(nlogn)

int n = sc.nextInt();

  int[] array = new int[n];
  ArrayList<Integer> list = new ArrayList<>();

  for (int i = 0; i < n; i++) {
    array[i] = sc.nextInt();
  }

  for (int num : array) {

    if (list.size() == 0 || list.get(list.size() - 1) < num) {
      list.add(num);
    } else {

      int i = 0;
      int j = list.size() - 1;

      while (i < j) {

        int mid = (i + j) / 2;

        if (list.get(mid) < num) {
          i = mid + 1;
        } else {
          j = mid;
        }

      }

      list.set(j, num);

    }

  }

  System.out.println(n - list.size());