stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,26)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.4807667986237323x):
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,7)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,26)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.5804518146345825x):
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,5)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,26)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.6331595572615043x):
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,4)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define mk make_pair

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  sort(p.begin(),p.end());

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,26)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8050276471620819x):
#include <bits/stdc++.h>

#define int long long

#define r(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int>P;



int h,w;

string s[600];

int dy[]={0,1,0,-1};

int dx[]={1,0,-1,0};

int sum=0;



bool ng[555][555];



void knock(int Y,int X){

  

  map<char,vector<P> >M;

  r(i,4){

    int y=Y;

    int x=X;



    while(!isalpha(s[y][x])){

      y+=dy[i];

      x+=dx[i];

      if(y<0||x<0||y>=h||x>=w)break;

    }



    if(y<0||x<0||y>=h||x>=w)continue;

    M[s[y][x]].push_back(P(y,x));

  }



  int TX=0;

  for(auto &e:M){

    if(e.second.size()!=2)continue;

    sum+=2;

    s[e.second[0].first][e.second[0].second] = '.';

    s[e.second[1].first][e.second[1].second] = '.';

    TX++;

  }



  if(!M.size())ng[Y][X]=1;



}



signed main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];



  r(tim,26)r(i,h)r(j,w)if(!isalpha(s[i][j])&&!ng[i][j]){

    knock(i,j);

  }



  cout<<sum<<endl;

}
// Slower C++ solution:
#include <cstdio>

#include <deque>

#include <iostream>

using namespace std;



int n;



signed main(void)

{

    cin >> n;

    int a;

    deque <int> b;

   for(int i=0; i<n; ++i)

    {

        cin >> a;

        int it= lower_bound(b.begin(),b.end(),a)-b.begin();

        if(!it) b.push_front(a);

        else b[it-1]=a;

    }

    cout << b.size() << "\n";

 

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.29381203137333x):
#include <cstdio>

#define N 100010

using namespace std;



int n, a, t[N];



inline void ef(int a) {

	int l = 1, r = t[0];

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (t[mid] < a)

			r = mid - 1;

		else

			l = mid + 1;

	}

	t[l] = a;

}



int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) {

		scanf("%d", &a);

		if (i == 1)

			t[++t[0]] = a;

		else if (a <= t[t[0]])

			t[++t[0]] = a;

		else

			ef(a);

	}

	printf("%d", t[0]);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,ans;

int q[N],f[N];

int dp[N],a[N];

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	memset(q,0x3f,sizeof(q));

	for(int i=1;i<=n;i++)

	{

		f[i]=upper_bound(q+1,q+n,-a[i])-q;

		q[f[i]]=-a[i];

		ans=max(ans,f[i]);

	}

	cout<<ans<<endl;

 } 

// Faster C++ solution for the same problem (measured speedup: 1.4004621756295328x):
#include<bits/stdc++.h>

using namespace std;

 

const int N = 200000 + 5;

int a[N], n;

int stk[N], top;

 

int main () {

	cin>>n;

	for (int i = 1; i <= n; ++i) {

		cin>>a[i];

	}

	stk[1] = 1;

	top = 1;

	for (int i = 2; i <= n; ++i) {

		if (a[i] <= a[stk[top]]) {

			stk[++top] = i;

		}

		else {

			int l = 1, r = top;

			while (l < r) {

				int mid = (l + r) / 2;

				if (a[stk[mid]] < a[i]) {

					r = mid;

				}

				else {

					l = mid + 1;

				}

			}

			stk[l] = i;

		}

	}

	cout<<top<<endl;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,ans;

int q[N],f[N];

int dp[N],a[N];

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	memset(q,0x3f,sizeof(q));

	for(int i=1;i<=n;i++)

	{

		f[i]=upper_bound(q+1,q+n,-a[i])-q;

		q[f[i]]=-a[i];

		ans=max(ans,f[i]);

	}

	cout<<ans<<endl;

 } 

// Faster C++ solution for the same problem (measured speedup: 1.393777248557388x):
#include <iostream>

#include <algorithm>

#include <set>

#include <map>

using namespace std;



const int N = 1e5 + 7;

map<int, int> m;



int main() {

    int n;

    cin >> n;

    int cnt = n;

    while (n--) {

        int a;

        cin >> a;

        if (m.empty()) {

            m[-a]++;

        } else {

            auto p = m.upper_bound(-a);

            if (p != m.end()) {

                m[p->first]--;

                if (m[p->first] == 0) {

                    m.erase(p->first);

                }

                cnt--;

            }

            m[-a]++;

        }

    }

    cout << cnt << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,ans;

int q[N],f[N];

int dp[N],a[N];

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	memset(q,0x3f,sizeof(q));

	for(int i=1;i<=n;i++)

	{

		f[i]=upper_bound(q+1,q+n,-a[i])-q;

		q[f[i]]=-a[i];

		ans=max(ans,f[i]);

	}

	cout<<ans<<endl;

 } 

// Faster C++ solution for the same problem (measured speedup: 1.3997304387120424x):
#include<bits/stdc++.h>

#define int long long 

using namespace std;

const int maxn=1e5+10;

vector<int>v;

int a[maxn],n,ans; 

int cnt[maxn];

set<int>s;

inline int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}

main()

{

	scanf("%lld",&n);

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),v.push_back(a[i]);

	sort(v.begin(),v.end());

	v.erase(unique(v.begin(),v.end()),v.end());

	for(int i=1;i<=n;i++)

	{

		set<int>::iterator it=s.upper_bound(-getid(a[i]));

		if(it!=s.end())

		{

			if(++cnt[getid(a[i])]==1)

			{

//				printf("!%d\n",a[i]);

				s.insert(-getid(a[i]));

			}

			if(--cnt[-*it]==0)

			{

//				printf("@%d\n",-*it);

				s.erase(it);

			}

		}

		else

		{

//				printf("#%d\n",a[i]);

			++cnt[getid(a[i])];

			s.insert(-getid(a[i]));

			ans++;

		}

	}

	printf("%lld\n",ans);

}

/*

6 

3 2 1 3 1 1

*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> llVEC;

typedef vector<P> PVEC;

typedef priority_queue<P,PVEC,greater<P> > PPQ;

typedef priority_queue<ll, llVEC, greater<ll> > llPQ;



#define rep(i,a,n) for(ll i = a;i < n;i++)

#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue;

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



template<typename T>

ll sz(vector<T> vec){ return (ll)vec.size(); }

ll sz(string s){ return (ll)s.size(); }



ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }





int main(){

    ll n;

    cin >> n;

    ll a[n] = {};

    ll memo[200000] = {};

    fill(memo,memo+200000,LINF);

    ll index = 0;



    rep(i,0,n){

        ll a;

        cin >> a;



        ll ok = index+1, ng = -1;

        while(abs(ok-ng) > 1){

            ll mid = (ok+ng)/2;

            if(memo[mid] < a) ok = mid;

            else ng = mid;

        }



        if(ok == index+1) memo[index++] = a;

        else memo[ok] = a;

    }

    

    cout << index << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.1072237420295927x):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> llVEC;

typedef vector<P> PVEC;

typedef priority_queue<P,PVEC,greater<P> > PPQ;

typedef priority_queue<ll, llVEC, greater<ll> > llPQ;



#define rep(i,a,n) for(ll i = a;i < n;i++)

#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue;

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



template<typename T>

ll sz(vector<T> vec){ return (ll)vec.size(); }

ll sz(string s){ return (ll)s.size(); }



ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }





int main(){

    ll n;

    cin >> n;

    ll a[n] = {};

    vector<ll> vec(n);

    ll memo = 0;



    rep(i,0,n){

        ll a;

        cin >> a;



        ll ok = memo, ng = -1;

        while(abs(ok-ng) > 1){

            ll mid = (ok+ng)/2;

            if(vec[mid] < a) ok = mid;

            else ng = mid;

        }



        if(ok == memo) vec[memo++] = a;

        else vec[ok] = a;

    }

    

    cout << memo << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using Pi = pair < int , int >;



template < typename T > 

struct BIT

{

	vector < T > dat;



	BIT (int n)

	{

		dat.assign(n + 1, 0);

	}

	

	void add(int k, T x)

	{

		k++;

		while ( k <= dat.size() ) {

			dat[k] += x;

			k += k & -k;

		}

	}



	T query(int k)

	{

		T sum = 0;

		k++;

		while ( k > 0 ) {

			sum += dat[k];

			k -= k & -k;

		}

		return ( sum );

	}



	int lower_bound(T x)

	{

		int l, r;

		l = -1, r = dat.size();

		while ( l + 1 < r ) {

			int m = (l + r) / 2;

			if ( query(m) >= x ) r = m;

			else l = m;

		}

		return ( r );

	}

};



int main()

{

	int N;

	int A[100005];

	Pi dat[100005];



	map < Pi , int > idx;

	cin >> N;



	for ( int i = 0; i < N; i++ ) {

		cin >> A[i];

		dat[i] = Pi(A[i], -i);

	}

	sort(dat, dat + N);

	

	for ( int i = 0; i < N; i++ ) {

		idx[dat[i]] = i;

	}

	

	BIT < int > tree(N);	

	int ans = 0;

	for ( int i = 0; i < N; i++ ) {

		int pos = idx[Pi(A[i], -i)];

		int value = tree.query(pos);

		

		if ( value == 0 ) {

			ans++;

		} else {

			tree.add(tree.lower_bound(value), -1);

		}

		tree.add(pos, 1);

	}



	cout << ans << endl;



	return ( 0 );

}


// Faster C++ solution for the same problem (measured speedup: 1.8130711704336044x):
#include <bits/stdc++.h>

using namespace std;



int main()

{

	int N;

	deque < int > d;



	cin >> N;

	for ( int i = 0; i < N; i++ ) {

		int A, p;

		cin >> A;

		p = lower_bound(begin(d), end(d), A) - begin(d);

		if ( p == 0 ) d.push_front(A);

		else d[p - 1] = A;

	}



	cout << d.size() << endl;



	return ( 0 );

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

/* typedef */

typedef long long ll;

typedef pair<int, int> pii;

/* constant */

const int INF = 1 << 30;

const ll LINF = 1LL << 50;

const int NIL = -1;

const int MAX = 100005;

const int mod = 1000000007;

const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */

int main(){

    int N;

    cin >> N;

    vector<int> A(MAX), L(MAX, -1), D;

    for (int i = 0; i < N; i++) cin >> A[i];

    L[0] = A[0];

    D.push_back(INF);

    int length = 1;

    for (int i = 1; i < N; i++) {

        if (L[length - 1] < A[i]) L[length++] = A[i];

        else {

            int ind = lower_bound(L.begin(), L.begin() + length, A[i]) - L.begin();

            int d = L[ind];

            L[ind] = A[i];

            if (d == -1) { continue; }

            auto itr = lower_bound(D.begin(), D.end(), d);

            if (itr == D.begin()) {

                D.insert(D.begin(), {d});

            }

            else *(itr - 1) = d;

        }

    }

    int ans = 1;

    if (D[0] != INF) ans += D.size() - 1;

    cout << ans << '\n';

}


// Faster C++ solution for the same problem (measured speedup: 1.8173438113944578x):
#include <bits/stdc++.h>

using namespace std;

/* typedef */

typedef long long ll;

typedef pair<int, int> pii;

/* constant */

const int INF = 1 << 30;

const ll LINF = 1LL << 50;

const int NIL = -1;

const int MAX = 10000;

const int mod = 1000000007;

const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */

int main(){

    int N;

    cin >> N;

    vector<int> a(N);

    for (int i = 0; i < N; i++) cin >> a[i];

    vector<int> L(N + 1);

    L[0] = a[N-1];

    int length = 1;

    for (int i = N-2; i >= 0; i--) {

        if (L[length - 1] <= a[i]) L[length++] = a[i];

        else {

            *upper_bound(L.begin(), L.begin() + length, a[i]) = a[i];

        }

    }

    cout << length << '\n';

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int maxn=2e5+5;

int a[maxn];

bool vis[maxn];



int main()

{

    int n;

    while(cin>>n){

        memset(vis, 0, sizeof(vis));

        multiset<int> LIS;

        for(int i=0;i<n;i++){

            cin>>a[i];

        }

        LIS.emplace(a[0]);

        for(int i=1;i<n;i++){

            if(a[i]<=*LIS.begin()){

                LIS.emplace(a[i]);

            }

            else{

                auto it = LIS.lower_bound(a[i]);

                if(it!=LIS.begin()) it--;

                LIS.erase(it);

                LIS.emplace(a[i]);

            }

        }

        cout<<LIS.size()<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.198290825964072x):
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int n;

    while(cin>>n){

        multiset<int> LIS;

        int temp;

        cin>>temp;

        LIS.insert(temp);

        for(int i=1;i<n;i++){

            cin>>temp;

            if(temp<=*LIS.begin()){

                LIS.insert(temp);

            }

            else{

                auto p = LIS.lower_bound(temp);

                if(p!=LIS.begin()) p--;

                LIS.erase(p);

                LIS.insert(temp);

            }

        }

        cout<<LIS.size()<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



const int N=100000+5;

const int inf=10000000;



int dis[N];

int f[N];

int dp[N];

int q[N];

int n;

int a[N];



int main()

{

	int i=1;

	cin>>n;

	int j;

	for(i=1;i<=n;++i)cin>>dis[i];

	for(i=0;i<N;++i)f[i]=inf; 

	i=1;

	for(j=1;j<=n;++j)

	{

		f[upper_bound(f+1,f+i+2,dis[j])-f]=dis[j];

		if(f[i+1]!=inf)i++;

	}

	int ans=0;

	reverse(dis+1,dis+1+n);

	memset(q,0x3f,sizeof(q));

	for(i=1;i<=n;++i)

	{

		dp[i]=upper_bound(q+1,q+n,dis[i])-q;

		q[dp[i]]=dis[i];

		ans=max(ans,dp[i]);

	}

	cout<<ans<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2873572882343753x):
#include<bits/stdc++.h>



using namespace std;



const int N=100000+5;

const int inf=10000000;



int dis[N];

int f[N];

int dp[N];

int q[N];

int n;

int a[N];



int main()

{

	int i=1;

	cin>>n;

	int j;

	for(i=1;i<=n;++i)cin>>dis[i];

	int ans=0;

	reverse(dis+1,dis+1+n);

	memset(q,0x3f,sizeof(q));

	for(i=1;i<=n;++i)

	{

		dp[i]=upper_bound(q+1,q+n,dis[i])-q;

		q[dp[i]]=dis[i];

		ans=max(ans,dp[i]);

	}

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



const int N=100000+5;

const int inf=10000000;



int dis[N];

int f[N];

int dp[N];

int q[N];

int n;

int a[N];



int main()

{

	int i=1;

	cin>>n;

	int j;

	for(i=1;i<=n;++i)cin>>dis[i];

	for(i=0;i<N;++i)f[i]=inf; 

	i=1;

	for(j=1;j<=n;++j)

	{

		f[upper_bound(f+1,f+i+2,dis[j])-f]=dis[j];

		if(f[i+1]!=inf)i++;

	}

	int ans=0;

	reverse(dis+1,dis+1+n);

	memset(q,0x3f,sizeof(q));

	for(i=1;i<=n;++i)

	{

		dp[i]=upper_bound(q+1,q+n,dis[i])-q;

		q[dp[i]]=dis[i];

		ans=max(ans,dp[i]);

	}

	cout<<ans<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8260699602138228x):
#include <bits/stdc++.h>

using namespace std;



const int N = 100000;

int a[N+5], dp[N+5], cnt;



int main(){

    int n; scanf("%d", &n);

    for (int i = 1; i <= n; ++i){

        scanf("%d", a+i);

    }

    reverse(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i){

        int pos = upper_bound(dp + 1, dp + cnt + 1, a[i]) - dp;

        dp[pos] = a[i]; cnt = max(cnt, pos);

    }

    printf("%d\n", cnt);

    return 0;

}