Järjestys

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define N (1<<17)
#define M 1000000007

using namespace std;

int v[2*N];

void ch (int n, int k) {
  k += N;
  v[k] = n;
  for (k /= 2; k >= 1; k /= 2) v[k] = max(v[2 * k], v[2 * k + 1]);
}

int sum (int n, int k) {
  k += N;
  n += N;
  int s = 0;
  while (n <= k) {
    if (n % 2 == 1) s = max(v[n++], s);
    if (k % 2 == 0) s = max(v[k--], s);
    n /= 2;
    k /= 2;
  }
  return s;
}

int main () {
  int n;
  cin>>n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    cin>>x;
    int q = sum(1, x - 1) + 1;
    ans = max(ans, q);
    ch(q, x);
  }
  cout<<n - ans<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED