using namespace std;
#include <cstdio>
#include <string>
#include <set>
#include <ctime>
#define maxn 1000001

set<int> H[1001];
int nr;
inline void insert(int v)
{
	int i, cnt;
	set<int>::iterator it;
	//for(cnt=1; cnt<=nr;cnt<<=1);
	for(i=0, cnt=(1<<10); cnt ; cnt>>=1)
		if(i+cnt<=nr)
		{
			it=H[i].end();--it;
			if(*it<=v)i+=cnt;
		}
		
	if(H[i].size()==0)
	{
		H[i].insert(v); return;
	}
	it=H[i].end();
	--it;

	if(*it<v) ++i;
	if(i>nr) ++nr;
	H[i].insert(v);
}
void afis()
{
	for(int i=0;i<=nr;++i) 
	{
		for(set<int>::iterator it=H[i].begin();it!=H[i].end();++it)printf("%d ", *it);
	//printf("\n");
	}

	printf("\n");
}

	


int main()
{
	insert(3);
	insert(9);
	insert(1);
	insert(21);
	insert(121);
	insert(83);
	insert(11);
	insert(32);
	insert(14);
	insert(2);
	insert(99);
	
	srand(time(0));
	
	double st=clock();
	for(int i=1;i<=100000;++i) insert(rand());
	//afis();	
	
	printf("%lf\n", (clock()-st)/(double)CLOCKS_PER_SEC);
	
	
	return 0;
}