2257.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2257 on 2006-05-29 at 10:25:23 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 102400;

int s[PN];

int main()
{
	int t, T, i;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n, len = 0; scanf("%d", &n);
		for(i = 0; i < n; i++) {
			int k; scanf("%d", &k);
			int id = upper_bound(s, s+len, k) - s;
			s[id] = k;
			if(id == len) len++;
		}
		printf("%d\n", n-len);
	}
	
	return 0;
}