stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <string>

#include <map>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <stack>

#include <set>

#include <vector>

//const int maxn = 1e5+5;

#define ll long long

#define MAX INT_MAX

#define FOR(i,a,b) for( int i = a;i <= b;++i)



using namespace std;

string s1,s2;

int main()

{

    int pos=0,ans=0;

    cin>>s1;

    while(s1.find("WB",pos)!=-1)

    {

        pos=s1.find("WB",pos)+1;

        ans++;

    }

    pos=0;

    while(s1.find("BW",pos)!=-1)

    {

        pos=s1.find("BW",pos)+1;

        ans++;

    }

     cout<<ans;



}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

char str[100005];

int main(void)

{

	scanf("%s", str);

	int len = strlen(str);

	int ans = 0;

	char t = str[0];

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

		if (str[i] != t) {

			t = str[i];

			ans++;

		}

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

	return 0;

}
// Slower C++ solution:




#include <bits/stdc++.h>



using namespace std;





int main(){



    string s;

    cin >> s;

    int c = 0;

    for(int i = 0;i < s.size() - 1;i++)

    {

        if(s[i] != s[i+1]) c++;

    }

    cout << c << endl;

    return 0;

}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

char str[100005];

int main(void)

{

	scanf("%s", str);

	int len = strlen(str);

	int ans = 0;

	char t = str[0];

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

		if (str[i] != t) {

			t = str[i];

			ans++;

		}

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

	return 0;

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



using namespace std;

#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)

#define REP(i,a,b) REPP(i,a,b,1)

#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)

#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) REP(i,0,(int)a-1)

#define FORD(i,a) REV(i,(int)a-1,0)

#define PB push_back

#define POB pop_back

#define MP make_pair

#define FI first

#define SE second

typedef long long ll;

typedef unsigned long long ull;

typedef pair < int , int > pii;

typedef vector < int > vi;

typedef vector < pii > vii;

typedef vector < ll > vl;



const double EPS = 1e-9;

const double PI = acos(-1);

const int INF = 1e9;

const ll MOD = 1e9 + 7;



ll addMod(ll a, ll b){

	return (a+b) % MOD;

}



ll mulMod(ll a, ll b){

	return (a*b) % MOD;

}



/////////////////////////////////////////////////////////



string str;



int getType(char ch){

	if(ch == 'W') return 0;

	return 1;

}



int solve(){

	int bef = getType(str[0]), ret = 0;

	FOR(i,str.length()){

		int c = getType(str[i]);

		if(c != bef){

			ret++;

			bef = c;

		}

	}

	return ret;

}



int main(){

	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> str;

	cout << solve() << endl;

	return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

char str[100005];

int main(void)

{

	scanf("%s", str);

	int len = strlen(str);

	int ans = 0;

	char t = str[0];

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

		if (str[i] != t) {

			t = str[i];

			ans++;

		}

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

	return 0;

}
// Slower C++ solution:
//### In The Name Of GOD ###



// %% Remember; (((He))) is The (((Accepter))) %%



#include <bits/stdc++.h>



using namespace std;



typedef long long ll ;



#define int ll

#define pb push_back

#define bp pop_back

#define pf push_front

#define fp pop_front

#define X first

#define Y second

#define IO ios_base::sync_with_stdio(false);

#define sz(a) (int)(a.size())

#define sg(a, b) (a + b - 1) / b



const int MOD = 1000 * 1000 * 1000 + 7;

const int INF = 2 * 1000 * 1000 + 200;

const int MAXN = 100 * 1000 + 1;

const int MLOG = 18;

const int NMAX = 1 * 1000;



signed main(){

  IO;

  string s;

  cin >> s;

  int ans = 0;

  for(int i = 1; i < sz(s); i++){

    ans += (s[i] != s[i - 1]);

  }

  cout << ans;

}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

char str[100005];

int main(void)

{

	scanf("%s", str);

	int len = strlen(str);

	int ans = 0;

	char t = str[0];

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

		if (str[i] != t) {

			t = str[i];

			ans++;

		}

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

	return 0;

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



using namespace std;



char c[100010];

int cnt1,cnt2,len;



int main()

{

	scanf("%s",c+1);

	len=strlen(c+1);

	for(int i=2; i<=len; i++)if(c[i]!=c[i-1])cnt1++;

	for(int i=len-1; i>=1; i--)if(c[i]!=c[i+1])cnt2++;

	printf("%d",min(cnt1,cnt2));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.215222549954537x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

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

#include <cmath>

#include <cstdio>

#include <cstring>

#include <string>

#include <map>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <stack>

#include <set>

#include <vector>

//const int maxn = 1e5+5;

#define ll long long

#define MAX INT_MAX

#define FOR(i,a,b) for( int i = a;i <= b;++i)



using namespace std;

string s1,s2;

int main()

{

    int pos=0,ans=0;

    cin>>s1;

    while(s1.find("WB",pos)!=-1)

    {

        pos=s1.find("WB",pos)+1;

        ans++;

    }

    pos=0;

    while(s1.find("BW",pos)!=-1)

    {

        pos=s1.find("BW",pos)+1;

        ans++;

    }

     cout<<ans;



}


// Faster C++ solution for the same problem (measured speedup: 5.270606846894798x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

}
// Slower C++ solution:




#include <bits/stdc++.h>



using namespace std;





int main(){



    string s;

    cin >> s;

    int c = 0;

    for(int i = 0;i < s.size() - 1;i++)

    {

        if(s[i] != s[i+1]) c++;

    }

    cout << c << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.316385383631619x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

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



using namespace std;

#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)

#define REP(i,a,b) REPP(i,a,b,1)

#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)

#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) REP(i,0,(int)a-1)

#define FORD(i,a) REV(i,(int)a-1,0)

#define PB push_back

#define POB pop_back

#define MP make_pair

#define FI first

#define SE second

typedef long long ll;

typedef unsigned long long ull;

typedef pair < int , int > pii;

typedef vector < int > vi;

typedef vector < pii > vii;

typedef vector < ll > vl;



const double EPS = 1e-9;

const double PI = acos(-1);

const int INF = 1e9;

const ll MOD = 1e9 + 7;



ll addMod(ll a, ll b){

	return (a+b) % MOD;

}



ll mulMod(ll a, ll b){

	return (a*b) % MOD;

}



/////////////////////////////////////////////////////////



string str;



int getType(char ch){

	if(ch == 'W') return 0;

	return 1;

}



int solve(){

	int bef = getType(str[0]), ret = 0;

	FOR(i,str.length()){

		int c = getType(str[i]);

		if(c != bef){

			ret++;

			bef = c;

		}

	}

	return ret;

}



int main(){

	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> str;

	cout << solve() << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.352435445358645x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

}
// Slower C++ solution:
//### In The Name Of GOD ###



// %% Remember; (((He))) is The (((Accepter))) %%



#include <bits/stdc++.h>



using namespace std;



typedef long long ll ;



#define int ll

#define pb push_back

#define bp pop_back

#define pf push_front

#define fp pop_front

#define X first

#define Y second

#define IO ios_base::sync_with_stdio(false);

#define sz(a) (int)(a.size())

#define sg(a, b) (a + b - 1) / b



const int MOD = 1000 * 1000 * 1000 + 7;

const int INF = 2 * 1000 * 1000 + 200;

const int MAXN = 100 * 1000 + 1;

const int MLOG = 18;

const int NMAX = 1 * 1000;



signed main(){

  IO;

  string s;

  cin >> s;

  int ans = 0;

  for(int i = 1; i < sz(s); i++){

    ans += (s[i] != s[i - 1]);

  }

  cout << ans;

}


// Faster C++ solution for the same problem (measured speedup: 5.385722206205229x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

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

#include<algorithm>

#define ll long long

using namespace std;

char s[100000];

int main()

{

	int ans = 0;

	cin >> s;

	for(int i = 0;s[i + 1] != '\0'; i++)

		if(s[i] != s[i + 1]) ans++;

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.272446090498473x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

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

using namespace std;

typedef long long ll;

char s1[100005];

int main()

{

	scanf("%s",s1);

	int n=strlen(s1);

	char c=s1[0];

	ll num=0;

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

	{

		if(s1[i]!=c)

		{

			num++;

			c=s1[i];

		}

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.212771210810731x):


#include<stdio.h>

#include<string.h>

int main()

{

    char s[100005];

    int sum=0;

    scanf("%s", s);

    int len=strlen(s);

    for(int i=0;i<len-1;i++)

        if(s[i]!=s[i+1])

            sum++;

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

    return 0;

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

#include <iostream>

#include <vector>

using namespace std;



int rec[100001];

int len[100001];



int main(){







    int con, ptr = 0, sum = 0;

    scanf("%d", &con);

    while(con--){

        scanf("%d", &rec[ptr]);

        //len[ptr] = 1;

        ptr++;

    }





    vector<int> v;

    v.push_back(rec[0]);



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

    {

        int n = rec[i];



        if (n > v.back())

            v.push_back(n);

        else{

            //printf("      %d\n", *lower_bound(v.begin(), v.end(), n));

            *lower_bound(v.begin(), v.end(), n) = n;

        }

        //for(int g = 0; g < v.size(); ++g)printf("%d ", v[g]);

        //printf("\n");



    }



    printf("%d\n" , v.size());







return 0;

}

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

#include<algorithm>

using namespace std;

int a[100000+1];

int l[100000+1];

int main()

{

    int n;

    scanf("%d",&n);

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

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

    l[0]=a[0];

    int chang=1;

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

    {

        if(l[chang-1]<a[i]){

            l[chang++]=a[i];



        }else{

        *lower_bound(l,chang+l,a[i])=a[i];

        }

    }

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

    return 0;

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

#include <cstdio>



using namespace std;



const int MAX = 100010;

int a[MAX];

int L[MAX];

int n;

int len;



int main() {

    scanf("%d", &n);

    len = 0;

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

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

    }

    L[0] = a[0];

    len = 1;

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

        if (L[len-1] < a[i]) {

            L[len++] = a[i];

        } else {

            *lower_bound(L, L+len, a[i]) = a[i];

        }

    }

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



    return 0;

}

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

#include<algorithm>

using namespace std;

int a[100000+1];

int l[100000+1];

int main()

{

    int n;

    scanf("%d",&n);

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

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

    l[0]=a[0];

    int chang=1;

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

    {

        if(l[chang-1]<a[i]){

            l[chang++]=a[i];



        }else{

        *lower_bound(l,chang+l,a[i])=a[i];

        }

    }

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

    return 0;

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

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAX 100000

using namespace std;

int n;

int A[MAX+1],L[MAX];

int lis(){

    L[0]=A[0];

    int length=1;

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

        if(L[length-1]<A[i]){

            L[length++]=A[i];

        }else{

           *lower_bound(L,L+length,A[i])=A[i];//函数lower_bound()在first和last中的前?后?区??行二分?找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，?返回last的位置

        }

    }

    return length;

}





int main(){

    cin>>n;

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



    cin>>A[i];

    }

    cout <<lis()<<endl;

return 0;

}

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

#include<algorithm>

using namespace std;

int a[100000+1];

int l[100000+1];

int main()

{

    int n;

    scanf("%d",&n);

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

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

    l[0]=a[0];

    int chang=1;

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

    {

        if(l[chang-1]<a[i]){

            l[chang++]=a[i];



        }else{

        *lower_bound(l,chang+l,a[i])=a[i];

        }

    }

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

    return 0;

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

#include<iomanip>

#include<math.h>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<complex>

#define REP(i, N) for(ll i = 0; i < N; ++i)

#define FOR(i, a, b) for(ll i = a; i < b; ++i)

#define ALL(a) (a).begin(),(a).end()

#define pb push_back

#define INF (long long)1000000000

#define MOD 1000000007

#define EPS (long double) 1e-8

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<ll, ll> P;

int dh[4] = {1, 0, -1, 0};

int dw[4] = {0, 1, 0, -1};



using namespace std;



int main() {

	int n;

	cin>>n;

	vector<int> a(n);

	REP(i, n) cin>>a[i];

	vector<int> dp(n + 1);

	dp[0] = -1;

	FOR(i, 1, n + 1) {

		dp[i] = INF;

	}

	FOR(i, 1, n + 1) {

		vector<int>::iterator ite = lower_bound(ALL(dp), a[i - 1]);

		if(ite != a.end()) *ite = a[i - 1];

	}

	int res = 0;

	REP(i, n + 1) {

		if(dp[i] != INF) res = i;

	}

	cout<<res<<endl;

}

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

#include<algorithm>

using namespace std;

int a[100000+1];

int l[100000+1];

int main()

{

    int n;

    scanf("%d",&n);

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

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

    l[0]=a[0];

    int chang=1;

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

    {

        if(l[chang-1]<a[i]){

            l[chang++]=a[i];



        }else{

        *lower_bound(l,chang+l,a[i])=a[i];

        }

    }

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

    return 0;

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

#include <iostream>

#include <vector>

using namespace std;



int rec[100001];

int len[100001];



int main(){







    int con, ptr = 0, sum = 0;

    scanf("%d", &con);

    while(con--){

        scanf("%d", &rec[ptr]);

        //len[ptr] = 1;

        ptr++;

    }





    vector<int> v;

    v.push_back(rec[0]);



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

    {

        int n = rec[i];



        if (n > v.back())

            v.push_back(n);

        else{

            //printf("      %d\n", *lower_bound(v.begin(), v.end(), n));

            *lower_bound(v.begin(), v.end(), n) = n;

        }

        //for(int g = 0; g < v.size(); ++g)printf("%d ", v[g]);

        //printf("\n");



    }



    printf("%d\n" , v.size());







return 0;

}

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



int a[100001];

int b[100001], *pb = b + 1;



int main(void) {

	int n;

	scanf("%d", &n);

	for (int i = 0; i != n; ++i) scanf("%d", a + i);

	*pb++ = a[0];

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

		if (a[i] > pb[-1]) *pb++ = a[i];

		else {

			int* p1 = b + 1, *p2 = pb;

			while (p1 <= p2) {

				int* p = p1 + (p2 - p1) / 2;

				if (a[i] > *p) p1 = p + 1;

				else p2 = p - 1;

			}

			*p1 = a[i];

		}

	}

	printf("%d\n", pb - b - 1);

	return 0;

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

#include <cstdio>



using namespace std;



const int MAX = 100010;

int a[MAX];

int L[MAX];

int n;

int len;



int main() {

    scanf("%d", &n);

    len = 0;

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

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

    }

    L[0] = a[0];

    len = 1;

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

        if (L[len-1] < a[i]) {

            L[len++] = a[i];

        } else {

            *lower_bound(L, L+len, a[i]) = a[i];

        }

    }

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



    return 0;

}

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



int a[100001];

int b[100001], *pb = b + 1;



int main(void) {

	int n;

	scanf("%d", &n);

	for (int i = 0; i != n; ++i) scanf("%d", a + i);

	*pb++ = a[0];

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

		if (a[i] > pb[-1]) *pb++ = a[i];

		else {

			int* p1 = b + 1, *p2 = pb;

			while (p1 <= p2) {

				int* p = p1 + (p2 - p1) / 2;

				if (a[i] > *p) p1 = p + 1;

				else p2 = p - 1;

			}

			*p1 = a[i];

		}

	}

	printf("%d\n", pb - b - 1);

	return 0;

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

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAX 100000

using namespace std;

int n;

int A[MAX+1],L[MAX];

int lis(){

    L[0]=A[0];

    int length=1;

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

        if(L[length-1]<A[i]){

            L[length++]=A[i];

        }else{

           *lower_bound(L,L+length,A[i])=A[i];//函数lower_bound()在first和last中的前?后?区??行二分?找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，?返回last的位置

        }

    }

    return length;

}





int main(){

    cin>>n;

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



    cin>>A[i];

    }

    cout <<lis()<<endl;

return 0;

}

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



int a[100001];

int b[100001], *pb = b + 1;



int main(void) {

	int n;

	scanf("%d", &n);

	for (int i = 0; i != n; ++i) scanf("%d", a + i);

	*pb++ = a[0];

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

		if (a[i] > pb[-1]) *pb++ = a[i];

		else {

			int* p1 = b + 1, *p2 = pb;

			while (p1 <= p2) {

				int* p = p1 + (p2 - p1) / 2;

				if (a[i] > *p) p1 = p + 1;

				else p2 = p - 1;

			}

			*p1 = a[i];

		}

	}

	printf("%d\n", pb - b - 1);

	return 0;

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

#include<iomanip>

#include<math.h>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<complex>

#define REP(i, N) for(ll i = 0; i < N; ++i)

#define FOR(i, a, b) for(ll i = a; i < b; ++i)

#define ALL(a) (a).begin(),(a).end()

#define pb push_back

#define INF (long long)1000000000

#define MOD 1000000007

#define EPS (long double) 1e-8

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<ll, ll> P;

int dh[4] = {1, 0, -1, 0};

int dw[4] = {0, 1, 0, -1};



using namespace std;



int main() {

	int n;

	cin>>n;

	vector<int> a(n);

	REP(i, n) cin>>a[i];

	vector<int> dp(n + 1);

	dp[0] = -1;

	FOR(i, 1, n + 1) {

		dp[i] = INF;

	}

	FOR(i, 1, n + 1) {

		vector<int>::iterator ite = lower_bound(ALL(dp), a[i - 1]);

		if(ite != a.end()) *ite = a[i - 1];

	}

	int res = 0;

	REP(i, n + 1) {

		if(dp[i] != INF) res = i;

	}

	cout<<res<<endl;

}

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



int a[100001];

int b[100001], *pb = b + 1;



int main(void) {

	int n;

	scanf("%d", &n);

	for (int i = 0; i != n; ++i) scanf("%d", a + i);

	*pb++ = a[0];

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

		if (a[i] > pb[-1]) *pb++ = a[i];

		else {

			int* p1 = b + 1, *p2 = pb;

			while (p1 <= p2) {

				int* p = p1 + (p2 - p1) / 2;

				if (a[i] > *p) p1 = p + 1;

				else p2 = p - 1;

			}

			*p1 = a[i];

		}

	}

	printf("%d\n", pb - b - 1);

	return 0;

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

#include<iostream>

#include<algorithm>

using namespace std;

int a[100010],L[100010];	int n;

int lis(){

	L[0]=a[0];

	int l=1;

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

		if(a[i]>L[l-1]) L[l++]=a[i];

		else{

			*lower_bound(L,L+l,a[i])=a[i];

		}

	}

	return l;

}

int main(){



	scanf("%d",&n);

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

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

	}

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

}


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



int a[100001];

int b[100001], *pb = b + 1;



int main(void) {

	int n;

	scanf("%d", &n);

	for (int i = 0; i != n; ++i) scanf("%d", a + i);

	*pb++ = a[0];

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

		if (a[i] > pb[-1]) *pb++ = a[i];

		else {

			int* p1 = b + 1, *p2 = pb;

			while (p1 <= p2) {

				int* p = p1 + (p2 - p1) / 2;

				if (a[i] > *p) p1 = p + 1;

				else p2 = p - 1;

			}

			*p1 = a[i];

		}

	}

	printf("%d\n", pb - b - 1);

	return 0;

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

using namespace std;

#define INF 1145141919

int DP[100010];

int a[100010];

int main(){

  for(int i = 0;i < 100010;i++)DP[i]=INF;

  int n;

  cin >> n;

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

  for(int i = 0;i < n;i++)*lower_bound(DP,DP+n,a[i])=a[i];

  cout << (lower_bound(DP,DP+n,INF) - DP) << endl;

}




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

using namespace std;

const int limN = 1e5 + 5;



int W = 0 ;

int minW[limN];



int main() {

    int n ;

    scanf("%d", &n);

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

        scanf("%d", &a);

        k = lower_bound(minW, minW+W, a) - minW;

        minW[k] = a;

        W = max(W, k+1);

    }

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

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

using namespace std;

#define INF 1145141919

int DP[100010];

int a[100010];

int main(){

  for(int i = 0;i < 100010;i++)DP[i]=INF;

  int n;

  cin >> n;

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

  for(int i = 0;i < n;i++)*lower_bound(DP,DP+n,a[i])=a[i];

  cout << (lower_bound(DP,DP+n,INF) - DP) << endl;

}




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

using namespace std;



typedef vector<int> vi;



vi lis( vi arr ){

	vi seq, back(arr.size()), ans;

	for( int i = 0; i < arr.size(); i++ ){

		int res = 0, lo = 1, hi = seq.size();

		while( lo <= hi ){

			int mid = (lo+hi)/2;

			if( arr[seq[mid-1]] < arr[i] ) res = mid, lo = mid+1;

			else hi = mid-1;

		}

		if( res < seq.size() ) seq[res] = i;

		else seq.push_back( i );

		back[i] = res == 0 ? -1 : seq[res-1];

	}

	int at = seq.back();

	while( at != -1 ) ans.push_back( at ), at = back[at];

	reverse(ans.begin(), ans.end());

	return ans;

}



int main(){

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

	

	int N;

	

	cin >> N;

	vi num(N);

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

		cin >> num[i];

	}

	

	cout << lis(num).size() << '\n';

	

	

	return 0;

}