记录编号	253531	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 167] 免费午餐	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2016-04-22 12:26:13	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e5+10;
const int inf = 1e9;

int c[maxn];
int n;

template <class T> class stack {
private:
	T a[maxn];
	int top_;
public:
	inline T top() { return a[top_]; }
	inline void push(T tar) { a[++top_] = tar; }
	inline void pop() { top_--; }
	inline int size() { return top_; }
	inline void change(T tar) {
		int l = 1, r = top_;
		int mid;
		while(l < r) {
			mid = (l + r) >> 1;
			if(a[mid] <= tar) r = mid;
			else l = mid+1;
		} 
	 	a[l] = tar;
	}
	void out() {
		for(int i = 1; i <= top_; i++) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
};

stack<int> s;

void read() {
	scanf("%d", &n);
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	for(int i = 1; i <= n ;i++) {
		if(c[i]) c[++cnt] = c[i];
	}
	n = cnt;
}

void solve() {
	s.push(inf);
	for(int i = 1; i <= n; i++) {
		if(c[i] < s.top()) s.push(c[i]);
		else s.change(c[i]);
//		s.out();
	}
	printf("%d\n", s.size()-1);
}

int main() {
	freopen("lunch.in", "r", stdin);
	freopen("lunch.out", "w", stdout);
	read();
	solve();
	return 0;
}