akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define answer cout << ans << endl;
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
using ll=long long;

//auto mod int
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}

  mint comb(int r){//O(r)で間に合うようなrのみ使用可能
    mint x=1,y=1;
    for(int i=0;i<=r-1;i++){
      y*=*this-i;
      x*=i+1;
    }
    return y/x;
  }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

signed _main(){
  int n,a,b; cin >> n >> a >> b;
  cout << mint(2).pow(n)-1-mint(n).comb(a)-mint(n).comb(b) << endl;
  return 0;
}


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

using namespace std;

vector<int> ans;
int n,m,p;
int main(){
	while(1){
		cin >> n >> m >> p;
		if(n == 0 && m == 0 && p == 0) break;
		int prize = 0;
		int x[100];
		int sum = 0;
		for(int i = 0;i < n; i++){
			cin >> x[i];
			sum += x[i];
		}
		if(x[m - 1] == 0){
			ans.push_back(0);
		}else{
			ans.push_back(sum *(100 - p)/x[m - 1]);
		}
	}
	for(int i = 0;i < ans.size();i++){
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 3028
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

int b[1000000];

int main() {
	int lidx = 500000;
	int ridx = lidx - 1;
	bool right = true;
	int n, x;
	cin >> n;
	FOR (i, n) {
		cin >> x;
		if (right) {
			ridx++;
			b[ridx] = x;
		}
		else {
			lidx--;
			b[lidx] = x;
		}
		right ^= 1;
	}
	if (right) {
		ffor (i, lidx, ridx + 1)
			cout << b[i] << " ";
	}
	else {
		for (int i = ridx; i >= lidx; i--)
			cout << b[i] << " ";
	}
	cout << endl;
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    string T;
    cin >> T;
    rep(i, T.size()) {
        if(T[i] == '?') {
            if(i != 0) {
                if(T[i - 1] == 'P') T[i] = 'D';
                else if(i != T.size() - 1 && T[i + 1] != 'P') T[i] = 'P';
                else T[i] = 'D';
            } else {
                if(i != T.size() - 1 && T[i + 1] != 'P') T[i] = 'P';
                else T[i] = 'D';
            }
        }
    }
    cout << T << endl;
    return 0;
}


Measured memory_bytes: 3724
import math
def jud(n):
    cnt=0
    while (True):
        if (n % 2 == 0):
            n /= 2
            cnt += 1
        else:
            break
    return cnt

n = int(input())
cnt = 0
ans=1
for i in range(n):
    tmp=jud(i+1)
    if (cnt < tmp):
        cnt = tmp
        ans = i + 1
print(ans)



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

#define ssync ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
template<typename T>
using vc=vector<T>;
template<typename T, typename X>
using pr=pair<T, X>;

const ll MOD = 1e9+7;
const ld PI = 3.14159265;

ll powerWithMod(ll base, ll exponent, ll modulus = LLONG_MAX)
{
	ll result = 1;
	base %= modulus;
	while(exponent > 0)
	{
		if(exponent % 2 == 1)
			result = (result * base) % modulus;
		exponent >>= 1;
		base = (base * base) % modulus;
	}
	return result;
}

ll modInverse(ll a, ll m = MOD)
{
	return powerWithMod(a, m-2, m);
}

int n, k, x, ans;
bool a[10];

bool check(int ans)
{
	for(char& c: to_string(ans))
		if(a[c - '0'])
			return false;
	return true;
}

int main()
{
	ssync;
	cin >> n >> k;
	for(int i=0; i<k; i++)
	{
		cin >> x;
		a[x]=1;
	}
	ans = n;
	while(!check(ans))
		ans++;
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

def lcm(a,b):
    return a//gcd(a,b)*b

input()
a=list(map(int,input().split()))
b=1
for i in a:
    b=lcm(b,i)
print(b)


Measured memory_bytes: 5600
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int nNot2and4 = 0;
    int n2 = 0;
    int n4 = 0;
    for (int i = 0; i < N; i++) {
      int a = sc.nextInt();
      if (a % 4 == 0) {
        n4++;
      } else if (a % 2 == 0) {
        n2++;
      } else {
        nNot2and4++;
      }
    }

    System.out.println(n4 >= nNot2and4 + (n2 % 2) - 1 ? "Yes" : "No");
  }
}

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

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;
constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;
const long double PI = (acos(-1));
const ull MOD = 1000000007;


struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> Play(N, vector<int>(3));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 3; j++) cin >> Play[i][j];
    }
    vector<vector<ll>> dp(N, vector<ll>(3));
    dp[0][0] = Play[0][0];
    dp[0][1] = Play[0][1];
    dp[0][2] = Play[0][2];
    for(int i = 0; i < N - 1; i++){
            dp[i + 1][0] = max(dp[i][1], dp[i][2]) + Play[i + 1][0];
            dp[i + 1][1] = max(dp[i][0], dp[i][2]) + Play[i + 1][1];
            dp[i + 1][2] = max(dp[i][0], dp[i][1]) + Play[i + 1][2];
    }
    cout << max(dp[N - 1][0], max(dp[N - 1][1], dp[N - 1][2])) << endl;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
#define printvector(v,n) for(int i=1;i<=n;i++) cout<<v[i]<<" "; cout<<ln;
#define printint(v) copy(begin(v), end(v), ostream_iterator<int>(cout," "))
#define printintv(s,e) copy(s,e, ostream_iterator<int>(cout," "))
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for int64)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define ln "\n"
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define RFOR(i,b,a) for(int i=b; i>=a; i--)
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define setPresent(x,s) (s.find(x)!=s.end())
#define sqr(x) x*x
#define siz(v) int(v.size())
const double pi = 3.14159265358979323846;
typedef long long ll;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef pair<char,int> pci;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
typedef map<ll,ll> m64;
#pragma GCC optimize ("-O2")
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T> >; 
const int LM=1e5;
int a[LM+2];
v32 v;

int main()
{    
   ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
   string s;cin>>s; 
   int n=s.length();
   FOR(i,0,int(s.length())-1) a[i+1]=s[i]-'0';
   if(a[1]==0 || a[n]==1){
      cout<<"-1\n"; return 0;
   }
   FOR(i,1,n-1){
      if(a[i]!=a[n-i]){
         cout<<"-1\n";
         return 0;
      }
   }
   FOR(i,1,n){
      if(a[i]==1) v.pb(i);
   }
   int ps=1,cn=1;
   FOR(i,0,siz(v)-1){
      cn++;
      if(i!=0){
         FOR(j,1,v[i]-v[i-1]-1){
            cout<<cn++<<" "<<ps<<endl;
         }
      }
      cout<<ps<<" "<<cn<<endl; 
      ps=cn;
   }
}

Measured memory_bytes: 2504
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int a[3];
	for(int i=0; i<3 ; i++){
		cin >> a[i];
	}
	sort(a, a+3);
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
}


Measured memory_bytes: 3116
n,l = gets.chomp.split(" ").map(&:to_i)

arr = []
(1..n).each do |i|
  arr << l + i - 1
end

sum = arr.inject(:+)

min = 1000000000
result = nil
(1..n).each do |i|
  copy_arr = arr.dup
  copy_arr.delete_at(i-1)
  sum2 = copy_arr.inject(:+)
  diff = (sum2 - sum).abs
  if diff < min then
    min = diff
    result = sum2
  end
end

puts result


Measured memory_bytes: 1916
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>

using namespace std;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define all(a) (a).begin(), (a).end()
typedef long long ll;

template<typename T>
void vdeb(vector<T> &da){
    int size=da.size();
    for(int i=0;i<size;i++){
        if(i==size-1){
            cout << da[i] << endl;
        }
        else{
            cout << da[i] << ' ';
        }
    }
}

double ch(vector<vector<int>> &da,int n,int x,int y){
	vector<double> dp(n,0);
	for(int i=n-1;i>-1;i--){
		int si = da[i].size();
		if(i == x){
			si--;
		}
		rip(j,da[i].size(),0){
			if(i==x && j==y){
				continue;
			}
			dp[i]+=(double)(dp[da[i][j]]+1)/si;
		}
	}
	return dp[0];
}

int main(){
	int n,m;
	cin >> n >> m;
	vector<vector<int>> da(n,vector<int>(0));
	int s,t;
	rip(i,m,0){
		cin >> s >> t;
		s--;t--;
		da[s].push_back(t);
	}
	vector<double> dp(n,0.0);
	vector<int> memo(n);
	for(int i= n-2;i>-1;i--){
		double now = -1;
		int si=da[i].size();
		rip(j,si,0){
			dp[i]+=(double)(dp[da[i][j]]+1)/si;
			if(now < dp[da[i][j]]){
				memo[i] = j;
				now = dp[da[i][j]];
			}
		}
	}
	double ans = dp[0];
	rip(i,n-1,0){
		if(da[i].size()==1){
			continue;
		}
		ans = min(ans, ch(da, n, i, memo[i]));
	}
	printf("%.07f\n",ans);
}

Measured memory_bytes: 1408
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
m = float("INF")
num = 0
for i in range(n):
    if abs(t - h[i] * 0.006 - a) < m:
        num = i
        m = abs(t - h[i] * 0.006 - a)

print(num + 1)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
      cout << "a > b" << endl;
    else if (a < b)
      cout << "a < b" << endl;
    else if (a == b)
      cout << "a == b" << endl;    
}



Measured memory_bytes: 3092
#include <stdio.h>

int main(void) {
	int i;
    int a, b;

    scanf("%d%d", &a, &b);
    if (a < b)
    	for (i = 0; i < b; i++)
        	printf("%d", a);
    else
    	for (i = 0; i < a; i++)
        	printf("%d", b);
    
    printf("\n");

    return 0;
}


Measured memory_bytes: 128
n = int(input())
d1 = []
d2 = []
count = 0
ans = 'No'
for x in range(n):
     c, b = input().split()
     d1.append(c)
     d2.append(b)
for y in range(n):
    if d1[y] == d2[y]:
        count +=1
        if count >= 3:
            ans = 'Yes'
            break
    else:
        count = 0
print(ans)

Measured memory_bytes: 9180
def div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

n=int(input())
at=[int(i) for i in input().split()]
a=set(at)
d={}
for i,j in enumerate(a):
    t=div(j)
    for k in t:
        if k in d:
            d[k]+=1
        elif i==0 or k not in d:
            d[k]=1
ans=1
for i in d:
    x=0
    for j in at:
        if j%i: x+=1
    if x<2: ans=max(ans,i)
print(ans)


Measured memory_bytes: 63984
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		PrintWriter ou = new PrintWriter(System.out);
		int n = Integer.parseInt(sc.next());
		long yono = Long.parseLong(sc.next()) , a , aa , bb , pa;
		for(int i = 0 ; i < n - 1 ; i++){
			a = Long.parseLong(sc.next());
			aa = a;
			bb = yono;
			while(bb != 0){
				pa = aa % bb;
				aa = bb;
				bb = pa;
			}
			yono /= aa;
			yono *= a;
		}
		ou.println(yono);
		ou.flush();
    }
}

Measured memory_bytes: 35824
n, m = map(int, input().split())
 
a_set=set()
 
for index in range(m):
    a_set.add(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])


Measured memory_bytes: 11884
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vbool vector<bool>
#define umap unordered_map
#define uset unordered_set
#define frw(i, a, b) for(int i = a; i < b; i++)
#define bck(i, a, b) for(int i = a; i > b; i--)
#define fi first
#define se second
#define pow asdihagsiduh
#define pub push_back
#define in insert
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int(a.size())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define vpll vector<pll>
#define vpii vector<pii>

#define trace(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> 
void ZZ(const char* name, Arg1&& arg1){
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

vi adj[N], dp;
vbool vis;

void dfs(int x){
	vis[x] = 1;
	for(int i : adj[x]){
		if(!vis[i])	dfs(i);
		dp[x] = max(dp[x], 1 + dp[i]);
	}
}

int main(){
	ios::sync_with_stdio(0);
	int n, m; cin >> n >> m;
	dp.assign(n + 1, 0);
	vis.assign(n + 1, 0);
	frw(i, 0, m){
		int x, y; cin >> x >> y;
		adj[x].pub(y);
	}
	frw(i, 1, n + 1)
		if(!vis[i])	
			dfs(i);
	int ans = 0;
	frw(i, 1, n + 1)	ans = max(ans, dp[i]);
	cout << ans;
}

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

int main(){
  int N;
  cin >> N;
  
  switch(N % 10){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      cout << "hon" << endl;
      break;
      
    case 0:
    case 1:
    case 6:
    case 8:
      cout << "pon" << endl;
      break;
      
    case 3:
      cout << "bon" << endl;
      break;
  }
}

    
      

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back

int main() {

    ll n, m , i ,  j ;
    string s ;
    ll ans = 0 ;
    cin >> n ;
    for (i = 1 ; i<= n ; i++) {
        cin >> m ;
        if (i%2 and m%2) ans ++ ;
    }
    cout << ans  << endl ;

    return 0 ;
}


Measured memory_bytes: 3588
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

typedef pair<int, int> P;
#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort((v).begin(), (v).end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define mod 1000000007LL
#define INF 1050000000

const int maxn = 1e5 + 10;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	ll a, b;
	cin >> n >> a >> b;

	ll h[maxn];
	rep(i, n)cin >> h[i];

	ll L = 0, R = 1e9 + 7;

	while (R - L != 1)
	{
		ll mid = (L + R)/2;
		ll need = 0;
		rep(i, n)
		{
			if (a*mid < h[i]) need += mid + 1;
			else if (b*mid >= h[i]);
			else need += (h[i] - b * mid + (a - b - 1)) / (a - b);
		}
		if (need <= mid) R = mid;
		else L = mid;
	}
	Print(R);
	return 0;
	
}

Measured memory_bytes: 1024
/*
============================================================================
Name        : AtCoder3.c
Author :
Version:
Copyright: Your copyright notice
Description : Hello World in C, Ansi - style
============================================================================
*/
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>


#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define f_cin(X) scanf("%f",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long  ll;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define Yes_RTN s_cout("Yes");return 0
#define No_RTN  s_cout("No");return 0
#define YES_RTN s_cout("YES");return 0
#define NO_RTN  s_cout("NO");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);

int  _gcd(int a, int b);

int s_asorts(const void* a, const void* b);


int main(void) {
	int A, B, tmp, r;

	i_cin2(A, B);
	
	tmp = (B -1) / (A - 1);
	i_cout((B - 1) % (A - 1)?tmp+1:tmp);
	return 0;
}

long _max(long a, long b) {
	return a > b ? a : b;
}
long _min(long a, long b) {
	return a < b ? a : b;
}
//昇順
int s_asorts(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}	
int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	for (i = 0; i < n; i++) {
		i_cin(*(a + i));
	}

	return 0;
}
int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}






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

int main(){
  int n;
  cin >> n;
  string tmp;
  int c1=0,c2=0,c3=0,c4=0;
  for(int i=0;i<n;i++){
    cin >> tmp;
    if(tmp.compare("AC")==0) c1++;
    else if(tmp.compare("WA")==0) c2++;
    else if(tmp.compare("TLE")==0) c3++;
    else if(tmp.compare("RE")==0) c4++;
  }

  cout << "AC x " << c1 << endl;
  cout << "WA x " << c2 << endl;
  cout << "TLE x " << c3 << endl;
  cout << "RE x " << c4 << endl;
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp17
{
    class Program
    {
        static Tuple<int, int>[][] d;

        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            d = new Tuple<int, int>[n][];

            for (int i = 0; i < n; i++)
            {
                var ai = int.Parse(Console.ReadLine());
                d[i] = new Tuple<int, int>[ai];

                for (int j = 0; j < ai; j++)
                {
                    var xy = Console.ReadLine().Split();
                    var x = int.Parse(xy[0]);
                    var y = int.Parse(xy[1]);
                    d[i][j] = Tuple.Create(x - 1, y);
                }
            }

            var ans = 0;
            for (int x = 0; x < 1 << n; x++)
            {
                var all = 0;
                for (int i = 0; i < n; i++)
                {
                    if ((x >> i & 1) == 0) continue;

                    if (pred(x, i))
                    {
                        all++;
                    }
                    else
                    {
                        all = -1;
                        break;
                    }
                }

                ans = Math.Max(ans, all);
            }

            Console.WriteLine(ans);
        }

        static bool pred(int x, int i)
        {
            foreach (var item in d[i])
            {
                var n = item.Item1;
                var f = item.Item2;
                var g = x >> n & 1;

                if (f != g)
                {
                    return false;
                }
            }

            return true;
        }
    }
}


Measured memory_bytes: 11220
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

int check(long long n){
	int dig = 0;

	while(n > 0 ){
		n /= 10;
		dig++;
	}

	ret dig;
}


int main(){
	long long n;
	cin >> n;
	
	int ans = check(n);
	
	for(long long i = 1 ; i*i <= n ; i++ ){
		if( n % i == 0 ){
			const int tmp_ans = max(check(i),check(n/i));
			ans = min(tmp_ans , ans);
		}
	}
	P(ans);
	ret 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
const ll MOD = 1e9+7;

int main(){
  int n;
  ll ans=0;cin>>n;
  vector<int> a(n,0),ttl(n+1,0);
  REP(i,n){
    cin>>a.at(i);
    ttl.at(i+1)=(int)(((ll)ttl.at(i)+(ll)a.at(i))%MOD);
  }
  for(int i=1;i<n;i++){
    ans+=((ll)a.at(i)*(ll)ttl.at(i))%MOD;
    ans%=MOD;
  }

  cout<<ans;
}

Measured memory_bytes: 4776
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll MOD = 1000000007LL;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
template <typename Functor>
struct fix_type
{
    Functor functor;
    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const& { return functor(functor, std::forward<Args>(args)...); }
};
template <typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor) { return {std::forward<Functor>(functor)}; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) { cin >> A[i], A[i] -= (i + 1); }
    sort(A.begin(), A.end());
    const ll median = A[N / 2 ];
    ll ans = 0;
    for (int i = 0; i < N; i++) { ans += abs(A[i] - median); }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for (int i = 0; i < (n); ++i)
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin >> n;
    vector<ll> a(n),b(n);
    rep(i,n){
        cin >> a[i] >> b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(n&1){
        cout << b[n/2]-a[n/2]+1 << endl;
    }
    else{
        ll l=a[n/2-1]+a[n/2],r=b[n/2-1]+b[n/2];
        cout << r-l+1 << endl;
    }
}

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

#define     pb              push_back
#define     ll              long long
#define     rep(i,a,b)      for( i=a;i<b;++i)
#define     F               first
#define     S               second
#define     mod7            1000000007
#define     vii             vector<int>
#define     mii             map<int,int>
using namespace std;


int32_t main()
{
    int n,k;
    cin>>n>>k;
    vector<int>ar(n);
    for(int i=0;i<n;i++)
    cin>>ar[i];
    vii dp(k+1,1);
    dp[1]= 1;

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


            if(i==ar[j]) 
            {
                dp[i]=0;
                break;
            }
            else if(i>ar[j])
            {
                dp[i]=1-dp[i-ar[j]];
                if(dp[i]==0) break;
            }
        }
    }
    if(dp[k]==1)
    {
        cout<<"Second";
    }
    else
    {
        cout<<"First";
    }
    



}    

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        void solve(InputReader in, PrintWriter out) {
            char[] s1 = in.next().toCharArray();
            char[] s2 = in.next().toCharArray();
            char[] s3 = in.next().toCharArray();
            char[] ans = {s1[0], s2[1], s3[2]};
            out.println(String.valueOf(ans));
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Measured memory_bytes: 20692
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int func(int x) {
  if (x % 100 != 0) return 0;
  return func(x / 100) + 1;
}

int main() {
  int D, N;
  cin >> D >> N;
  int ans = 0;
  for (int i = 1;; i++) {
    if (func(i) == D) {
      ans++;
      if (ans == N) {
        cout << i << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3628
from networkx.utils import UnionFind
def main():
    n,m=map(int, input().split())
    uf=UnionFind()
    for i in range(n):
        _=uf[i]
    for _ in range(m):
        x,y,z=map(int, input().split())
        uf.union(x-1,y-1)
    print(len(list(uf.to_sets())))
    
    
if __name__=='__main__':
    main()

Measured memory_bytes: 103824
n, m = map(int, input().split())
h = list(map(int, input().split()))

G = [[] for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

ans = 0
for i in range(n):
    mx = 0
    for j in G[i]:
        mx = max(mx, h[j])
    if mx < h[i]:
        ans += 1

print(ans)


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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005

ll n;

int main()
{
    _FastIO;
    cin >> n;
    if(n % 2){
        cout << "0" << endl;
        return 0;
    }
    ll k = 1;
    ll ans = 0;
    while(k <= n){
        k *= 5;
        ll x = n / k;
        x /= 2;
        ans += x;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>

long long int cmpfunc (const void * a, const void * b)
{
   return ( *(long long int*)a - *(long long int*)b );
}

int main(void) {

long long int n,i,l=0,b=0,j;
scanf("%lld",&n);
long long int a[n],s[n];
for(i=0;i<n;i++)
{
    scanf("%lld",&a[i]);
}
qsort(a,n, sizeof(long long int), cmpfunc);
for(i=0;i<n;i++)
    {
        s[i] = a[n-i-1];
    }
    //temp =s[0];
   for(i=0;i<n;i++)
   {
      if(s[i]==s[i+1])
      {
          l = s[i];
          break;
      }
       
   }
   for(j=i+2;j<n;j++)
   {
      if(s[j]==s[j+1])
      {
          b = s[j];
          break;
      }
       
   }
   if(l==0||b==0)
   printf("0\n");
   else
   printf("%lld\n",l*b);

	return 0;
}



Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;

signed main(){
    int x,y;cin>>x>>y;
    cout<<(abs(x-y)<2?"Brown":"Alice")<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
string s;int n;
bool F(int x){
    int a=0,b=0;
    lol(i,n){
	if(s[i]=='I'&&x)x--,a++;
	else if(s[i]=='O'&&a)a--,b++;
	else if(s[i]!='O')b=max(0,b-1);
    }
    return (x+a+b==0);
}
int main(){
    cin>>n>>s;
    reverse(s.begin(),s.end());
    int l=0,r=n,m;
    while(l<r-1){
	m=(l+r)/2;
	if(F(m))l=m;
	else r=m;
    }
    cout<<l<<endl;
    return 0;
}



Measured memory_bytes: 3996
N, K = map(int, input().split(' '))
hate = list(map(int, input().split(' ')))
allow = set([0,1,2,3,4,5,6,7,8,9]) - set(hate)
for i in range(N, 88889):
    tmp_set = set(map(int, list(str(i))))
    if tmp_set <= allow:
        print(i)
        break

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
        	int n = scan.nextInt();
        	int sum = 2;
        	for(int i = 2;i <= n;i++){
        		sum += i;
        	}
        	System.out.println(sum);
        }
    }
}

Measured memory_bytes: 18032
#include<iostream>
using namespace std;
#define MAX 100000
typedef long long llong;

int n, k;
llong T[MAX];

int check(llong p) {
	int i=0;
	for(int j = 0; j < k; j++ ) {
		llong sum = 0;
		while( sum + T[i] <= p) {
			sum += T[i];
			i++;
			if(i == n ) return n;
		}
	}
	return i;
}

int solve() {
	llong left = 0;
	llong right = 100000 * 10000;
	llong mid; 
	while(left <= right) {
		mid = left + (right - left) / 2;
		int v = check(mid);
		if(v >= n) right = mid -1;
		else left = mid + 1;
	}
	return left;
}

main() {
	cin >> n >> k;
	for( int i = 0; i < n; i++) cin >> T[i];
	llong ans = solve();
	cout << ans << endl;
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;

int main() {

	int a, b;
	cin >> a >> b;
	int ans = 0;
	rep(i, 2) {
		if (a < b)swap(a, b);
		ans += a;
		a--;
	}
	cout << ans << endl;
}

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

#define For(i,a,b) for(int (i) = (a);(i) < (b);i++)
#define Rep(i,n) For((i),0,(n))
#define All(a) (a).begin(),(a).end()
#define sp " "
#define INF 1e18
#define INT_INF 1e9

typedef long long ll;
const ll MOD = 1000000007;
const ll MOD_9 = 998244353;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if((a+b+c) >= 22){
        cout << "bust";
    }else{
        cout << "win";
    }
}

Measured memory_bytes: 256
import sys


class Vector(object):
    def __init__(self, _from, to):
        self.x = to[0]-_from[0]
        self.y = to[1]-_from[1]

    def cross(self, other: "Vector") -> float:
        return self.x * other.y - self.y * other.x


for a in (list(map(float, l.split(","))) for l in sys.stdin):
    points = [(x, y) for x, y in zip(a[::2], a[1::2])]
    sign = {Vector(p2, p3).cross(Vector(p2, p1)) > 0
            for p1, p2, p3 in zip(points, points[1:]+points, points[2:]+points)}
    print("YES" if len(sign) == 1 else "NO")


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

typedef long long LL;

int x;
int ada[300005];

void pre(){
	for(int i=1;i<=100000;i++){
		int tmp = 0;
		int idx = -1;
		for(int j=i;tmp<=100000;j++){
			tmp+=j;
			ada[tmp]++;
			idx = j;
//			if(i>=3663) cout << tmp << endl;
		}
//		cout << i << " " << idx << endl;
	}
	return;
}

int main(){
	pre();
	scanf("%d",&x);
	LL ans = 0;
	for(int i=1;i*i<=x;i++){
		if(x%i == 0){
			int cur = i;
			int bagi = x/i;
			ans += (LL)(ada[cur])*(LL)(ada[bagi]);
			if(i*i==x) continue;
			ans += (LL)(ada[cur])*(LL)(ada[bagi]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 3992
n = int(input())
count = 0
T, X, Y = 0,0,0
for i in range(n):
    t, x, y = map(int, input().split())
    if abs(X-x)+abs(Y-y) <=abs(T-t) and t%2==(x+y)%2:
        count +=1
    T,X,Y = t,x,y
print("Yes" if count==n else "No")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a.at(i);
  sort(a.begin(),a.end());
  cout<<a.at(n-1)-a.at(0)<<endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::*;
use std::collections::*;

fn main() {
    let line1 = read_vec::<u64>();
    let line2 = read_vec::<u64>();
    let (n, k) = (line1[0], line1[1]);
    let mut queue = BinaryHeap::with_capacity(n as usize);
    for i in line2 {
        queue.push(i);
    }
    for _ in 0..k {
        let val = queue.pop().unwrap();
        queue.push(val / 2);
    }
    let result = queue.iter().fold(0, |acc, &i| acc + i );
    println!("{}", result);
}

fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line: String = String::new();
    stdin().read_line(&mut line).ok();
    line.trim().split_whitespace()
        .map(|i| i.parse().ok().unwrap()).collect()
}

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

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
	auto no = [](){ puts("-1"); exit(0); };
	int n;
	scanf("%d", &n);
	vector<long long> d(n);
	map<long long, int> mp;
	set<long long> ds;
	rep(i, n) {
		scanf("%lld", &d[i]);
		ds.insert(d[i]);
		mp[d[i]] = i;
	}
	sort(d.rbegin(), d.rend());
	UnionFind uf(n);
	vector<pair<int, int>> ans;
	rep(i, n - 1) {
		long long cur = d[i];
		int sz = uf.get(mp[cur]);
		int d = n - 2 * sz;
		long long par = cur - d;
		if (ds.count(par) == 0) {
			no();
		}
		ans.emplace_back(mp[cur], mp[par]);
		uf.unite(mp[cur], mp[par]);
	}
	vector<vector<int>> g(n);
	rep(i, n - 1) {
		int a = ans[i].first;
		int b = ans[i].second;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<long long> s(n);
	vector<int> dis(n);
	vector<int> sz(n);
	function<void (int, int)> dfs = [&](int u, int prev) {
		sz[u] = 1;
		for (auto v : g[u]) if (v != prev) {
			dis[v] = dis[u] + 1;
			dfs(v, u);
			sz[u] += sz[v];
		}
	};
	dfs(0, -1);
	rep(i, n) s[0] += dis[i];
	function<void (int, int)> dfs2 = [&](int u, int prev) {
		for (auto v : g[u]) if (v != prev) {
			s[v] = s[u] + n - sz[v] * 2;
			dfs2(v, u);
		}
	};
	dfs2(0, -1);
	sort(s.begin(), s.end());
	sort(d.begin(), d.end());
	if (s != d) {
		cout << -1 << endl;
		return 0;
	}
	for (auto it : ans) printf("%d %d\n", it.first + 1, it.second + 1);
        return 0;
}


Measured memory_bytes: 31348
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int LIS(vector<int> A){
    int N=A.size();
    vector<int> D;
    for(int i=0;i<N;i++){
        int pos=distance(D.begin(),upper_bound(D.begin(), D.end(),A[i]));
        if(pos==D.size()){
            D.push_back(A[i]);
        }else{
            D[pos]=A[i];
        }
    }
    return D.size();
}

signed main(void){
    int N;
    int a[114514];
    vector<int> A;
    cin >> N;
    REP(i,N){
        cin  >> a[i];
    }
    REP(i,N){
        A.push_back(a[N-1-i]);
    }
    int Ans=LIS(A);
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 4084
import java.util.*;
import java.io.*;

class Main {

    public static void main( String[] args ) {
        try {
	      	BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
			int n = Integer.parseInt( kb.readLine( ) );        
			ArrayDeque<Integer> dq = new ArrayDeque<Integer>( );
            String[] str;
            for( int i=0; i<n; i++ ) {
				str = kb.readLine().split( " " );
                if( 'i' == str[0].charAt( 0 ) ) {
                    dq.addFirst( Integer.parseInt( str[1] ) );
                } else if( 6 < str[0].length( ) && 'F' == str[0].charAt( 6 ) ) {
                    dq.removeFirst( );
                } else if( 6 < str[0].length( ) && 'L' == str[0].charAt( 6 ) ) {
                    dq.removeLast(  );
                } else {
                    dq.removeFirstOccurrence( Integer.parseInt( str[1] ) );
                }
            } 	
			StringBuilder output = new  StringBuilder( );
            for( Iterator itr = dq.iterator( ); itr.hasNext( ); ) {
                output.append( itr.next( ) ).append( " " );
            }
            output.deleteCharAt( output.lastIndexOf( " " ) );
            System.out.println( output );
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

Measured memory_bytes: 561100
//     自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只
// 要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也
// 能够保持自己的本色走下去。                               ——陈立杰
/*************************************
 * @contest:      ABC172.
 * @user_name:    brealid/hkxadpall/zhaoyi20/jmoo/jomoo/航空信奥/littleTortoise.
 * @time:         2020-06-27.
 * @language:     C++.
*************************************/ 

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

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

namespace baseFastio {
    template <typename Int>
    inline Int read()       
    {
        Int flag = 1;
        char c = getchar();
        while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
        if (c == '-') flag = -1, c = getchar();
        Int init = c & 15;
        while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
        return init * flag;
    }

    template <typename Int>
    inline Int read(char &c)       
    {
        Int flag = 1;
        c = getchar();
        while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
        if (c == '-') flag = -1, c = getchar();
        Int init = c & 15;
        while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
        return init * flag;
    }

    template <typename Int>
    inline void write(Int x)
    {
        if (x < 0) putchar('-'), x = ~x + 1;
        if (x > 9) write(x / 10);
        putchar((x % 10) | 48);
    }  

    template <typename Int>
    inline void write(Int x, char nextch)
    {
        write(x);
        putchar(nextch);
    }
}

struct Reader {
    char endch;
    Reader() { endch = '\0'; }
    template <typename Int>
    Reader& operator >> (Int &i) {
        i = baseFastio::read<Int>(endch);
        return *this;
    }
    template <typename Int>
    inline Int get_int() {
        return baseFastio::read<Int>();
    }
    inline char get_nxt() {
        return endch;
    }
} read;

struct Writer {
    Writer& operator << (const char *ch) {
        // char *p = ch;
        while (*ch) putchar(*(ch++));
        return *this;
    }
    Writer& operator << (const char ch) {
        putchar(ch);
        return *this;
    }
    template <typename Int>
    Writer& operator << (const Int i) {
        baseFastio::write(i);
        return *this;
    }
} write;

// #define int int64



signed main()
{
    int a;
    read >> a;
    write << (a + a * a + a * a * a) << '\n';
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n,A,B,C,D;
int main()
{
	scanf("%lld",&n);
	A=n*(n+1)/2;
	B=(n/15)*(n/15+1)/2*15;
	C=(n/3)*(n/3+1)/2*3;
	D=(n/5)*(n/5+1)/2*5;
	printf("%lld\n",A-C-D+B);
	return 0;
}


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

void solve(std::istream &ist, std::ostream &ost)
{
    /* ------- 宣言と入力 ------- */

    long long A, B, N;
    ist >> A >> B >> N;

    /* ------- 計算 ------- */
    long long  x;

    if (B == 1)
    {
        ost << "0" << endl;
        return;
    }

    if (B > N)
    {
        x = N;
    }
    else
    {
        x = B - 1;
    }

    long long ans = ((x % B) * A) / B;
    // int tmp1 = floor((double)A * x / B);
    // int tmp2 = A * floor((double)x / B);
    // int ans = tmp1 - tmp2;

    ost << ans << endl;
}

#ifndef WOMAIN
int main()
{
    solve(std::cin, std::cout);
    return 0;
}
#endif


Measured memory_bytes: 3676
#include<algorithm>
#include<iostream>
#include<map>
int main(int, char**)
{
	int num = 0;
	std::cin >> num;
	int buff = 0;
	int pre = 0;
	std::map<int, int> count;
	std::cin >> pre;
	for (int c = 0; num - 1 > c; ++c)
	{
		std::cin >> buff;
		if (pre > buff)
		{
			count[pre] -= 1;
			count[buff] += 1;
		}
		pre = buff;
	}
	count[pre] -= 1;
	count[0] += 1;
	
	int max_num = 0;
	int current_num = 0;
	for (auto itr = count.begin(); count.end() != itr; ++itr)
	{
		current_num += itr->second;
		if (max_num < current_num)
		{
			max_num = current_num;
		}
	}
	std::cout << max_num << std::endl;
}


Measured memory_bytes: 7740
import itertools
N=int(input())
P=tuple(map(int,input().split()))
Q=tuple(map(int,input().split()))

seq = range(1,N+1)
Nlist=list(itertools.permutations(seq))
for index,lists in enumerate(Nlist):
    if lists == P:
        a = index
        break

for index,lists in enumerate(Nlist):
    if lists == Q:
        b = index
        break

print(abs(a-b))

Measured memory_bytes: 8052
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long LL;
LL K, A, B;

int main(){
	cin>>K>>A>>B;
	if(A>=B||B-A==1){
		printf("%lld\n", K + 1);
		return 0;
	}
	if(K<=A){
		printf("%lld\n", K + 1);
		return 0;
	}
	LL ans = 0LL;
	K-=(A+1);
	ans=B;
	ans+=(K/2)*(B-A);
	if(K%2==1)ans++;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256