akhauriyash/Code-Regression huggingface dataset:
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)
elif x<2000:
    print(1)

Measured memory_bytes: 9080
#include <iostream>
#include <vector>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); }; } fast_ios_;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }

constexpr int MOD = 1000000007;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> S(N), T(M);
    cin >> S >> T;

    vector<unsigned int> dp1(M + 1, 1);
    for (int i = 0; i < N; i++)
    {
        for (int j = M - 1; j >= 0; j--)
        {
            if (S[i] != T[j]) dp1[j + 1] += MOD - dp1[j];
        }
        for (int j = 0; j < M; j++)
        {
            (dp1[j + 1] += dp1[j]) %= MOD;
        }
    }

    cout << dp1[M] << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 1000
#define INF 100000000
#define ff(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
typedef long long ll;
int ans,n,cnt[310],mx;
char mp[310][310];
int main()
{
    scanf("%d",&n);
    ff(i,0,n-1)
    scanf("%s",mp[i]);
    ff(i,0,n-1)
    {
        ff(j,0,n-1)
        {
            cnt[mp[i][j]]++;
            mx=max(mx,cnt[mp[i][j]]);
        }
    }
    if(mx==n*n)
        printf("%d",n*n);
    else
    {
        ff(i,0,n-1)
        {
                int flag=1;
                ff(k1,0,n-1)
                {
                    ff(k2,0,k1)
                    {
                        if(mp[(k1+i)%n][k2]!=mp[(k2+i)%n][k1])
                        {
                            flag=0;
                            break;
                        }
                    }
                    if(!flag)break;
                }
                if(flag)ans+=n;
        }
        printf("%d",ans);
    }
    return 0;
}

Measured memory_bytes: 384
k, a, b = map(int, raw_input().split())
res = k+1
if a >= b:
    print(res)
    exit()

k -= a-1
if k >= 0:res = max(res, a + (k / 2) * (b-a))
k -= 1
if k >= 0:res = max(res, a + 1 + (k / 2) * (b-a))
print res


Measured memory_bytes: 2568
#![allow(dead_code, unused_imports, non_snake_case)]

use std::io::*;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::str::FromStr;

const MOD: i32 = 1_000_000_007;

fn main() {
    let (n, x): (usize, u64) = input();
    let mut va: Vec<u64> = input();

    let mut ans: u64 = 0;
    for i in 0..n {
        if i == 0 {
            if va[0] > x {
                ans += va[0] - x;
                va[0] = x;
            }
        } else {
            if va[i - 1] + va[i] > x {
                ans += va[i - 1] + va[i] - x;
                va[i] = x - va[i - 1];
            }
        }
    }
    println!("{}", ans);
}

trait Read {
    fn read(s: &str) -> Self;
}

fn input<T: Read>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

macro_rules! read_impl {
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl Read for String {
    fn read(s: &str) -> Self {
        s.to_string()
    }
}

impl Read for Vec<char> {
    fn read(s: &str) -> Self {
        s.chars().collect()
    }
}

impl<T: Read> Read for Vec<T> {
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

impl<A: Read, B: Read, C: Read, D: Read> Read for (A, B, C, D) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]), D::read(tokens[3]))
    }
}

Measured memory_bytes: 8444
import math
from itertools import permutations
N = int(input())
coodinate = [list(map(int,input().split())) for _ in range(N)]
f_N = math.factorial(N)
SumDistance = 0
for val in permutations(coodinate):
    for i in range(len(val) - 1):
        SumDistance += ((val[i+1][0] - val[i][0]) ** 2 + (val[i+1][1] - val[i][1]) ** 2) ** (1 / 2)
print(SumDistance / math.factorial(N))

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

#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(int _##i = (t), i = (f); i <= _##i; i++)
#define uptil(f, t, i)   for(int _##i = (t), i = (f); i <  _##i; i++)
#define downto(f, t, i)  for(int _##i = (t), i = (f); i >= _##i; i--)
#define downtil(f, t, i) for(int _##i = (t), i = (f); i >  _##i; i--)
typedef long double ld;
#define long long long

#if defined(EBUG) && !defined(ONLINE_JUDGE)
    #define debug true
    #define ln << endl
#else
    #define debug false
    #define ln << '\n'
#endif
#define tb << '\t'
#define sp << ' '

const long MOD = 1e9 + 7;

signed main() { // long: 64bit
    if(!debug) {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }

    long N;
    scanf("%lld",&N);

    if(N == 2) { cout << 4 ln; return 0; }

    long p = 0, t1 = N * N, t2 = N;
    times(N-2, i) {
        long t = (N-1-i) * N + p + (N-1) * i + t1;
        t %= MOD;
        p += t2; p %= MOD;
        t2 = t1;
        t1 = t;
        if(debug) if(N < 100 || i % 100 == 0 || i == N-3) cout << p sp << t1 sp << t2 ln;
    }
    cout << t1 ln;


#if 0
int t[N];
t[N-1] = N;
//       A
t[N-2] = N * N;
//       AB
t[N-3] = (N-1) * N + t[N-2];
//       aBB         1??
t[N-4] = (N-2) * N + t[N-1] + (N-1) + t[N-3];
//       aBBB        211?     2aaa    1???
t[N-5] = (N-3) * N + t[N-1] + t[N-2] + (N-1)*2 + t[N-4]
//       aBBBB       3111?    211??    [23]aaaa  1????
t[N-6] = (N-4) * N + t[N-1] + t[N-2] + t[N-3] + (N-1)*3 + t[N-5]
//       aBBBBB      41111?   3111??   211???   [234]aaa  1?????
#endif

    return 0;
}


Measured memory_bytes: 256
r, g, b, n = [int(i) for i in input().split(" ")]
c = 0
for i in range(0, n // r + 1):
    for j in range(0, n // g + 1):
        t = n - i * r - j * g
        if t >= 0 and t % b == 0:
            c += 1
print(c)

Measured memory_bytes: 40940
n=int(input())
A=list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(A[0]-A[1])
for i in range(2,n):
  dp[i]=min(dp[i-1]+abs(A[i-1]-A[i]),dp[i-2]+abs(A[i-2]-A[i]),)
print(dp[n-1])


Measured memory_bytes: 13928
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    int h,n;
    cin >> h >> n;
    int a[101010],b[101010];
    int dp[101010];
    dp[0]=0;
    for(int i=1; i<=1e4; i++)
    {
        dp[i]=0x3f3f3f3f;
    }
    for(int i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=a[i]; j<=10000; j++)
        {
            dp[j]=min(dp[j],dp[j-a[i]]+b[i]);
        }
    }
    int mine=0x3f3f3f3f;
    for(int i=h; i<=10000; i++)
    {
        mine=min(mine,dp[i]);
    }
    printf("%d\n",mine);
}


Measured memory_bytes: 256
//Naveen Venkat
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>	
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <climits>
using namespace std;
#define FOR(index, start, end) for(int index = start; index < end; index++)
#define RFOR(index, start, end) for(int index = start; index > end; index--)
#define FOREACH(itr, b) for(auto itr = b.begin(); itr != b.end(); itr++)
#define RFOREACH(itr, b) for(auto itr = b.rbegin(); itr != b.rend(); itr++)
#define INF 1000000000
#define M 1000000007
typedef long long ll;
typedef pair<int, int> pii;

string s;

int main(void)
{
	//freopen("snukesfavoriteyakiniku.in", "r", stdin);
	//freopen("snukesfavoriteyakiniku.out", "w", stdout);
	cin >> s;
	if (s.size() > 3 && s.substr(0, 4) == "YAKI")
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	cout << "";
}

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

int main() {
  int N, M, s = 0, t = 0;
  cin >> N >> M;
  vector<int> A(N);
  for(int i = 0; i < N; i++) {
    cin >> A.at(i);
    t += A.at(i);
  }
  for(int i = 0; i < N; i++) {
    if(4*M*A.at(i)>=t)
      s++;
  }
  if(s < M)
    cout << "No" << endl;
  else
    cout << "Yes" << 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 repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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

const long long INF = 1LL << 60;

int main(){
  int sx = 0, sy = 0;
  int gx, gy, n;
  cin >> gx >> gy >> n;

  rep(i, n){
    int x, y, a;
    cin >> x >> y >> a;
    if(a == 1) chmax(sx, x);
    else if(a == 2) chmin(gx, x);
    else if(a == 3) chmax(sy, y);
    else if(a == 4) chmin(gy, y);
  }

  int w = max(gx - sx, 0);
  int h = max(gy - sy, 0);

  cout << w * h << endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

//template
typedef long long int ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v,a,b) v.begin(a),v.end(b)
#define in cin>>
#define out cout<<
#define endl <<endl
const ll INF = 10000000000000;

int main() 
{
	int N, W;
	in N >> W;
	vector<int> w(110);
	vector<int> v(110);
	rep(i, N)
	{
		in w.at(i) >> v.at(i);
	}
	vector<vector<ll>> ans(110, vector<ll>(100100 , INF));
	ans.at(0).at(0) = 0;
	rep(i, N)
	{
		rep(j, 100100)
		{
			if (j - v.at(i) >= 0)
			{
				ans.at(i + 1).at(j) = min(ans.at(i + 1).at(j), ans.at(i).at(j - v.at(i)) + w.at(i));
			}
			ans.at(i + 1).at(j) = min(ans.at(i + 1).at(j), ans.at(i).at(j));
		}
	}
	ll mi;
	rep(i, 100100)
	{
		if (ans.at(N).at(i) <= W)
		{
			mi = i;
		}
	}
	out mi endl;
}


Measured memory_bytes: 87296
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18,MOD=1e9+7;
const int iINF=1e9;
typedef struct{
    int x,y,h;
} pyramid;
int main(){
    int n,s,high,k;
    cin>>n;
    vector<pyramid>p(n);
    for(int i=0;i<n;i++){
        cin>>p[i].x>>p[i].y>>p[i].h;
        if(p[i].h!=0)s=i;
    }
    for(int i=0;i<101;i++){//x
        for(int j=0;j<101;j++){//y
            bool flag=true;
            high=p[s].h+abs(i-p[s].x)+abs(j-p[s].y);
            for(int k=0;(k<n)&&flag;k++){
                if(p[k].h!=max(high-abs(i-p[k].x)-abs(j-p[k].y),0))flag=false;
            }
            if(flag){
                cout<<i<<" "<<j<<" "<<high<<endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int N,M,L,R;
    int start,end;
    int i;
    scanf("%d %d",&N,&M);
    start=0;
    end=N+1;

    for(i=0;i<M;i++){
        scanf("%d %d",&L,&R);
        if(end-start>=-1){
            if(L>=start){
                start=L;
            }
            if(R<=end){
                end=R;
            }
        }
    }
    if(end-start>-1){
        printf("%d\n",end-start+1);   
    }else{
        printf("0\n");
    }
    return 0;
}

Measured memory_bytes: 128
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
C = [int(a) - 1 for a in input().split()]
X = [[] for i in range(N)]
head = [-1] * (N + 1)
to = [0] * (N - 1 << 1)
nxt = [0] * (N - 1 << 1)
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    nxt[i] = head[x]
    to[i] = y
    head[x] = i
    j = i + N - 1
    nxt[j] = head[y]
    to[j] = x
    head[y] = j

def EulerTour(n, i=0):
    f = lambda k: k * (k + 1) // 2
    USED = [0] * n
    ORG = [0] * n
    TMP = [0] * n
    ANS = [f(n)] * n
    
    P = [-1] * n
    ct = 0
    ET1 = [0] * n
    ET2 = [0] * n
    while i >= 0:
        e = head[i]
        if e < 0:
            ET2[i] = ct
            USED[C[i]] += 1 + TMP[i]
            if i:
                k = ET2[i] - ET1[i] + 1 - USED[C[P[i]]] + ORG[i]
                ANS[C[P[i]]] -= f(k)
                TMP[P[i]] += k
            i = P[i]
            continue
        
        j = to[e]
        if P[i] == j:
            head[i] = nxt[e]
            continue
        
        P[j] = i
        head[i] = nxt[e]
        i = j
        ORG[i] = USED[C[P[i]]]
        ct += 1
        ET1[i] = ct
    
    for i in range(n):
        ANS[i] -= f(n - USED[i])
    return ANS

print(*EulerTour(N, 0), sep = "\n")

Measured memory_bytes: 90732
#include <bits/stdc++.h>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
#define mod 1000000007

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}

int main(){
    ll n,m;
    cin >> n >> m;
    vector<int> c[n+1];
    rep(i,m){
        int a,b;
        cin >> a >> b;
        --a;
        --b;
        c[a].push_back(b);
        c[b].push_back(a);
    }
    
    vector<int> ans(n+1);
    vector<bool> flag(n+1,false);
    queue<int> que;
    que.push(0);
    flag[0]=true;
    
    
    while(que.size()){
        int p=que.front();que.pop();
        for(int i=0;i<c[p].size();i++){
            if(!flag[c[p][i]]){
                que.push(c[p][i]);
                flag[c[p][i]]=true;
                ans[c[p][i]]=p;
            }
        }
    }
    
    bool flag2=true;
    for(int i=0;i<n;i++){
        if(flag[i]==false) flag2=false;
    }
    
    if(flag2){
        cout << "Yes" <<endl;
        for(int i=1;i<n;i++){
            cout << ans[i]+1 << endl;
        }
    }else{
        cout << "No" <<endl;
    }

    return 0;
}











Measured memory_bytes: 9972
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

char tx[1006][1006];
char pt[106][106];
char qt[106][106];

int decode(char c){
	if(isupper(c)) return c-'A';
	if(islower(c)) return c-'a'+26;
	if(isdigit(c)) return c-'0'+52;
	return c=='+' ? 62 : 63;
}

void rotate(int p){
	memcpy(qt, pt, sizeof(pt));
	for(int i=0;i<p;i++)
		for(int j=0;j<p;j++)
			pt[i][j] = qt[p-j-1][i];
}

int main(){
	int w, h, p;
	while(cin >> w >> h >> p, w){
		for(int i=0;i<h;i++){
			string str; cin >> str;
			for(int j=0;j<(w+5)/6;j++){
				int tmp = decode(str[j]);
				for(int k=0;k<6;k++) tx[i][6*j+k] = ((tmp>>(5-k))&1)+'0';
			}
		}
		for(int i=0;i<p;i++){
			string str; cin >> str;
			for(int j=0;j<(p+5)/6;j++){
				int tmp = decode(str[j]);
				for(int k=0;k<6;k++) pt[i][6*j+k] = ((tmp>>(5-k))&1)+'0';
			}
		}
		if(p > w || p > h){
			cout << 0 << endl;
			continue;
		}
		vector< vector<unsigned int> > pat(8, vector<unsigned int>(p, 0));
		for(int i=0;i<4;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<p;k++){
					for(int l=0;l<p;l++){
						pat[2*i+j][k] = pat[2*i+j][k]*101+pt[k][j==0 ? l : p-1-l];
					}
				}
			}
			rotate(p);
		}
		sort(pat.begin(), pat.end());
		pat.erase(unique(pat.begin(), pat.end()), pat.end());
		unsigned int mul = 1;
		vector<int> hash(h, 0);
		for(int i=0;i<h;i++){
			for(int j=0;j<p;j++){
				hash[i] = (hash[i]*101+tx[i][j]);
				if(i==0) mul *= 101;
			}
		}
		int res = 0;
		for(int i=p;i<=w;i++){
			for(int j=0;j<pat.size();j++){
				for(int k=0;k+p-1<h;k++){
					bool flag = true;
					for(int l=0;l<p;l++){
						if(hash[k+l] != pat[j][l]){
							flag = false;
							break;
						}
					}
					if(flag) res++;
				}
			}
			if(i!=w)
				for(int j=0;j<h;j++){
					hash[j] = hash[j]*101-tx[j][i-p]*mul+tx[j][i];
				}
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 1940
#include <iostream>
#include <vector>
using namespace std;
int main() {
	char w[7][8]={"Thurs","Fri","Satur","Sun","Mon","Tues","Wednes"};
	int mon[12]={31,29,31,30,31,30,31,31,30,31,30,31};
	int m,d,i,j,s;
    vector<int> a,b;
	while (cin >> m >> d) {
		if (m==0 || d==0) break;
		a.push_back(m); b.push_back(d);
	}
	for (i=0; i<a.size(); i++) {
     s=0;
	 for (j=0;j<a[i]-1;j++) s+=mon[j];
     s=(s+b[i]-1) % 7;
     cout << w[s] << "day" << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
using System;

namespace AtCoder2020Ned
{
    class Program
    {
        static void Main(string[] args)
        {
            var money = int.Parse(Console.ReadLine());

            var fiveHundredHappiness = money / 500 * 1000;
            money %= 500;
            var fiveHappiness = money / 5 * 5;
            Console.WriteLine(fiveHundredHappiness + fiveHappiness);
            Console.Read();
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i,n) for(int i = 0;  i < n ; ++i)
#define REP(i,a,b) for(int i = a ; i <= b ; ++i)
#define s(n) scanf("%d",&n)
#define rev(i,n) for(int i = n ; i >= 0 ; --i)
#define REV(i,a,b) for(int i = a ; i >= b ; --i)
#define miN(a,b) (((a)<(b))?(a):(b))
#define sc(n) scanf("%c",&n)
#define tr(c,i) for(typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define INF 1000000000
#define pii pair<long long int,long long int>
#define pb(a) push_back(a)
typedef long long ll;
using namespace std;
void pre(){}
void solve(){
    ll n,k,d,l;cin>>n>>k;
    set<int>s;
    for(int i=0;i<k;i++){
        cin>>d;
        for(int i=0;i<d;i++){
            cin>>l;
            s.insert(l);
        }
    }
    cout<<n-s.size()<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       // cout<<"Case #"<<i+1<<" :";
       	solve();
    }   
}




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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum = 0, fg = 1;
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MAXN = (int) 1e5;

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

namespace BIT
{
	int c[MAXN * 2 + 5];

	inline void init() { memset(c, 0, sizeof c); }
	inline void add(int p, int val) { while(p <= n * 2 + 1) c[p] += val, p += p & -p; }
	inline int prefix(int p) { int res = 0; while(p) res += c[p], p -= p & -p; return res; }
}

inline LL calc(int mid)
{
	static int c[MAXN + 5];

	for(int i = 1; i <= n; ++i) c[i] = a[i] < mid ? +1 : -1;

	int res = 0;
	LL cnt = 0;
	BIT::init(), BIT::add(n + 1, +1);
	for(int i = 1; i <= n; ++i)
	{
		res += c[i];
		cnt += BIT::prefix(res - 1 + n + 1);
		BIT::add(res + n + 1, +1);
	}
	return cnt;
}

inline void solve()
{
	int l = 1, r = (int) 1e9;
	while(l < r)
	{
		int mid = (l + r + 1) >> 1;
		if(calc(mid) <= (LL) n * (n + 1) / 4) l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l);
}

int main()
{
//#ifndef ONLINE_JUDGE
//	freopen("D.in", "r", stdin);
//	freopen("D.out", "w", stdout);
//#endif

	input();
	solve();

	return 0;
}



Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}

typedef long long ll;
typedef pair<ll, ll> P;

ll f(ll x)
{
  ll ret = 0;
  REP(i, 50) {
    // i桁目の周期は2^(i+1).
    // 0,...xの(x + 1)個の数字の中で周期はいくつ現れたか
    ll T = (x + 1) / (1LL << (i + 1));
    ll cnt = T * (1LL << i);
    // 端数の計算. 2^i個の0が連続し,以降1が連続する
    // 従って, 端数の位置から2^iを引けば1の個数が出る.
    // 終了位置が0の場合値は負になるはず
    cnt += max(0LL, ((x + 1) % (1LL << (i + 1))) - (1LL << i));
    ret += (cnt % 2) * (1LL << i);
  }
  return ret;
}

int main()
{
  ll A, B;
  cin >> A >> B;
  cout << (f(A - 1) ^ f(B)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    ll a = x*360/gcd(x,360);
    PRINT(a/x);
}


Measured memory_bytes: 3568
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 55
#define M 2005
int a,b;
int main()
{
    scanf("%d %d",&a,&b);
    printf("%d\n",max(a+b,max(a-b,a*b)));
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void print_YES_NO(bool answer){cout<<(answer?"YES":"NO")<<endl;}
void print_Yes_No(bool answer){cout<<(answer?"Yes":"No")<<endl;}
void print_POSSIBLE_IMPOSSIBLE(bool answer){cout<<(answer?"POSSIBLE":"IMPOSSIBLE")<<endl;}

char ca[200005];

int main(){
	int n;
	int a,b,c,d;
	int i,j,k;
	bool s=true;
	cin>>n>>a>>b>>c>>d;
	cin>>ca;
	a--,b--,c--,d--;
	for(i=a;i<max(c,d);i++){
		if(ca[i]=='#' && ca[i+1]=='#')s=false;
	}
	if(c>d){
		bool flag=false;
		for(i=b;i<=d;i++){
			if(ca[i-1]=='.' && ca[i]=='.' && ca[i+1]=='.')flag=true;
		}
		if(!flag)s=false;
	}
	print_Yes_No(s);
}
	


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
    int tmp,X,Y,Z;
    
    scanf("%d",&X);
    scanf("%d",&Y);
    scanf("%d",&Z);

    tmp=X;
    X=Y;
    Y=tmp;

    tmp=X;
    X=Z;
    Z=tmp;

    printf("%d %d %d\n",X,Y,Z);

    return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int infI=1e9+5;
const long long infL=1e16;
const int MOD=1e9+7;
const int MAX=2e5+5;

#define mp make_pair
#define in &
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define pll pair<ll,ll>
#define vvl vector<vector<ll> >
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define eb emplace_back
#define forn(i,a,b) for(ll i=a;i<b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define popb pop_back()
#define se second
#define fi first
#define test(t) int t;cin>>t;while(t--)
#define debug(x) cerr<<"=>"<<#x<<" = "<<x<<endl

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    if(b==1){
        return a;
    }
    ll temp=power(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2){
        temp=(temp*a)%MOD;
    }
    return temp;
}

//only use if mod is prime
ll mod_inv(ll a,ll mod){
    a%=mod;
    return power(a,mod-2);
}

void extended_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    ll x1,y1;
    extended_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return;
}

//TLE can also occur if vectors are not passed by reference
//priority_queue implements max heap by default

int main(){
    fastio;
    int n;
    cin>>n;
    vl a(n);
    for(auto &x:a){
        cin>>x;
    }
    ll ans = 1;
    map<ll,ll> m;
    m[-1]=3;
    for(auto x:a){
        ans = (ans * m[x-1])%MOD;
        m[x]++;
        m[x-1]--;
    }
    cout<<ans;
    return 0;
}

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

 int my_sum(int n){
  int sum = 0;
  while(n > 0){
    sum += n%10;
    n /= 10;
  }
  return sum;
}

int main(){
  int N;
  cin >> N;
  int min = my_sum(1) + my_sum(N-1);
  for (int i = 1; i < N; i++){
    int sum = my_sum(i) + my_sum(N-i);
    if(sum < min)
      min = sum;
  }
  
  cout << min << endl;
  return 0;
}



Measured memory_bytes: 256
// B - ss
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define irp(i,s,e) for(int i=(s);i>(e);--i)

int main(){
	string S; cin>>S;
	int N = S.size();

	// for(int d=1; d<N-1; ++d){//number of del char
	rp(d, 1, N-1){//number of del char
		int n = N - d;
		if(n%2) continue; //n: odd
		int len = n/2;//len: half length

		int f;
		for(f=0; f<len; ++f) if(S[f] != S[len + f]) break;//fore half != back half -> break
		if(f < len) continue;//fore half != back half
		cout<< n <<endl;
		return 0;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n-1; i >= 0; i--)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 1e9+7;
const int INF = 1e9;
const int MAX = 10;

struct edge {int to, cost;}; // 辺
vector<edge> graph[MAX]; // 隣接リスト
bool visited[MAX]; // 訪問状況

void dfs(int s, int i, int n, int &cnt) { // 始点, 今の深さ、頂点の数、パスの数
    if (i == n) {
        cnt++;
        return;
    }
    visited[s] = true;
    for (edge e : graph[s]) {
        if (not visited[e.to]) {
            dfs(e.to, i+1, n, cnt);
        }
    }
    visited[s] = false;
}

int main() {
    // input
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back({v, 0});
        graph[v].push_back({u, 0});
    }
    // solve
    int cnt = 0;
    dfs(0, 1, n, cnt);
    // output
    cout << cnt << endl;
}

Measured memory_bytes: 3620
k,a,b=map(int,input().split())
ans=0
if a+2>=b:
	print(1+k)
	exit()
else:
	if a-1>=k:
		print(1+k)
		exit()
	else:
		k=k-a+1
		print((k//2)*(b-a)+k%2+a)

Measured memory_bytes: 2940
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():

    s = input()
    ans = 0
    now = 0
    isATCG = False
    for i in range(len(s)):
        if s[i] in ["A", "G", "C", "T"]:
           isATCG = True

        if isATCG == False:
            now = 0
        else:
            now += 1
            ans = max(now,ans)

        isATCG = False

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 13572
fun main() = Thread(null, ::abc170a, "(^o^)", 128 * 1024 * 1024).apply { start() }.join()

@OptIn(ExperimentalStdlibApi::class)
fun abc170a() {
    val line = readLine()!!.split(' ').map { it.toInt() }

    val answer = line.indexOf(0) + 1

    println(answer)
}


Measured memory_bytes: 36740
def f(c):
    """
    入力に対する勝ち手を出力
    """
    if c=="r":
        return "p"
    elif c=="s":
        return "r"
    else:
        return "s"

def main():
    """
    まずは全て勝つ組み合わせを作って、合計ポイントを求める。
    iを0からN-Kまで変化させ、T(i)=T(k+i)となる時、
    T(k+i)をT(i)、T(i+2K)と異なる手に変更する。
    ※T(i)を変更すると、T(i)=T(i+k)=T(i+2K)=...=と連続した時に、
    全て変更されてスコアが最大にならない。
    T(k+i)は勝ちから"あいこまたは負け"に変化するので、合計ポイントから差っ引く。
    """

    #input
    N,K=map(int,input().strip().split())
    R,S,P=map(int,input().strip().split())
    T=list(input())
    
    win_T=list(map(lambda x:f(x),T))
    point={"r":R,"s":S,"p":P}
    score=sum([point[win_T[n]] for n in range(N)])
    for i in range(N-K):
        l=["r","s","p"]
        if win_T[i]==win_T[i+K]:
            score-=point[win_T[i+K]]
            l.remove(win_T[i])
            if i<=N-2*K-1 and win_T[i]!=win_T[i+2*K]:
                l.remove(win_T[i+2*K])
            win_T[i+K]=l[0]
    return score

if __name__=="__main__":
    print(main())

Measured memory_bytes: 5560
/*
********************
Author : Sahil Kundu
********************
*/
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define mod 1000000007
#define pb(i) push_back(i)
#define pp() pop_back()
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mk(l,r) make_pair(l,r)
#define all(vc) vc.begin(),vc.end()
#define bg(vc) vc.begin()
#define ed(vc) vc.end()
#define ms(i,j) memset(i,j,sizeof i)
#define w(t) while(t--)
const ll MAX=1e5+5;
const ll INF=2e18;
bool isprime[MAX];
vector<ll> vc;
void init()
{
    ms(isprime,true);
    isprime[1]=false;
    for(ll i=2;i*i<=MAX;i++)
    {
        if(isprime[i])
        {
            for(ll j=i*i;j<=MAX;j+=i)
                isprime[j]=false;
        }
    }
    for(ll i=2;i<=MAX;i++)
        if(isprime[i])
        vc.pb(i);
}
ll power(ll a,ll b)
{
    if(!b)return 1;
    ll res=power(a,b/2);
    res=res*res%mod;
    if(b%2)
        return res*a%mod;
    else return res%mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin>>t;
    //init();
    w(t)
    {
     	ll n;
        cin>>n;
        map<pair<ll,ll>,ll>mp;
        ll cnt=0;
        for(int i=0;i<n;i++)
        {
            ll a,b;
            cin>>a>>b;
            if(!a and !b)
            {
                cnt++;
                continue;
            }
            ll g=__gcd(a,b);
            a=a/g;
            b=b/g;
            if(a<0)
            {
                a=-a;
                b=-b;
            }
            if(a==0)
            {
                b=1;
            }
            mp[{a,b}]++;
        }
        ll ans=1;
        for(auto all: mp)
        {
            ll a=all.f.f,b=all.f.s;
            ll aa=-b;
            ll bb=a;
            if(aa<0)
            {
                aa=-aa;
                bb=-bb;
            }
            if(!aa)
            {
                bb=1;
            }
            if(mp.find({aa,bb})!=ed(mp))
            {
                ll sd=mp[{aa,bb}];
                ll m=all.s;
                (ans*=(power(2,sd)+power(2,m)-1)%mod)%=mod;
                mp.erase({aa,bb});
            }
            else 
            {
                (ans*=(power(2,all.s)%mod))%=mod;
            }
        }
        (ans+=(cnt+mod)%mod)%=mod;
        cout<<(ans-1+mod)%mod<<endl;
    }
}
/*
ll msb(ll x)
{
	ll k=(ll)log2(x);
	return (ll)(pow(2,k));
}
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}*/

Measured memory_bytes: 16080
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pb push_back

# define inOut(a,b) freopen(a,"r",stdin);freopen(b,"w",stdout);
# define RESET(a) memset(a,0,sizeof(a))
# define MEMO(a) memset(a,-1,sizeof(a))
# define DEBUG puts("Debug-Has-Come-Until-Here")


typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main(){
	cin.tie(NULL);

	double x1, x2, x3, y1, y2, y3;
	double a,b,c,d,e,f;
	double x,y;
	int dummy;
	
	scanf("%d", &dummy);
	while(scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3) != EOF){
		a = -2*x1 + 2*x2;
		b = -2*y1 + 2*y2;
		c = (x2*x2 - x1*x1) + (y2*y2 - y1*y1);
		d = -2*x2 + 2*x3;
		e = -2*y2 + 2*y3;
		f = (x3*x3 - x2*x2) + (y3*y3-y2*y2);
		
		x = (c*e - b*f)/(a*e-b*d);
		y = (c*d - a*f)/(b*d-e*a);
		printf("%.3lf %.3lf %.3lf\n", x, y, sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)));
	}

	return 0;
}

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

#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"

#define ll long long
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"

#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007

typedef vector<ll> vl;
typedef vector< vl > vvl;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;


int main() {

	// Use ctrl+shift+b ( second option )
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	ll n;
	cin>>n;

	ll ans=0;
	for(ll i=1;i<n;i++){
		ans += (n-1)/i;
	}

	cout<<ans<<nl;


	return 0;
}


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

int main(){
  unsigned long long n,k;cin >> n >> k;
  unsigned long long a[n];
  for (unsigned long long i=0;i<n;i++){
    cin >> a[i];
  }
  if (n <= k){
    cout << 0 << endl;
    return 0;
  }
  sort(a, a+n);
  unsigned long long s=0;
  for (unsigned long long i=0;i<n-k;i++){
    s += a[i];
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int MAX=10000;

int main(){
	int N;
	cin>>N;
	
	if(N==1)cout<<"Hello World";
	else{
		int A,B;
		cin>>A>>B;
		cout<<A+B;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=1;i<=2;i++)
	{
		if(a<=b)
    	{
        	cout<<a;
        	break;
    	}
    	if(a>b)
    	{
        	cout<<a-1;
        	break;
    	}
	}
    return 0;
}

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

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

using namespace std;

#define int 		long long
#define endl 		"\n"
#define mod 		1000000007
#define inf 		1e12
#define IOS 		ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)


int32_t main() {

	IOS;

	string s;
	cin >> s;

	int sum = 0;

	for (char c : s) {
		sum += c - '0';
		if (sum >= 9)
			sum -= 9;
	}

	if (!sum)
		cout << "Yes";
	else
		cout << "No";

	return 0;

}

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

using namespace std;

int main() {

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

	int n, x, t;
	cin >> n >> x >> t;
	
	int ans = ceil((1.0*n)/x)*t;
	cout << ans << '\n';
	return 0;
}

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

int main() {
    //入力
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i, n) {
        cin >> s[i];
    }
    int m;
    cin >> m;
    vector<string> t(m);
    rep(i, m) {
        cin >> t[i];
    }
    int mx = max(n, m);
    vector<string>st(mx);
    vector<int>cnt(mx);
    rep(i, n) {
        rep(j, mx) {
            if (st[j] == s[i]) {
                ++cnt[j];
            }
            else if (st[j]=="") {
                st[j] = s[i];
                ++cnt[j];
                break;
            }
        }
    }
    rep(i, m) {
        rep(j, mx) {
            if (st[j] == t[i]) {
                --cnt[j];
            }
            else if (st[j] == "") {
                st[j] = t[i];
                --cnt[j];
                break;
            }
        }
    }
    int ans = 0;
    rep(i, mx) {
        ans = max(ans, cnt[i]);
    }
    if (ans < 0) ans = 0;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
/**
 * SwappingTwoNumbers.cpp
 * Create:20180419
 * Description:複数の２組の数字を小さい順に並べ、それぞれ出力する。
 */
#include <iostream>
#include <vector>

class Number{
private:
  int x;
  int y;
public:
  /**
   * コンストラクタ
   * @param x 数値１
   * @param y 数値２
   */
  Number(int x, int y){
    this->x = x;
    this->y = y;
  }

  /**
   * 交換
   */
  void swap(){
    if (x > y) {
      int tmp = x;
      x = y;
      y = tmp;
    }
  }

  /**
   * ゲッター　X
   */
  int get_x(){
    return x;
  }

  /**
   * ゲッター　Y
   */
  int get_y(){
    return y;
  }

};

int main(int argc, char* argv[]){
  std::vector<Number> vec;
  int x, y;

  while (true){
    std::cin >> x >> y;
    if (x == 0 && y == 0){
      break;
    }
    Number n = Number(x, y);
    vec.push_back(n);
  }

  for(Number n : vec){
    n.swap();
    std::cout << n.get_x() << " " << n.get_y() << std::endl;
  }

  return 0;
}


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

static class Program
{
    static void Main()
    {
        var nm = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
        var (n, m) = (nm[0], nm[1]);
        var friendPairs = Enumerable.Range(1, m)
            .Select((i) => Console.ReadLine().Split(" ").Select(s => int.Parse(s) - 1).ToArray());

        var unionFind = new UnionFind(n);
        foreach (var friendPair in friendPairs)
        {
            unionFind.Unite(friendPair[0], friendPair[1]);
        }

        var answer = Enumerable.Range(0, n).Max(i => unionFind.Size(i));

        Console.WriteLine(answer);
    }
}

public class UnionFind
{
    public int[] Parent { get; set; }
    public UnionFind(int n)
    {
        Parent = Enumerable.Repeat(-1, n).ToArray();
    }

    public int Root(int x)
    {
        if (Parent[x] < 0)
        {
            return x;
        }

        Parent[x] = Root(Parent[x]);

        return Parent[x];
    }

    public void Unite(int x, int y)
    {
        if (!Same(x, y))
        {
            Parent[Root(y)] += Parent[Root(x)];
            Parent[Root(x)] = Root(y);
        }
    }

    public bool Same(int x, int y)
    {
        return Root(x) == Root(y);
    }

    public int Size(int x)
    {
        return -Parent[Root(x)];
    }
}

Measured memory_bytes: 56808
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();

        String input = scanner.next();
        String[] input_array = input.split("");

        int topping_count = 0;

        for(int i=0;i<input_array.length;i++) {
        	if(input_array[i].equals("o")) {
        		topping_count++;
        	}
        }
        System.out.println(700+(100*topping_count));

    }

    private class MyScanner {
        String[] s;
        int i;
        BufferedReader br;
        String reg = " ";
        MyScanner () {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public String next() {
            try {
                if (i < s.length) return s[i++];
                String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0);
                i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}

Measured memory_bytes: 21204
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

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

#define MOD 1000000007

void solve(int test_case) {//228
	int n;
	cin>>n;
	unordered_map<int,int> a,b;
	bool flag = true;
	REP(i,1,n) {
		int val;
		cin>>val;
		if(flag)a[val]++;
		else b[val]++;
		flag=!flag;
	}
	int a1=0,a1v=0,a2=0;
	int b1=0,b1v=0,b2=0;
	for(auto p:a) {
		if(p.S>=a1) {
			//cerr<<p.F<<" "<<p.S<<" ";
			a2=max(a2,a1);
			a1=p.S;
			a1v=p.F;
		} else {
			a2=max(a2,p.S);
		}
	}
	for(auto p:b) {
		if(p.S>=b1) {
			//cerr<<p.F<<" "<<p.S<<" ";
			b2=max(b1,b2);
			b1=p.S;
			b1v=p.F;
		} else {
			b2=max(b2,p.S);
		}
	}
	if(a1v==b1v) {
		//cerr<<a1<<" "<<b1<<" "<<a1v<<" "<<b1v;
		cout<<min(max(0,n-b1-a2),max(0,n-a1-b2));
	} else {
		cout<<n-a1-b1;
	}
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 7236
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <set>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 999999999
#define MINF -999999999
#define ALL(n) n.begin(),n.end()

int main() {
	int n, m,j[110000],ans;
	vector<int> s;
	cin >> n >> m;
	ans = n;
	cin >> j[0];
	REPO(i, n - 1) {
		cin >> j[i];
		s.push_back(j[i] - j[i - 1]);
	}
	sort(ALL(s));
	REP(i, n - m) {
		ans += s[i] - 1;
	}
	cout << ans << endl;
}




Measured memory_bytes: 3948
class Node():
    "node of the tree structure"
    def __init__(self, parent = -1, left = -1, right = -1):
        self.parent = parent
        self.left = left
        self.right = right
def preParse(u):
    if u == -1:
        return
    list_preParse.append(u)
    preParse(node_list[u].left)
    preParse(node_list[u].right)

def inParse(u):
    if u == -1:
        return
    inParse(node_list[u].left)
    list_inParse.append(u)
    inParse(node_list[u].right)

def postParse(u):
    if u == -1:
        return
    postParse(node_list[u].left)
    postParse(node_list[u].right)
    list_postParse.append(u)

def returnRoot(u):
    while node_list[u].parent != -1:
        u = node_list[u].parent
    return u

list_preParse = []
list_inParse = []
list_postParse = []
n = int(input())
node_list = []
for i in range(n):
    node = Node()
    node_list.append(node)

for i in range(n):
    a,b,c = map(int, input().split())
    node_list[a].left = b
    node_list[a].right = c
    if b != -1:
        node_list[b].parent = a
    if c != -1:
        node_list[c].parent = a

print("Preorder")
preParse(returnRoot(0))
for i in range(n):
    list_preParse[i] = str(list_preParse[i])
print(" " + " ".join(list_preParse))

print("Inorder")
inParse(returnRoot(0))
for i in range(n):
    list_inParse[i] = str(list_inParse[i])
print(" " + " ".join(list_inParse))
print("Postorder")
postParse(returnRoot(0))
for i in range(n):
    list_postParse[i] = str(list_postParse[i])
print(" " + " ".join(list_postParse))



Measured memory_bytes: 5616
k = int(input())
ls = [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(ls[k-1])


Measured memory_bytes: 2940