Submission #4019283

---

Source Code Expand

#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define LOG(...) fprintf(stderr, __VA_ARGS__)
#define INF 30001
using namespace std;

/*
n
c1
...
cn

n 3*10^4
ci n
 */
int n;
int c[30000];

int main(){
  cin >> n;
  REP(i,n)
    cin >> c[i];

  vector<int> dp(n, INF);
  REP(j,n){
    auto itr = upper_bound(dp.begin(), dp.end(), c[j]);
    if(c[j] > *(itr-1))
      *itr = c[j];
  }

  int l = 0;
  REP(i,n){
    if(dp[i] < INF)
      l = i + 1;
  }

  cout << n - l << endl;

  return 0;
}

Submission Info

Judge Result