stablegradients/pie-gem5-pairs huggingface dataset:
// 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];

	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.4184639935649084x):
#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;

}
// 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.7823896771050602x):
#include<bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

using namespace std;

const int mod=1e9+7;

int m,n,yy[100005],sy[100005],cnt,ans;

unordered_map<int,int> mp;

int main()

{

    std::ios::sync_with_stdio(0); std::cin.tie(0);

	cin>>m;

	for(int i=1;i<=m;++i) cin>>yy[i];

	sy[0]=2e9;

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

	{

		if(yy[i]<=sy[cnt]) sy[++cnt]=yy[i];

		else

		{

			int l=0,r=cnt,mid,e;

			while(l<=r)

			{

				mid=(l+r)>>1;

				if(sy[mid]<yy[i]) r=mid-1;

				else { l=mid+1; e=mid; } 

			}

			sy[e+1]=yy[i];

		}

	}

	//for(int i=1;i<=cnt;++i) ans+=mp[sy[i]];

	cout<<cnt;

	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];

	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.3845337991208542x):
#include<bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

using namespace std;

const int mod=1e9+7;

int m,n,yy[100005],sy[100005],cnt,ans;

unordered_map<int,int> mp;

int main()

{

    std::ios::sync_with_stdio(0); std::cin.tie(0);

	cin>>m;

	for(int i=1;i<=m;++i) cin>>yy[i];

	sy[0]=2e9;

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

	{

		if(yy[i]<=sy[cnt]) sy[++cnt]=yy[i];

		else

		{

			int l=0,r=cnt,mid,e;

			while(l<=r)

			{

				mid=(l+r)>>1;

				if(sy[mid]<yy[i]) r=mid-1;

				else { l=mid+1; e=mid; } 

			}

			sy[e+1]=yy[i];

		}

	}

	//for(int i=1;i<=cnt;++i) ans+=mp[sy[i]];

	cout<<cnt;

	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.765246164898254x):
#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define sigma_size 30

#define max_size (int)(1e5+10)

#define MAX (int)(1e5+7)



int N;

int a[max_size];

const int INF = 1e9+7;

int main ()

{

	ios::sync_with_stdio(0);

	cin >> N ;

	vector <int> v;

	v.push_back(0);

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

		cin >> a[i];

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

	{

		if ( v.size() == 1 )

		{

			v.push_back(a[i]);

			continue;

		}

		int left = 1 , right = (int)v.size();

		while ( left < right )

		{

			int mid = left + right >> 1;

			if ( v[mid] < a[i] )

				right = mid;

			else left = mid+1;

		}

		if ( left == (int)v.size() )

			v.push_back(a[i]);

		else v[left] = a[i];

	}

	cout << v.size()-1 << endl;

}
// 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];

	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.371216973742626x):
#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define sigma_size 30

#define max_size (int)(1e5+10)

#define MAX (int)(1e5+7)



int N;

int a[max_size];

const int INF = 1e9+7;

int main ()

{

	ios::sync_with_stdio(0);

	cin >> N ;

	vector <int> v;

	v.push_back(0);

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

		cin >> a[i];

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

	{

		if ( v.size() == 1 )

		{

			v.push_back(a[i]);

			continue;

		}

		int left = 1 , right = (int)v.size();

		while ( left < right )

		{

			int mid = left + right >> 1;

			if ( v[mid] < a[i] )

				right = mid;

			else left = mid+1;

		}

		if ( left == (int)v.size() )

			v.push_back(a[i]);

		else v[left] = a[i];

	}

	cout << v.size()-1 << endl;

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

using namespace std;



#define ll long long

#define ull unsigned long long

#define vii vector<int>

#define pii pair<int,int>

#define pll pair<long long,long long>

#define pdd pair<double,double>

#define pldld pair<long long double, long long double>

#define ff first

#define ss second

#define pb push_back

#define read freopen("alu.txt","r",stdin);

#define write freopen("vorta.txt","w",stdout);

#define fastio ios::sync_with_stdio(false); cin.tie(NULL);

#define PI 2*acos(0.0)

#define DEBUG(x) cerr << #x << " = " << x << endl



const int MAX = 3e5 + 5, MOD = 1e9 + 7, MAXLG = log2(MAX)+1;

const ll inf = 1e18 + 5;



int arr[MAX];

int mx = 0;

void compress(int n){

    vii v;

    for(int i=0;i<n;i++) v.pb(arr[i]);

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

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

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

        int zipped=lower_bound(v.begin(),v.end(),arr[i])-v.begin()+1;

        arr[i]=zipped;

        mx=max(mx,zipped);

    }

}



int bit[MAX];

void update(int pos, int val){

    while(pos <= mx){

        bit[pos] = max(bit[pos], val);

        pos += (pos & (-pos));

    }

}



int get(int pos){

    int ret = 0;

    while(pos > 0){

        ret = max(ret, bit[pos]);

        pos -= (pos & (-pos));

    }

    return ret;

}



int col[MAX];

int main(){



    fastio;

    int n;

    cin>>n;

    for(int i=0; i<n; i++) cin>>arr[i];

    compress(n);



    for(int i=n-1; i>=0; i--){

        int g = get(arr[i]);

        col[i] = g + 1;

        update(arr[i], g + 1);

//        cout<<g<<" "<<col[i]<<" "<<get(arr[i])<<"\n";

    }



    int ans = 0;

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

//        cout<<col[i]<<" ";

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

    }

//    cout<<"\n";

    cout<<ans<<"\n";



}


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

#include<set>

using namespace std;

const int MAXN=100005;

int n,a[MAXN],ans;

multiset<int>low;

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

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

    {

        set<int>::iterator sec=low.upper_bound(-a[i]);

        if(sec!=low.end())

        {

            low.erase(sec);

            low.insert(-a[i]);

        } else {

            low.insert(-a[i]);

            ++ans;

        }

    }

    printf("%d",ans);

    return 0;

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

using namespace std;

typedef long long ll;

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    multiset<int> ms;

    int n;

    cin >> n;

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

        int x;

        cin >> x;

        ms.insert(-x);

        int tmp = x - 1;

        auto it = ms.find(-tmp);

        if (it != ms.end()) {

            ms.erase(it);

            continue;

        }

        it = ms.upper_bound(-tmp);

        if (it != ms.end()) ms.erase(it);

    }

    cout << ms.size();

    return 0;

}

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

#include<set>

using namespace std;

const int MAXN=100005;

int n,a[MAXN],ans;

multiset<int>low;

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

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

    {

        set<int>::iterator sec=low.upper_bound(-a[i]);

        if(sec!=low.end())

        {

            low.erase(sec);

            low.insert(-a[i]);

        } else {

            low.insert(-a[i]);

            ++ans;

        }

    }

    printf("%d",ans);

    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.9440057099729517x):
#include<cstdio>

#include<set>

using namespace std;

const int MAXN=100005;

int n,a[MAXN],ans;

multiset<int>low;

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

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

    {

        set<int>::iterator sec=low.upper_bound(-a[i]);

        if(sec!=low.end())

        {

            low.erase(sec);

            low.insert(-a[i]);

        } else {

            low.insert(-a[i]);

            ++ans;

        }

    }

    printf("%d",ans);

    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];

	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.510074730410838x):
#include<cstdio>

#include<set>

using namespace std;

const int MAXN=100005;

int n,a[MAXN],ans;

multiset<int>low;

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

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

    {

        set<int>::iterator sec=low.upper_bound(-a[i]);

        if(sec!=low.end())

        {

            low.erase(sec);

            low.insert(-a[i]);

        } else {

            low.insert(-a[i]);

            ++ans;

        }

    }

    printf("%d",ans);

    return 0;

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

using namespace std;

#define LL long long

#define sigma_size 30

#define max_size (int)(1e5+10)

#define MAX (int)(1e5+7)



int N;

int a[max_size];

const int INF = 1e9+7;

int main ()

{

	ios::sync_with_stdio(0);

	cin >> N ;

	vector <int> v;

	v.push_back(0);

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

		cin >> a[i];

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

	{

		if ( v.size() == 1 )

		{

			v.push_back(a[i]);

			continue;

		}

		int left = 1 , right = (int)v.size();

		while ( left < right )

		{

			int mid = left + right >> 1;

			if ( v[mid] < a[i] )

				right = mid;

			else left = mid+1;

		}

		if ( left == (int)v.size() )

			v.push_back(a[i]);

		else v[left] = a[i];

	}

	cout << v.size()-1 << endl;

}

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

#include<set>

using namespace std;

const int MAXN=100005;

int n,a[MAXN],ans;

multiset<int>low;

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;++i) scanf("%d",&a[i]);

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

    {

        set<int>::iterator sec=low.upper_bound(-a[i]);

        if(sec!=low.end())

        {

            low.erase(sec);

            low.insert(-a[i]);

        } else {

            low.insert(-a[i]);

            ++ans;

        }

    }

    printf("%d",ans);

    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.7797388671509193x):
#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(0)

#define ll long long

#define pr pair<int,int>

#define N 100005

#define mod 1000000007

#define INF 2147483647

using namespace std;

int a[N];

bool vis[N];

vector<int>v;

int main() {

	IOS;

    int m,n,cnt=1;

    cin>>n;

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

        cin>>a[i];

    }

    v.push_back(a[1]);

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

        if(v.back()>=a[i])v.push_back(a[i]);

        else{

            int l=-1,r=v.size();

            while(l+1<r){

                int mid=l+r>>1;

                if(v[mid]<a[i])r=mid;

                else l=mid;

            }

            v[l+1]=a[i];

        }

        //for(auto i:v)cout<<i<<' ';

        //cout<<'\n';

    }

    cout<<v.size();

	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];

	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.382474689362928x):
#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(0)

#define ll long long

#define pr pair<int,int>

#define N 100005

#define mod 1000000007

#define INF 2147483647

using namespace std;

int a[N];

bool vis[N];

vector<int>v;

int main() {

	IOS;

    int m,n,cnt=1;

    cin>>n;

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

        cin>>a[i];

    }

    v.push_back(a[1]);

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

        if(v.back()>=a[i])v.push_back(a[i]);

        else{

            int l=-1,r=v.size();

            while(l+1<r){

                int mid=l+r>>1;

                if(v[mid]<a[i])r=mid;

                else l=mid;

            }

            v[l+1]=a[i];

        }

        //for(auto i:v)cout<<i<<' ';

        //cout<<'\n';

    }

    cout<<v.size();

	return 0;

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

using namespace std;

const int maxn = 100000 + 10;

const int INF = 0x3f3f3f3f;



int n,a[maxn],q[maxn],f[maxn],res;

int main() {

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

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

	q[0] = -INF;

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

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

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

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

	}

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

	return 0;

}

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

using namespace std;

typedef long long ll; typedef double db;

typedef pair<int, int> pii; typedef pair<ll, ll> pll;

typedef vector<int> vi; typedef vector<ll> vl;

typedef vector<pii> vpii; typedef vector<pll> vpll;

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

const ll mod = 1e9 + 7; const ll inf = 0x3f3f3f3f;

ll qpow(ll a, ll b) { ll t = 1; while (b != 0) { if (b & 1)t = (t * a) % mod; a = (a * a) % mod; b >>= 1; }return t; }

ll sr[112345];

vl a;

int find(int x, int y, int val) {

	if (x == y)return x;

	int mid = x + y >> 1, temp;

	if (a[mid] >= val)temp = find(mid + 1, y, val);

	else temp = find(x, mid, val);

	return temp;

}

signed main() {

	int n;

	cin >> n;

	FOR(n)cin >> sr[i];

	a.push_back(sr[0]);

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

		if (sr[i] <= a[a.size() - 1]) {

			a.push_back(sr[i]);

		}

		else {

			int pos = find(0, a.size() - 1, sr[i]);

			a[pos] = sr[i];

		}

	}

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

	return 0;

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

using namespace std;

const int maxn = 100000 + 10;

const int INF = 0x3f3f3f3f;



int n,a[maxn],q[maxn],f[maxn],res;

int main() {

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

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

	q[0] = -INF;

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

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

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

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

	}

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

	return 0;

}

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

#include<bits/stdc++.h>

using namespace std;

int num[100009]={0},a[100009]={0},f=0;

int main()

{

    int n,i,mi;

    scanf("%d",&n);

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

        int n1;

        scanf("%d",&n1);

        num[i]=n1;

    }

    a[1]=num[1];

    f++;

    mi=a[1];

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

        if(num[i]<=mi){

            mi=num[i];

            a[++f]=num[i];

        }

        else{

                for(int j=1;j<=f;j++){

                    if(a[j]<num[i]){

                        a[j]=num[i];

                        if(j==f)

                            mi=num[i];

                            break;

                    }

                }

        }

        //printf("%d  %d\n",mi,f);



    }

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



    return 0;

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

using namespace std;

const int maxn = 100000 + 10;

const int INF = 0x3f3f3f3f;



int n,a[maxn],q[maxn],f[maxn],res;

int main() {

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

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

	q[0] = -INF;

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

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

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

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

	}

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

	return 0;

}

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

#define N 100009

#define INF 0x3f3f3f3f

#define LLINF 0x3f3f3f3f3f3f3f3f

#define LL long long

// ios::sync_with_stdio(false);

using namespace std;

int n, cnt;

int a[N], b[N], len[N];

int main()

{

    cin >> n;

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

        scanf("%d", &a[i]);

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

        b[i] = a[n - i + 1];

    len[++cnt] = b[1];

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

    {

        int p = upper_bound(len + 1, len + 1 + cnt, b[i]) - len;

        if (p > cnt)

            cnt++;

        len[p] = b[i];

    }

    cout << cnt << endl;

    return 0;

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

using namespace std;

const int maxn = 100000 + 10;

const int INF = 0x3f3f3f3f;



int n,a[maxn],q[maxn],f[maxn],res;

int main() {

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

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

	q[0] = -INF;

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

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

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

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

	}

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

	return 0;

}

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

using namespace std;

const int maxn=1e5+5;

typedef long long ll;

const int inf =2e9;

int N,top=0;

int st[maxn];

int main(){

    cin>>N;

    st[top]=-inf;

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

        int x;

        cin>>x;

        x=-x;

        if(x>=st[top])st[++top]=x;

        else{

            int l=1,r=top;

            while(l<=r){

                int mid=(l+r)/2;

                if(x>=st[mid])l=mid+1;

                else r=mid-1;

            }

            st[l]=x;

        }

    }

    cout<<top<<endl;

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

#include <bitset>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <ctime>

#include <deque>

#include <fstream>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <random>

#include <set>

#include <stack>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

#define ll long long

#define ull unsigned long long

using namespace std;

void io() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

}



const int MAXN = 1e5 + 5;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MOD = 1e9 + 7;



int n;

int a[MAXN];

int t[MAXN];

int len;



int main() {

    io();

    memset(t, -1, sizeof(t));

    cin >> n;

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

        cin >> a[i];

    }

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

        int p = upper_bound(t, t + len, a[i], greater<int>()) - t;

        t[p] = a[i];

        if (p == len) {

            len++;

        }

    }

    cout << len;

}


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

using namespace std;

const int maxn=1e5+5;

typedef long long ll;

const int inf =2e9;

int N,top=0;

int st[maxn];

int main(){

    cin>>N;

    st[top]=-inf;

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

        int x;

        cin>>x;

        x=-x;

        if(x>=st[top])st[++top]=x;

        else{

            int l=1,r=top;

            while(l<=r){

                int mid=(l+r)/2;

                if(x>=st[mid])l=mid+1;

                else r=mid-1;

            }

            st[l]=x;

        }

    }

    cout<<top<<endl;

}