Submission #2202545

---

Source Code Expand

#include <iostream>
#include <vector>
#define INF 1000000

using namespace std;

int main(void){
	int n;

	cin >> n;

	vector<int> c(n+1, 0);

	for (int i = 1; i < n+1; i++){
		cin >> c[i];
	}


	vector<int> dp(n + 2);

	for (int i = 0; i < n + 2; i++){
		dp[i] = INF;
	}


	int m = 0;
	for (int i = 1; i < n + 1; i++){
		int left = 1, right = n;

		int mid = (left + right)/2;


		while (left <= right){
			mid = (left + right)/2;

			if (dp[mid] > c[i]){
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}

		dp[left] = c[i];

		m = max(m, left);
	}



	cout << n - m << endl;
}

Submission Info

Judge Result