akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m;
    while(cin >> n >> m, n) {
        vector<vector<bool>> relation(n, vector<bool>(n));
        for(int i=0; i<m; ++i) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            relation[a][b] = relation[b][a] = true;
        }
        vector<bool> friends(n);
        for(int i=0; i<n; ++i) {
            if(relation[0][i]) {
                friends[i] = true;
                for(int j=0; j<n; ++j) {
                    if(relation[i][j]) {
                        friends[j] = true;
                    }
                }
            }
        }
        friends[0] = false;
        cout << count(friends.begin(), friends.end(), true) << endl;
    }
}


Measured memory_bytes: 3128
n = int(input())
a = list(map(int,input().split()))

# i個使う時の要素の和の最大値
dp = [0]*(n+1)
dp[1] = 0
dp[2] = max(a[0],a[1])

# 奇数の番号の累積和
b = [0]*(n+1)
b[1] = a[0]
for i in range(1,n-1,2):
    b[i+2] = b[i] + a[i+1]
# print(b)

for i in range(3,n+1):
    if i % 2 == 0:
        dp[i] = max(dp[i-2] + a[i-1], b[i-1])
    else:
        dp[i] = max(dp[i-2] + a[i-1], dp[i-3] + a[i-2], b[i-2])

# print(dp)
print(dp[n])

Measured memory_bytes: 105440
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <fstream>
#include <cassert>
using namespace std;

//common
typedef long long i64,ll;

#define BR "\n"
#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,l,r) for(int i=(l);i<(int)(r);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}

template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

string BITtoString(int bit){
    stringstream ss;
    while(bit!=0){ss<<(bit%2);bit/=2;}
    string res=ss.str();reverse(ALL(res));
    return res;
}

template<typename T,typename V> inline T pmod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}


ll MOD=1000000007;

class Main{
public:
	
	void run(){
		
		while(true){
			int N;cin >> N;if(N==0)break;
			string cs;cin >> cs;

			vector<int> res(N);
			int place=0;

			int v=0;
			REP(i,100){
				if(cs[i]=='M'){
					res[v]++;
				}else if(cs[i]=='S'){
					place++;
					place+=res[v];
					res[v]=0;
				}else if(cs[i]=='L'){
					res[v]++;
					res[v]+=place;
					place=0;
				}
				v=(v+1)%N;
			}
			sort(ALL(res));
			cout << toString(res)<<" "<<place<<endl;
		}

	}
};

 int main(){
	//ios::sync_with_stdio(false);
 	Main().run();
 	return 0;
 }

Measured memory_bytes: 1240
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;



int main() {
    string S;
    cin >> S;

    int num = S.size();
    vector<bool> check(26);
    rep(i, num) {
        check[S[i]-'a'] = true;
    }

    if(num != 26) {
        cout << S;
        int i;
        rep(i_, num+1) {
            if(!check[i_]) {
                i = i_;
                break;
            }
        }
        char x = 'a'+i;
        cout << x << endl;
    } else {
        for(int i = num-1; i>0; --i) {
            if(S[i] > S[i-1]) {
                string h = S.substr(i);
                reverse(all(h));
                string::iterator itr = lower_bound(all(h), S[i-1]);
                cout << S.substr(0, i-1) << *itr << endl; 
                break;
            }
            if(i == 1) {
                cout << -1 << endl;
            }
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,i,k;
  cin>>n>>m;
  if(n==m)
  {
    for(i=0; i<n; i++)
    {
      cout<<n;
    }
  }
  else if(n>m)
  {
    for(i=0; i<n; i++)
    {
      cout<<m;
    }
  }
  else
  {
    for(i=0; i<m; i++)
    {
      cout<<n;
    }
  }
}

Measured memory_bytes: 256
# A = [list(map(int, input().split())) for _ in range(3)]
k = int(input())
# B = [int(input()) for _ in range(n)]
# X = list(map(int, input().split()))
# a, b = map(int, input().split())
ans = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1,
        15, 2, 2, 5, 4, 1, 4, 1, 51]
print(ans[k-1])


Measured memory_bytes: 2940
def main():
    import sys
    input = sys.stdin.readline

    S = list(input().rsplit()[0])
    T = list(input().rsplit()[0])

    NS = len(S)
    NT = len(T)

    # dp[i+1][j+1]: Sのi文字目と，Tのj文字目までのLCS
    dp = [[0]*(NT+1) for _ in range(NS+1)]

    for i in range(NS):
        for j in range(NT):
            if S[i] == T[j]:
                # dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

    ans = ''
    i = NS
    j = NT
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            ans = S[i-1]+ans
            j -= 1
            i -= 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 111708
#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int n;
	int a[42858][2]={0};
	a[1][0]=1;
	a[1][1]=1;
	for(int i=2;i<=42857;i++){
		if(a[i][0]==2) goto end1;
		for(int j=1;j<i/2+1;j++){
			if(a[j][0]==1){
				if((7*i-1)%(7*j-1)==0){
					a[i][0]=2;
					goto end1;
				}
			}
			if(a[j][1]==1){
				if((7*i-1)%(7*j+1)==0){
					a[i][0]=2;
					goto end1;
				}
			}
		}
		a[i][0]=1;
		for(int j=1;j*(7*i-1)+i<42857;j++){
			a[j*(7*i-1)+i][0]=2;
			a[j*(7*i-1)-i][1]=2;
		}
		end1:;
		if(a[i][1]==2) goto end2;
		for(int j=1;j<i/2+1;j++){
			if(a[j][0]==1){
				if((7*i+1)%(7*j-1)==0){
					a[i][1]=2;
					goto end2;
				}
			}
			if(a[j][1]==1){
				if((7*i+1)%(7*j+1)==0){
					a[i][1]=2;
					goto end2;
				}
			}
		}
		a[i][1]=1;
		for(int j=1;j*(7*i+1)+i<42857;j++){
			a[j*(7*i+1)+i][1]=2;
			a[j*(7*i+1)-i][0]=2;
		}
		end2:;
	}
	while(cin>>n){
		if(n==1) break;
		int y[100]={0},ct=0;
		for(int i=1;i<n/7+3;i++){
			if(a[i][0]==1&&n%(7*i-1)==0){
				y[ct]=7*i-1;
				ct++;
			}
			if(a[i][1]==1&&n%(7*i+1)==0){
				y[ct]=7*i+1;
				ct++;
			}
		}
		cout<<n<<":";
		int a=0;
		while(y[a]>0){
			cout<<" "<<y[a];
			a++;
		}
		cout<<endl;
	}
    return 0;
}

Measured memory_bytes: 1500
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int x;
	cin>>x;
	ll ans = 1000*(x/500);
	x %=500;
	ans += 5*(x/5);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		String s= scanner.next();

		if (s.equals(s.toUpperCase())) {
			System.out.println("A");
		} else {
			System.out.println("a");
		}

	}
}


Measured memory_bytes: 35476
loop = int(raw_input())
taro = []
hanako = []
taro_score = 0
hanako_score = 0
for i in range(loop):
    t, h = raw_input().split()
    taro += [t]
    hanako += [h]

for t, h in zip(taro,hanako):
    if t < h:
        hanako_score += 3
    if t > h:
        taro_score += 3
    if t == h:
        taro_score += 1
        hanako_score += 1
print "%d %d" % (taro_score, hanako_score)

Measured memory_bytes: 6440
#include <bits/stdc++.h>
using namespace std;
int main(){
 string S;
  int Q;
  cin >> S >> Q;
  bool isreverse = false;
  
  for(int i=0;i<Q;i++){
    int T;
    cin >> T;
    if(T==1&&isreverse) isreverse = false;
    else if(T==1&&!isreverse) isreverse = true;
    
    if(T==2){
      int F;
      string s;
      cin >> F >> s;
      
      if(F==1&&isreverse) S += s;
      if(F==1&&!isreverse) S.insert(0,s);
      if(F==2&&isreverse) S.insert(0,s);
      if(F==2&&!isreverse) S += s;
    }
  }
  
  if(isreverse) reverse(S.begin(),S.end());
  
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 3920
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt(),l=sc.nextInt();
		int[][] A = new int[n][m];
		int[][] B = new int[m][l];
		long[][] C = new long[n][l];

		for(int i=0; i<n;i++) {
			for(int j=0; j<m;j++) {
				A[i][j]=sc.nextInt();
			}
		}

		for(int i=0; i<m;i++) {
			for(int j=0; j<l ;j++) {
				B[i][j]=sc.nextInt();
			}
		}

		for(int i=0; i<n; i++) {
			for(int j=0;j<l; j++) {
				long tmp=0;
				for(int k=0; k<m; k++) {
					tmp+= A[i][k]*B[k][j];
				}
				C[i][j]=tmp;
			}
		}

		for(int i=0; i<n; i++) {
			for(int j=0; j<l; j++) {
				if(j==0) {
					System.out.print(C[i][j]);
				}else {
					System.out.print(" "+C[i][j]);
				}
			}
			System.out.println("");
		}

	}
}



Measured memory_bytes: 53676
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

bool prime(int num) {
	if (num % 2 == 0) return false;
	double hey = sqrt(num);

	for (int i = 3; i <= hey; i += 2) {
		if (num  % i == 0) { return false; }
	}

	return true;

}



int main() {

	int x; cin >> x;
	if (x == 2) { cout << "2" << endl; goto end; }
	for (int i = x; ; i++) {
		if (prime(i) == true) { cout << i << endl; break; }
	}

	end:

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

std::string s;
int main() {
	std::cin >> s;

	bool ok = false;
	for (size_t i = 0; i < s.size(); ++i)
		for (size_t j = 0; i + j <= s.size(); ++j)
			if (s.substr(0, i) + s.substr(i + j, s.size()) == "keyence")
				ok = true;
	if (ok)
		std::cout << "YES" << std::endl;
	else
		std::cout << "NO" << std::endl;
	return 0;
}


Measured memory_bytes: 256
/************************Code by Hardik Aggarwal!!!!***********************************/

#include<bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;

typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =1e9+7;

int main()
{
    
  
    IOS
    ll n;
    cin>>n;
    double a[n];
    double ans=0.0;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        
    }
    sort(a,a+n);
    double last=a[0];
    for(ll i=1;i<n;i++)
    {
        last=(last+a[i])/2.0;
    }

    cout<<last;
    

}
    
 
    
    



Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    int n;
    int ans=0;
    while(cin>>n,n){
        ans=0;
        int hoge=1000-n;
        int a=hoge/500;
        hoge-=a*500;
        ans+=a;
        a=hoge/100;
        hoge-=a*100;
        ans+=a;
        a=hoge/50;
        hoge-=a*50;
        ans+=a;
        a=hoge/10;
        hoge-=a*10;
        ans+=a;
        a=hoge/5;
        ans+=a;
        hoge-=a*5;
        cout<<ans+hoge<<endl;
        
    }
}

Measured memory_bytes: 3072
x = int(input())

if x < 600:
    print(8)
elif x < 800:
    print(7)
elif x < 1000:
    print(6)
elif x < 1200:
    print(5)
elif x < 1400:
    print(4)
elif x < 1600:
    print(3)
elif x < 1800:
    print(2)
else:
    print(1)

Measured memory_bytes: 9176
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools
import itertools
import math
import sys

INF = float('inf')
YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int):
    return [NO, YES][N == M]


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(f'{solve(N, M)}')


if __name__ == '__main__':
    main()


Measured memory_bytes: 75172
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 200000

int n, k;
long c[MAXN];

int input() {
	if (scanf("%d %d", &n, &k) < 0) return 0;
	return 1;
}

void init() {
}

long solve() {
	long m = 0;
	memset(c, 0, sizeof(*c)*k);
	for (int i=1; i<=n; i++) {
		if (i*2 % k == 0) c[i % k]++;
	}
	for (int i=0; i<k; i++)
		m += c[i]*c[i]*c[i];
	return m;
	//return m * (m-1) * (m-2)/6 + m + m * (m-1);
}

void output(long ans) {
	printf("%ld\n", ans);
}

void cleanup() {
}

int main() {
	//int ca; scanf("%d", &ca);
	while (input()) {
		init();
		output(solve());
		cleanup();
		//break;
	}
}





Measured memory_bytes: 1664
// problem: "https://atcoder.jp/contests/abc147/tasks/abc147_c"

#include<bits/stdc++.h>
#define Pair pair<int,int>

using namespace std;

bool checkPos(vector<Pair>G[],int n,int J)
{
    int p = 0;
    int j = J;
    while(j)
    {
        if(j&1)
        {
            int i;
            for(i=0;i!=G[p].size();i++)
                if((J ^ (G[p][i].second << G[p][i].first)) & (1 << G[p][i].first))
                    return false;
        }

        j = j>>1;
        p++;
    }

    return true;
}

int num1(int j)
{
    int c = 0;
    while(j)
    {
        if(j&1)
            c++;

        j = j>>1;
    }

    return c;
}

int maxH(vector<Pair>G[],int n)
{
    int c = 0;
    int j = 0;

    while(j < (1<<n))
    {
        if(checkPos(G,n,j))     // define
            c = max(c,num1(j));     // define

        j++;
    }

    return c;
}

int main()
{
    int n;
    cin>>n;

    int i;
    vector<Pair>V[n];

    for(i=0;i!=n;i++)
    {
        int x,j;
        cin>>x;

        for(j=0;j!=x;j++)
        {
            int a,b;
            cin>>a>>b;

            V[i].push_back(Pair(a-1,b));
        }
    }

    cout<<maxH(V,n);        // define

    return 0;
}


Measured memory_bytes: 256
def getlist():
	return list(map(int, input().split()))

N = int(input())
p = getlist()

L = []
c = 0
for i in range(N):
	if p[i] == i + 1:
		c += 1
	else:
		L.append(c)
		c = 0

L.append(c)
ans = 0
for i in L:
	ans += (i + 1) // 2

print(ans)

Measured memory_bytes: 14008
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
int main(){
	std::ios::sync_with_stdio(false);
	int n,i,c=0,w=0,minn=inf;
	string s;
	cin>>n>>s;
	rep(i,s.length()){
		if(s[i]=='E'){
			c++;
		}
	}
	rep(i,s.length()){
		if(s[i]=='E'){
			c--;
		}
		minn=min(minn,w+c);
		if(s[i]=='W'){
			w++;
		}
	}
	cout<<minn<<endl;
} 
	

Measured memory_bytes: 720
object Main {
   def main (args: Array[String]) {
     val S: Int = scala.io.StdIn.readLine().toInt
     val h = S / 3600
     val m = (S - h * 3600) / 60
     val s = (S - h * 3600 - m * 60)
     println( h + ":" + m + ":" + s);
  }
}

Measured memory_bytes: 43704
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if (a!=c) cout << 1 << endl;
    else cout << 0 << endl; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

ll gcd(ll a, ll b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;  cin >> n;
    ll ans = 1;
    rep(i, n) {
      ll t;  cin >> t;
      ans = lcm(ans, t);
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
int main(){
	string S,T;
	int s,t,ans;
	ans=10000;
	cin>>S>>T;
	s=S.size(),t=T.size();
	for(int i=0;i+t<=s;i++){
		int tot=t;
		for(int j=0;j<t;j++){
			if(S[i+j]==T[j]){
				tot--;
			}
		}
		if(tot<ans) ans=tot;
	}
	cout<<ans;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n,m;
  cin>>n>>m;
  vector<int64_t> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  sort(a.begin(),a.end());
  priority_queue<int64_t> A;
  for(int i=0;i<n;i++){
  A.push(a.at(i));
  }
  for(int i=0;i<m;i++){
  int64_t max=A.top();
    max/=2;
    A.pop();
    A.push(max);
  }
  vector<int64_t> b(n);
  for(int i=0;i<n;i++){
  b.at(i)=A.top();
  A.pop();
  }
  int64_t ans=0;
  for(int i=0;i<n;i++){
    ans+=b.at(i);
  }
  cout<<ans;
}

Measured memory_bytes: 2676
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String S = sc.next();

		boolean app[] = new boolean[26];

		for (int i = 0; i < 26; i++) {
			app[i] = false;
		}

		for (int i = 0; i < S.length(); i++) {
			app[S.charAt(i) - 'a'] = true;
		}

		for (int i = 0; i < 26; i++) {
			if(!app[i]) {
				char c = (char)('a' + i);
				System.out.println(c);
				System.exit(0);
			}
		}
		System.out.println("None");
	}
}


Measured memory_bytes: 23988
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

int main() {
  
  int n;
  cin >> n;
  vector<long long> a(n+1);
  a.at(0) = 2;
  a.at(1) = 1;
  for(int i = 2; i <= n; i++) {
    a.at(i) = a.at(i-1) + a.at(i-2);
  }
  cout << a.at(n) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する


int main() {
    int N;
    cin >> N;
    vector<int> A(N),B(N),C(N);
    REP(i,0,N) cin >> A[i];
    REP(i,0,N) cin >> B[i];
    REP(i,0,N) cin >> C[i];

    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    sort(C.begin(),C.end());
    vector<int> cnB(N,0);

    vector<pair<int,int> > pBC;
    REP(i,0,N){
        pBC.push_back(make_pair(B[i],2));
    }
    REP(i,0,N){
        pBC.push_back(make_pair(C[i],1));
    }

    sort(all(pBC));

    int a = 0;
    int cnt = N;
    REP(i,0,pBC.size()){
        if(pBC[i].second == 1){
            --cnt;
        }else{
            cnB[a] = cnt;
            ++a;
        }
    }

    vector<pair<int,int> > pAB;
    REP(i,0,N){
        pAB.push_back(make_pair(A[i],2));
    }
    REP(i,0,N){
        pAB.push_back(make_pair(B[i],1));
    }

    sort(all(pAB));


    ll cntl = 0LL;
    REP(i,0,N){
        cntl += 1LL * cnB[i];
    }
    a = 0;
    int b = 0;
    vector<ll> cnA(N,0LL);

    REP(i,0,pAB.size()){
        if(pAB[i].second == 1){
//            cnt -=
            cntl -= cnB[b];
            b++;
        }else{
//            cnB[a] = cnt;
//            ++a;
            cnA[a] = 1LL * cntl;
            a++;
        }
    }

    ll ans = 0LL;
    REP(i,0,N){
        ans += cnA[i];
    }

    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 6384
(defun f (heights maximum)
  (cond
    ((null heights) 0)
    ((>= (car heights) maximum)
     (1+ (f (cdr heights) (car heights))))
    (t (f (cdr heights) maximum))))

(let* ((n (read))
       (h (loop for i below n collect (read))))
  (format t "~A~%" (f h 0)))


Measured memory_bytes: 5608
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
    ll N, A, B;
    cin >> N >> A >> B;

    ll ret = (N / (A + B)) * A;
    ll tmp = N % (A + B);
    if (tmp >= A) {
        ret += A;
    } else {
        ret += tmp;
    }

    cout << ret << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)


using namespace std;
using ll = long long;

int main(void)
{
    
    int r;
    double ans;
    cin >> r;
    ans =2*r*3.1415;
    cout <<ans <<endl;
    return 0;
}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  int N, M;
  cin >> N >> M;
  priority_queue<long long> pq;
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    pq.push(A);
  }
  for (int i = 0; i < M; i++) {
    long long top = pq.top();
    pq.pop();
    pq.push(top / 2);
  }

  long long ans = 0;
  for (int i = 0; i < N; i++) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl,dotti;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
  
       cin.tie(0);
    ios::sync_with_stdio(false);
      
      cin>>n;
      rep(i,n)cin>>a[i];
      if(n==1)Cout(1);
      else{
        ll flags;
        rep(i,n){
          if(a[i]<a[i+1]){
            fl=true;
            flags=i;
            break;
          }
          else if(a[i]>a[i+1]){
            fl=false;
            flags=i;
            break;
          }
        }
        dotti=false;
        rrep(i,flags,n-1){
          if(a[i]==a[i+1])continue;
          if(dotti){
            if(a[i]<a[i+1])fl=true;
            else fl=false;
            dotti=false;
          }
          if(fl){
            if(a[i]>a[i+1]){
              dotti=true;
              ans++;
            }
          }
          else{
            if(a[i]<a[i+1]){
              dotti=true;
              ans++;
            }
          }
        }
         Cout(ans+1);
      }
    
       
return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define SORT(a) sort(a.begin(),a.end())

int main() {
	
	//vector<int> a(n);
	//cout << "test" << endl;

	cin.tie(0);
	ios::sync_with_stdio(false);
	
	//string ans="YES";


	int n,d;
	cin >> n >> d;
	
	int ans;
	
	ans=n/(2*d+1);
	if(n%(2*d+1)) ans++;
	
	
	cout << ans << "\n";
	
	
	return 0;

    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    using ll = long long;
    ll x, y;
    cin >> x >> y;

    int ans = 0;
    for(int i = 0; i < 100; i++)
    {
        if(x > y) break;
        x *= 2;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
long long n,m,a[1000005],a1[1000005],v2[1000005],usj,k,m1;
map <long long, long long> ans1;
int main()
{
	cin>>n>>m;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i];
		a[i]/=2;
	}
  long long usg=a[1];
  long long usj=a[1];
	for (int i=2 ; i<=n; i++)
    {
      usg=__gcd(usj,a[i]);
      usj=(usj*a[i])/usg;
      if (usj>m) 
      {cout<<0<<endl;
       return 0;
      }
    }
       
          // cout<<usj<<endl;
 
 
	for (long long i=1; i<=n; i++)
	{
		if ((usj/a[i])%2==0)
		{
			cout<<0<<endl;
			return 0;
		}
	}
//  cout<<usj<<endl;
	k=m/usj;
	if (k%2==0) k/=2;
	else k=k/2+1;
	cout<<k<<endl;
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1e9

struct Node {
	int n, rest, cost;
};
struct Edge {
	int to, dist, enemy;
};

bool operator >(const Node& n1, const Node& n2) {
	return n1.cost > n2.cost;
}

int main() {
	int N, M, L;
	while (cin >> N >> M >> L, N || M || L) {
//		int dist[100][100], enemy[100][100];
//		fill(&dist[0][0], &dist[0][0]+100*100, INF);
//		fill(&enemy[0][0], &enemy[0][0]+100*100, INF);
		vector< vector<Edge> > edges(N);
		for (int i = 0; i < M; ++i) {
			int a, b, d, e; cin >> a >> b >> d >> e; --a, --b;
			edges[a].push_back( (Edge){b, d, e} );
			edges[b].push_back( (Edge){a, d, e} );
//			dist[a][b] = dist[b][a] = d;
//			enemy[a][b] = enemy[b][a] = e;
		}
//		for (int i = 0; i < N; ++i) dist[i][i] = enemy[i][i] = 0;
		int dp[100][101]; // dp[to][rest] = min enemy;
		fill(&dp[0][0], &dp[0][0]+100*101, INF);
		priority_queue<Node, vector<Node>, greater<Node> > Q; Q.push( (Node){0, L, 0} );
		while ( !Q.empty() ) {
			Node node = Q.top(); Q.pop();
			int n = node.n, rest = node.rest, cost = node.cost;

			if (cost >= dp[n][rest]) continue;
			dp[n][rest] = cost;

			for (int i = 0; i < edges[n].size(); ++i) {
				Edge& e = edges[n][i];
				if (rest >= e.dist) {
					Q.push( (Node){e.to, rest-e.dist, cost} );
				}
				Q.push( (Node){e.to, rest, cost+e.enemy} );
			}
		}

		int ans = INF;
		for (int i = 0; i <= L; ++i) {
			ans = min(ans, dp[N-1][i]);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 12368
n,k=list(map(int,input().split()))
num=int((n-1)*(n-2)/2-k)

if num<0:
    print(-1)
else:
    print(n-1+num)
    for i in range(n-1):
        print(1,i+2)
    total=0
    for i in range(n-1):
        for j in range(i+1,n-1):
            total+=1
            if total>num:
                exit()
            print(i+2,j+2)
            

Measured memory_bytes: 3608
#include "bits/stdc++.h"

#include <atcoder/all>

using namespace std;
using namespace atcoder;

//#define int long long
#define ll long long

ll INF = (1LL << 60);
int mod = 998244353;
using P = pair<int, int>;
signed main() {
	int N; cin >> N;
	vector<pair<int, P>>p;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		p.push_back({ y,{x,i} });
	}
	sort(p.begin(), p.end());
	set<P>st;
	dsu uf(N);
	for (int i = 0; i < N; i++) {
		st.insert({ p[i].second.first, p[i].second.second });
	}
	for (int i = 0; i < N; i++) {
		int t = p[i].second.first, idx = p[i].second.second;
		auto itr = st.upper_bound({ t,idx });
		while (itr != st.end()) {
			int idx2 = (*itr).second;
			if (uf.same(idx, idx2))break;
			uf.merge(idx, idx2);
			itr++;
		}
		st.erase({ t,idx });
	}
	for (int i = 0; i < N; i++) {
		cout << uf.size(i) << endl;
	}
	return 0;
}


Measured memory_bytes: 15840
s = input()
front = int(s[:2])
back = int(s[2:])
def isMM(num):
    if 1<=num<=12:
        return True
    else:
        return False

if isMM(front) and isMM(back):
    print('AMBIGUOUS')
elif isMM(front) and not isMM(back):
    print('MMYY')
elif not isMM(front) and isMM(back):
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3060
/*
 * atcoder/abc130/a.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

string S;

void input() {
  cin >> S;
}

void solve() {
  // 0123456789
  // yyyy/mm/dd
  int m = stoi(S.substr(5, 2));
  int d = stoi(S.substr(8, 2));
  if (m <= 4) {
    cout << "Heisei" << endl;
    return;
  }

  cout << "TBD" << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Hello
{

    static void Main(string[] args)
    {
        int count = 0;
        var AB = Console.ReadLine().Split(' ');
        var AC =int.Parse( AB[0]);
        var BB = int.Parse(AB[1]);
        for (int i = 1; i <BB; i++)
        {
        
            
            if ((AC-1) * i+1 >= BB)
            {
                count = count + i;
                break;
            }
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 1e5 + 7;

int c[N];
vector<pair<int, int>> g[N];

void dfs(int cur, int p, int cl) {
	c[cur] = cl;
	for (auto t : g[cur]) {
		if (t.first != p) {
			dfs(t.first, cur, cl ^ t.second);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	

	int n;
	cin >> n;
	for (int i = 0; i + 1 < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		w %= 2;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dfs(0, -1, 0);
	for (int i = 0; i < n; i++) {
		cout << c[i] << '\n';
	}
}


Measured memory_bytes: 8320
#include <cinttypes>
#include <cstdint>
#include <cstdio>
#include <algorithm>
using ui16 = std::uint_fast16_t;
using ui32 = std::uint_fast32_t;
using std::scanf;
using std::printf;
const ui32 N_MAX = 100000;
ui16 h[N_MAX];
ui32 F[N_MAX];
int main()
{
    ui32 N;
    scanf("%" SCNuFAST32, &N);
    for (ui32 i = 0; i < N; ++i)
    {
        scanf("%" SCNuFAST16, h + i);
        if (i) F[i] = i > static_cast<ui32>(1) ? std::min(F[i - static_cast<ui32>(2)] + static_cast<ui32>(std::max(h[i - static_cast<ui32>(2)], h[i]) - std::min(h[i - static_cast<ui32>(2)], h[i])), F[i - static_cast<ui32>(1)] + static_cast<ui32>(std::max(h[i - static_cast<ui32>(1)], h[i]) - std::min(h[i - static_cast<ui32>(1)], h[i]))) : F[i - static_cast<ui32>(1)] + static_cast<ui32>(std::max(h[i - static_cast<ui32>(1)], h[i]) - std::min(h[i - static_cast<ui32>(1)], h[i]));
    }
    printf("%" PRIuFAST32, F[N - static_cast<ui32>(1)]);
    return 0;
}

Measured memory_bytes: 1664
from math import factorial

N, K = list(map(int, input().split()))

x = 1000000007

num = factorial(N - K + 1) * factorial(K - 1)

for i in range(1, K + 1):
    if N - K < i - 1:
        print(0)
    else:
        denom = factorial(i) * factorial(N - K + 1 - i) * factorial(i - 1) * factorial(K - i)
        v = num // denom

        print(v % x)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	ll n; cin >> n;
	ll res=n*(n+1)/2;
	res-=3*(n/3)*(n/3+1)/2;
	res-=5*(n/5)*(n/5+1)/2;
	res+=15*(n/15)*(n/15+1)/2;
	cout << res << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int w, h, n; cin >> w >> h >> n;
    vector<vector<int>> hw(h, vector<int>(w, 1));

    for(int i = 0; i < n; i++) {
        int x, y, a; cin >> x >> y >> a;
        if(a == 1) {
            for(int j = 0; j < h; j++) {
                for(int k = 0; k < x; k++) {
                    hw[j][k] = 0;
                }
            }
        } else if(a == 2) {
            for(int j = 0; j < h; j++) {
                for(int k = x; k < w; k++) {
                    hw[j][k] = 0;
                }
            }
        } else if(a == 3) {
            for(int j = 0; j < y; j++) {
                for(int k = 0; k < w; k++) {
                    hw[j][k] = 0;
                }
            }
        } else if(a == 4) {
            for(int j = y; j < h; j++) {
                for(int k = 0; k < w; k++) {
                    hw[j][k] = 0;
                }
            }
        }
    }

    int ans = 0;

    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            ans += hw[i][j];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;

int main() {
	int n, x[1000], y[1000], i, j;
	double d;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (i = 0; i < n; i++) {
		cin >> y[i];
	}
	for (i = 0, d = 0; i < n; i++) {
		d += fabs((double)(x[i]-y[i]));
	}
	cout << fixed << setprecision(6) << d << endl;
	for (i = 0, d = 0; i < n; i++) {
		d += pow(fabs((double)(x[i]-y[i])), 2);
	}
	cout << fixed << setprecision(6) << sqrt(d) << endl;
	for (i = 0, d = 0; i < n; i++) {
		d += pow(fabs((double)(x[i]-y[i])), 3);
	}
	cout << fixed << setprecision(6) << pow(d, 1.0/3.0) << endl;
	for (i = 0, d = 0; i < n; i++) {
		d = fabs((double)(x[i]-y[i])) > d ? fabs((double)(x[i]-y[i])) : d;
	}
	cout << fixed << setprecision(6) << d << endl;
	return 0;
}

Measured memory_bytes: 1308
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>
#include <bitset>
#include <atcoder/all>

//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(ll i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const double PI = 3.1415926535897932;



int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << ketasitei;

	ll n, m;
	cin >> n >> m;
	vector<ll> a(m), b(m);
	dsu d(n);
	rep(i, m)
	{
		cin >> a[i] >> b[i];
		d.merge(a[i] - 1, b[i] - 1);
	}

	vector<ll> use(n, 0);
	ll ans = 0;
	rep(i, n)
	{
		if (!use[d.leader(i)])
		{
			ans++;
			use[d.leader(i)]++;
		}
	}
	cout << ans-1 << endl;

	return 0;
}

Measured memory_bytes: 6140
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<-1<<endl;return 0;}
//template
//main
signed main(){
  int N;cin>>N;
  std::vector<int> v(N);
  for(int i=0;i<N;i++)cin>>v[i];
  reverse(v.begin(),v.end());
  typedef pair<int,int> P;
  set<P> s;
  s.insert(P(LINF,0));
  for(int i=0;i<N;i++){
    P p=*s.upper_bound(P(v[i],i));
    if(p.first<LINF)s.erase(p);
    s.insert(P(v[i],i));
  }
  cout<<s.size()-1<<endl;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>

using namespace std;


int main(int argc, char *argv[])
{
   
    
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    
    double x1, y1, x2, y2;
    
    cin >> x1 >> y1 >> x2 >> y2;
    cout << fixed << setprecision(8) << sqrt(pow(x2-x1,2)+pow(y2-y1,2)) << endl;
    
    return 0;
}



Measured memory_bytes: 3272
/*-- ILSH  --*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < ll >
#define vll vector < ll > 
#define dt cout<<"HERE\n";
#define pii pair < ll , ll >
#define pll pair < ll , ll >
#define vpi vector < pii >
#define vpl vector < pll >
#define fi first
#define se second 
#define sz size 
#define len length 
const ll inf=1e18+1e17;
const ll mod =1e9+7;
using cd= complex < double > ;
//const ll mod = 998244353;

ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
const ll N = 2e5+5;
ll arr[N];
bool comp( pll p1, pll p2){
	return p1.fi>p2.fi;
}
void solve(){
	int n,k;
	cin>>n>>k;
	vpl v;
	for ( int i=0;i<n;i++){
		cin>>arr[i];
		v.pb( mp( (arr[i]<0?-arr[i]:arr[i]),( arr[i]>0?0:(arr[i]<0?1:-1))));
	}
	sort( v.begin(),v.end(),comp);
	ll mo=1;
	int cnt=0;
	for ( int i=0;i<k;i++){
		mo=(mo*v[i].fi)%mod;
		if ( v[i].se==1)
			cnt++;
		if ( v[i].se==-1){
			cout<<0<<'\n';
			return;
		}
	}
	if ( cnt%2){
		ll maxpo=-1,maxno=-1;
		for ( int i=k;i<n;i++)
			if ( v[i].se==1){
				maxno=v[i].fi;
				break;
			}
		for ( int i=k;i<n;i++)
			if ( v[i].se==0){
				maxpo=v[i].fi;
				break;
			}
		ll minpo=-1,minno=-1;
		for ( int i=k-1;i>=0;i--)
			if ( v[i].se==1){
				minno=v[i].fi;
				break;
			}
		for ( int i=k-1;i>=0;i--)
			if ( v[i].se==0){
				minpo=v[i].fi;
				break;
			}
		if ( maxpo!=-1&&minpo!=-1&&minno!=-1&&maxno!=-1){
			if ( maxpo*minpo>minno*maxno){
				mo=(mo*modInverse( minno,mod))%mod;
				mo=( mo* maxpo)%mod;
			}else{
				mo=(mo*modInverse( minpo,mod))%mod;
				mo=( mo* maxno)%mod;
			}
		}
		else
		if ( maxpo!=-1&&minno!=-1){
			mo=(mo*modInverse( minno,mod))%mod;
			mo=( mo* maxpo)%mod;
		}
		else
		if ( maxno!=-1&&minpo!=-1){
			mo=(mo*modInverse( minpo,mod))%mod;
			mo=( mo* maxno)%mod;
		}
		else
		{
			mo=1;
			int j=n-1;
			while ( k-- ){
				mo=(mo*v[j].fi*( v[j].se==1?-1:1)+mod)%mod;
				j--;
			}
		}
		cout<<(mo+mod)%mod<<'\n';
	}
	else
		cout<<mo<<'\n';
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	cout.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen ("INPUT.txt" , "r" , stdin);
		freopen ("OUTPUT.txt", "w" , stdout);
	#endif
	ll t=1;
	//cin>>t;
	for ( ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
    	solve();
    }
}


Measured memory_bytes: 8452
<?php
define("MOD", 10**9+7);
list($n, $a, $b) = ints();
echo subm(subm(subm(powerm(2,$n),1), nCm($n, $a)), nCm($n, $b)) ;

//足し算
function addm($a, $b){
    return ($a + $b) % MOD;
}

//引き算
function subm($a, $b){
    return ($a + MOD - $b) % MOD;
}

//掛け算
function mulm($a, $b){
    return ($a * $b) % MOD;
}

//割り算
function divm($a, $b){
    return mulm($a, powerm($b, MOD - 2));
}

//累乗
function powerm($a, $b){
    if($b == 0)return 1;
    if($b & 1)return (powerm($a, $b>>1)**2 % MOD) * $a % MOD;
    return powerm($a, $b>>1)**2 % MOD;
}

//階乗
function factorialm($a){
    if($a == 0)return 1;
    return factorialm($a - 1) * $a % MOD;
}

//順列
function nPm($n, $m){
    if($m == 0)return 1;
    return nPm($n, $m - 1) * ($n - $m + 1) % MOD;
}

//組み合わせ
function nCm($n, $m){
    $m = min($m, $n-$m);
    return divm(nPm($n, $m), factorialm($m));
}


function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array: ";
            echo implode(" ", addIndex($val))."\n";
        }else{
            echo "array:array\n";
            if(isCleanArray($val)){
                foreach($val as $row)echo implode(" ", addIndex($row))."\n";
            }else{
                foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row))."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
function addIndex($val){
    if(!isCleanArray($val)){
        $val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);
    }
    return $val;
}
function isCleanArray($array){
    $clean = true;
    $i = 0;
    foreach($array as $k => $v){
        if($k != $i++)$clean = false;
    }
    return $clean;
}
/**
 * 座圧対象の配列を渡すと以下の値を返す
 * ・圧縮された配列
 * ・復元用のMap
 * ・圧縮用のMap
 **/
function atsu($array){
    $a = array_flip($array);
    $fuku = array_flip($a);
    sort($fuku);
    $atsu = array_flip($fuku);
    foreach($array as $i => $val)$array[$i] = $atsu[$val];
    return [$array, $fuku, $atsu];
}
//配列の最大公約数
function gcdAll($array){
    $gcd = $array[0];
    for($i = 1; $i < count($array); $i++){
        $gcd = gcd($gcd, $array[$i]);
    }
    return $gcd;
}

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

//配列の最小公倍数
function lcmAll($array){
    $lcm = $array[0];
    for($i = 1; $i < count($array); $i++){
        $lcm = lcm($lcm, $array[$i]);
    }
    return $lcm;
}

//最小公倍数
function lcm($a, $b) {
    return $a / gcd($a, $b) * $b;
}
//ビットカウント-1の数を数える
function popcount($x){
    $con = 0;
    while ($x) {
        $x &= $x-1;
        ++$con;
    }
    return $con;
}


Measured memory_bytes: 61944
#include <iostream>

using namespace std;

int main(){
  
  int N;
  int a[100001] = {};
  int out = 0; //ans
  
  cin >> N;

  for(int i = 0; i < N; i++){
	int num;
	cin >> num;
	if(num <= N){
	  a[num]++;
	}
	else{
	  out++;
	}
  }

  for(int i = 1;i <= N; i++){
	if(i <= a[i]){
	  out += a[i] - i;
	}
	else{
	  out += a[i];
	}
  }

  cout << out << "\n";
    
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(const T a, const T b){return a>=0 ? a/b : (a+1)/b-1;}
template<class T> T div_ceil(const T a, const T b){return a>=0 ? (a-1)/b+1 : a/b;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 1000010;

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) && n){
        int h[n+1], w[m+1];
        h[0] = w[0] = 0;
        rep(i, n) scanf("%d", &h[i+1]);
        rep(i, m) scanf("%d", &w[i+1]);
        partial_sum(h, h+n+1, h);
        partial_sum(w, w+m+1, w);
        vector<int> x, y;
        rep(i, n+1)For(j, i+1, n+1) x.push_back(h[j] - h[i]);
        rep(i, m+1)For(j, i+1, m+1) y.push_back(w[j] - w[i]);
        sort(y.begin(), y.end());
        lint ans = 0;
        for(int v: x){
            ans += upper_bound(y.begin(), y.end(), v) - lower_bound(y.begin(), y.end(), v);
        }
        printf("%lld\n", ans);
    }
}


Measured memory_bytes: 19852
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;

int main() {
  string s; cin >> s;
  s[3] = '8';
  cout << s << endl;
}

Measured memory_bytes: 256