Submission #2205900

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repe(i, a, n) for(int i = a;i <= n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
#define reper(i, a, n) for(int i = a;i >= n;i--);
#define INF 999999999
using namespace std;


int n;
int c[30010];
vector<int> dp;


void makeDP(){
	dp.push_back(-INF);
	dp.push_back(c[0]);
	rep(i, 1, n){
		if(dp.back() < c[i]) dp.push_back(c[i]);
		else *upper_bound(dp.begin(), dp.end(), c[i]) = c[i];
	}
}


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

	makeDP();

	cout << n - dp.size() + 1 << endl;

	return 0;
}

Submission Info

Judge Result