akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fup(i,a,b) for(int i=a;i<=b;++i)
#define fdw(i,a,b) for(int i=a;i>=b;--i)
#define sync ios::sync_with_stdio(false);cin.tie(0)
#define cl(a) memset(a,0,sizeof(a))
#define gcd __gcd
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll ksm(ll a,ll b,ll mod){ll ans=1;a%=mod;for(;b;b>>=1){if(b&1) ans=ans*a%mod;a=a*a%mod;}return ans;}
//ll oula(ll n){ ll res=n;for(ll i=2;i*i<=n;i++){if(n%i==0){ res=res-res/i;while(n%i==0) n/=i;}}if(n>1) res=res-res/n;return res;}
//bool MRT(ll x){if(x==2)return true;fup(i,1,50){ll now=rand()%(x-2)+2;if(ksm(now,x-1,x)!=1)return false;}return true;}
//void shai(int n)fup(i,2,n){if(isprime[i]){v.push_back(i);for(int j=2*i;j<=10000;j+=i)isprime[j]=0;}}//"埃氏筛筛选素数"
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double eps=1e-7;
const int N=3e5+10;
int a[110];
ll plzh(ll n,ll m)
{
    ll ans=1;
    ll ls=m;
    while(ls)
    {
        ans=(ans%mod*n%mod)%mod;
        n--;
        ls--;
    }
    return ans;
}
int main()
{
//    freopen("D:\\untitled3\\in","r",stdin);
    sync;
    ll n,a,b;
    cin>>n>>a>>b;
    ll ans=0,ls=0;
    ans=(ksm(2,n,mod)-1+mod)%mod;
    ls=(plzh(n,a)%mod*ksm(plzh(a,a),mod-2,mod)%mod)%mod;
    ans=(ans-ls+mod)%mod;
    ls=(plzh(n,b)%mod*ksm(plzh(b,b),mod-2,mod)%mod)%mod;
    ans=(ans-ls+mod)%mod;
    cout<<ans<<endl;
    return 0;
}



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

int main(){
int n,d,x;
cin>>n>>d>>x;
vector<int>a(n);
for(int i=0;i<n;i++){
int t;
cin>>t;
x+=(d-1)/t;
}
x+=n;
cout<<x<<endl;
}

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

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

#define ll long long

int main(){
    char s;

    for(int i=0; i < 19; ++i){
        cin >> s;
        if(s==',')
            cout << ' ';
        else
            cout << s;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define mod 1000000007
#define M 1000000
using namespace std;

ll r[100002],g[100002],c[100002];

void answer(){
    ll n,m,ans1=0,k,x,y,z;
    cin>>n>>m>>x>>y>>z;
    std::vector<ll> v;
    for(int i=0;i<x;i++) cin>>r[i];
    for(int i=0;i<y;i++) cin>>g[i];
    for(int i=0;i<z;i++) cin>>c[i];
    sort(r,r+x);
    sort(g,g+y);
    sort(c,c+z);
    for(int i=0;i<n;i++){
        v.pb(r[x-i-1]);
    }
    for(int i=0;i<m;i++){
        v.pb(g[y-i-1]);
    }
    ll f=-1,ans=0;
    sort(v.begin(),v.end());
    for(int i=0;i<z;i++){
        if(i<v.size() && c[z-i-1]>v[i]) ans+=c[z-i-1];
        else{ f=i; break;}
    }
    if(f==-1) f = z;
    for(int i=f;i<v.size();i++) ans+=v[i];
    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int q;
    //cin>>q; while(q--)
        answer();
    return 0;
}

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

using namespace std;

int main() {
    int n , l; cin>>n>>l;
    vector<string>v(n);
    for(string& s : v)cin>>s;
    sort(v.begin(), v.end());
    string ans = "";
    for(string& s : v)ans += s;
    cout<<ans<<"\n";
}

Measured memory_bytes: 256
#include<stdio.h>
long long cnt=0,i,n,tmp;
long long arr[10000010]={0};
int main()
{
  	scanf("%lld",&n);
  	for(i=1;i<=n;i++)
    {
      	if(cnt<n)
          cnt=cnt+i,tmp=i;
    	else
          	break;
    }
  	for(i=tmp;i>=1;i--)
    {
      	if(n-i>=0)
        {
        	arr[i]=1;
        	n=n-i;
        }
    }
  	for(i=1;i<=tmp;i++)
    {
      	if(arr[i]==1)
      		printf("%lld\n",i);
    }
  	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		if(str.contains("7")){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 26960
N = int(input())
P = [int(_) for _ in input().split()]

ans = 0
for i in range(N-1):
    if P[i] == i+1:
        P[i], P[i+1] = P[i+1], P[i]
        ans += 1
if P[-1] == N:
    P[-2], P[-1] = P[-2], P[-1]
    ans += 1
print(ans)


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

   typedef long long ll;
   typedef pair<ll, ll> Pii;
   typedef vector<ll> Vi;
   typedef vector<Vi> VVi;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define RSORT(x) sort((x).rbegin(), (x).rend()
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   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; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}
   ll pow(ll a, ll b, ll m){if (b == 0) return 1; else if (b % 2 == 0) return (pow(a * a, b / 2, m) % m); else return (pow(a * a, b / 2) * a) % m;}


   ll dx[4]={1,0,-1,0};
   ll dy[4]={0,1,0,-1};

ll A, B, C;
int main(){
  cin >> A >>B >> C;
  cout << B + min(A + B + 1, C) << endl;
}


Measured memory_bytes: 764
#include<stdio.h>

int gcd(int, int);

int main(){
  int x, y, i;

  scanf("%d%d",&x,&y);
  if(x > y){
    i = x;
    x = y;
    y = i;
  }
  printf("%d\n",gcd(x, y));
  return 0;
}
  
int gcd(int x, int y){
  int r;
  while(y > 0){
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

Measured memory_bytes: 592
N = gets.to_i
xs, ys, hs = [], [], []
N.times do |i|
    xs[i], ys[i], hs[i] = gets.split.map(&:to_i)
end

(0..100).each do |x|
  (0..100).each do |y|
    h = nil
    hmax = 10**10
    success = true
    N.times do |i|
      dist =(xs[i] - x).abs + (ys[i] - y).abs
      if hs[i] == 0
        hmax = dist if hmax > dist
      else
        hc = hs[i] + dist
        if h && h != hc
          success = false
          break
        else
          h = hc
        end
      end
    end
    if success && h <= hmax
        puts [x, y, h].join(' ')
        exit
    end
  end
end

Measured memory_bytes: 1788
#include <stdio.h>
int main()
{
  int n,i,j,array[200000],maxv,minv;

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%d",&array[i]);
    }

  maxv=array[1]-array[0];
  minv=array[0];

  for(j=1;j<n;j++)
    {
      if(maxv < array[j]-minv)
	{
	  maxv=array[j]-minv;
	}
      if(minv > array[j])
	{
	  minv=array[j];
	}
    }

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

  return 0;
}

Measured memory_bytes: 1376
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())

// code
// ------------------------------------------------
int main() {

  int ans = 0;
  string s;
  cin >> s;

  rep(i,4)
  {
    if(s[i] == '+')
    {
      ans++;
    }
    else
    {
      ans--;
    }
  }

  cout << ans;

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

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

using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
using ll = long long;

vector<int> ans;
void solve(int n,int m){
    string ans(n,'#');
    rep(i,m){
        char c;
        cin>>c;
        if(c=='A'){
            int idx=0;
            while(ans[idx]!='#')++idx;
            ans[idx]='A';
        }
        else if(c=='B'){
            int idx = n-1;
            bool ok=false;
            while(1){
                if(ans[idx]!='#'){
                    --idx;
                    continue;
                }
                if(idx>0&&ans[idx-1]=='A'){
                    --idx;
                    continue;  
                }
                if(idx<n-1&&ans[idx+1]=='A'){
                    --idx;
                    continue;  
                }
                ans[idx]='B';
                ok=true;
                break;
            }
            if(!ok){
                int idx=0;
                while(ans[idx]!='#')++idx;
                ans[idx]='A';
            }
        }

        else if(c=='C'){
            if(i==0){
                ans[n/2]='C';
            }
            else {
                int idx=0;
                while(1){
                    if(ans[idx]=='#'){
                        ++idx;
                        continue;
                    }
                    if(idx<n-1&&ans[idx+1]=='#'){
                        ans[idx+1]='C';
                        break;
                    }
                    if(idx>0&&ans[idx-1]=='#'){
                        ans[idx-1]='C';
                        break;
                    }
                    ++idx;
                }
            }
        }
        else {
            if(i==0){
                ans[0]='D';
                continue;
            }
            vector<int> dist(n,1000);
            rep(k,n){
                if(ans[k]!='#'){
                    rep(j,n)dist[j]=min(dist[j],abs(k-j));
                }
            }
            int ma = -1, idx = -1;
            rep(j,n){
                if(dist[j]>ma){
                    ma=dist[j];
                    idx = j;
                }
            }
            ans[idx]='D';
        }
    }
    cout<<ans<<endl;
}

int main(){
    int n,m;
    while(cin>>n>>m,n!=0)solve(n,m);
}


Measured memory_bytes: 2996
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;


map<pair<int, int>, int> cnt;

int main() {
    long long H, W, N, a, b;
    vector<long long> ans(10, 0);
    cin >> H >> W >> N;

    long long sum = (H-2)*(W-2);
    
    for(int i = 0; i < N; i++) {
        cin >> a >> b;
        a--, b--;
        for(int i = -2; i <= 0; i++) {
            for(int j = -2; j <= 0; j++) {
                if(i + a >= 0 and j + b >= 0 and i + a < H-2 and j + b < W-2) {
                    cnt[make_pair(i+a, j+b)]++;
                }
            }
        }
    }

    for(auto i = cnt.begin(); i != cnt.end(); i++) {
        ans[i->second]++;
        sum--;
//        cout << i->first.first << ',' << i->first.second << ':' << i->second << endl;
    }
    ans[0] = sum;
    for(auto &i : ans) {
        cout << i << endl;
    }
}

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

int n, q;
vector<int> A(20);
vector<int> m(200);

int main(){

    cin >> n;
    for (int i=0; i<n; i++){
        cin >> A.at(i);
    }
    cin >> q;
    for (int i=0; i<q; i++){
        cin >> m.at(i);
    }

    int sum = 0;
    vector<string> ans(200, "no");
    for (int i=0; i<(1 << n); i++){
        bitset<20> used(i);

        for (int j=0; j<n; j++){
            if (used.test(j)){
                sum += A.at(j);
            }
        }
        /*
        cout << "i = " << i << endl;
        cout << "sum = " << sum << endl;
        */
        for (int k=0; k<q; k++){
            if (m.at(k) == sum){
                ans.at(k) = "yes";
            }
        }
        sum = 0;
    }

    for (int i=0; i<q; i++){
        cout << ans.at(i) << endl;
    }
    return 0;
}



Measured memory_bytes: 3192
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int h,w,mas=0;
    cin >> h >> w;
    char a;
    int p[h+2][w+2];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin >> a;
            if(a=='#') mas++;
            p[i][j]=(a=='.'?0:1);
        }
    }
    for(int i=0;i<=h+1;i++){
        p[i][0]=1;
        p[i][w+1]=1;
    }
    for(int j=1;j<=w+1;j++){
        p[0][j]=1;
        p[h+1][j]=1;
    }
    queue<pair<int,int>> q;
    q.push(make_pair(1,1));
    int cost[h+2][w+2];
    for(int i=0;i<h+2;i++)
        for(int j=0;j<w+2;j++)
            cost[i][j]=10000000;
    cost[1][1]=0;
    int x,y;
    while(!q.empty()){
        x=q.front().first;
        y=q.front().second;
        if(p[x-1][y]==0)
            if(cost[x-1][y]>cost[x][y]+1){
                cost[x-1][y]=cost[x][y]+1;
                q.push(make_pair(x-1,y));
            }
        if(p[x+1][y]==0)
            if(cost[x+1][y]>cost[x][y]+1){
                cost[x+1][y]=cost[x][y]+1;
                q.push(make_pair(x+1,y));
            }
        if(p[x][y-1]==0)
            if(cost[x][y-1]>cost[x][y]+1){
                cost[x][y-1]=cost[x][y]+1;
                q.push(make_pair(x,y-1));
            }
        if(p[x][y+1]==0)
            if(cost[x][y+1]>cost[x][y]+1){
                cost[x][y+1]=cost[x][y]+1;
                q.push(make_pair(x,y+1));
            }
        q.pop();
    }
    if(cost[h][w]>h*w)
        cout << -1 << endl;
    else
        cout << h*w-cost[h][w]-mas-1 << 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 ALL(n) begin(n),end(n)

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

    int ans=1;
    for(int i=2; i<=sqrt(x); i++){
        for(int j=2; j<1000; j++){
            if(pow(i,j)>x){
                break;
            }
            if(pow(i,j)>ans){
                ans=pow(i,j);
            }
        }
    }

    cout<<ans<<endl;
}

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

int x[1000],n,q,a,b;
int y[1000][2];
char c;

int main(){
	while(true){
		for(int i=0;i<1000;i++){x[i]=0;y[i][0]=0;y[i][1]=0;}
		cin>>n>>q;
		if(n==0 && q==0){break;}
		for(int i=0;i<q;i++){
			cin>>c>>a;
			if(c=='s'){
				cin>>b;
				for(int j=0;j<=n-b;j++){
					int t=b;
					for(int k=j;k<j+b;k++){
						if(x[k]==0){
							t--;
						}
					}
					if(t==0){
						cout<<j<<endl;
						for(int k=j;k<j+b;k++){
							x[k]=1;
						}
						y[a][0]=j;y[a][1]=j+b;
						goto E;
					}
				}
				cout<<"impossible"<<endl;
E:;
			}
			if(c=='w'){
				for(int j=y[a][0];j<y[a][1];j++){
					x[j]=0;
				}
				y[a][0]=0;y[a][1]=0;
			}
		}
		cout<<"END"<<endl;
	}
	return 0;
}

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

using namespace std;

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

int main() {
    string str, com, phrase;
    int a, b, q;

    cin >> str >> q;
    REP(t, q) {
        cin >> com >> a >> b;
        if (com == "print") {
            cout << str.substr(a, b - a + 1) << endl;
        } else if (com == "reverse") {
            string tmp = str.substr(a, b - a + 1);
            int n = tmp.size();
            REP(i, n) str[i + a] = tmp[n - i - 1];
        } else if (com == "replace") {
            cin >> phrase;
            str = str.replace(a, b - a + 1, phrase);
        }
    }
}

Measured memory_bytes: 3220
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    string s;cin>>s;
    for(int i=0;i<s.size();i+=2)if((i+1)%2==1)cout<<s[i];
    cout<<endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
   int n;
   cin>>n;
   vector<int> v(n);
   for(int &x:v) cin>>x;
   vector<int> m(n);
   m[0]=v[0];
   int small = v[0]; 
   for(int i=1;i<n;i++)
   {
       small = min(small,v[i]);
       m[i]=small;
   }
   int ans=0;
   for(int i=0;i<n;i++)
   {
       if(v[i]==m[i]) ans++;
   }
   cout<<ans;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll H,A;
  cin>>H>>A;
  if(H%A==0) {
cout<<H/A<<endl;
  }
  else {
cout<<H/A+1<<endl;
  }
}


Measured memory_bytes: 3592
n = int(input())

if n<105:
    print(0)
    exit(0)

ans = 0

for i in range(105,n+1):
    if i%2 == 0:
        continue
    num = 0
    for j in range(1,i+1):
        if i%j == 0:
            num += 1
    if num == 8:
        ans += 1

print(ans)

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int main()
{
  long a, b, k, i;
  long count=0;
  scanf("%ld %ld %ld",&a, &b, &k);
  while(1) {
    a /= 2;
    b += a;
    count++;
    if(count==k)break;

    b /= 2;
    a += b;
    count++;
    if(count==k)break;
  }
  printf("%ld %ld", a , b);
  return 0;
}


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

int main() {
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;
	vector<pair<int, int>> sum;
	pair<int, int> tmp;
	for (int i = 0; i < S.size(); ++i) {
		if (S[i] == '0') ++tmp.first;
		else {
			if (tmp.first) sum.push_back(tmp);
			tmp.first = 0;
			tmp.second = i + 1;
		}
	}
	if (tmp.first) sum.push_back(tmp);
	//for (pair<int, int>& i : sum) cout << i.first << ' ' << i.second << endl;
	sort(sum.begin(), sum.end(), [](pair<int, int>& a, pair<int, int>& b)->bool { return a.second < b.second; });
	//	for (pair<int, int>& i : sum) cout << i.first << ' ' << i.second << endl;
	if (sum.size() <= K) cout << S.size();
	else {
		int ans = sum[K].second;
		for (int i = 1; i < sum.size() - K; ++i) {
			ans = max(sum[i + K].second - (sum[i - 1].second + sum[i - 1].first), ans);
			//	10 - 4 = 6
		}
		ans = max(N - (sum[sum.size() - K - 1].second + sum[sum.size() - K - 1].first), ans);
		//	14 - (5 + )
		cout << ans;
	}
}

Measured memory_bytes: 1020
#include"bits/stdc++.h"
using namespace std;
typedef long long               ll ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef vector<int>             vi ;
typedef vector<vector<int>>     vvi ;
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mem(a) memset(a,0,sizeof(a))
#define mod  1000000007LL
#define     ff          first
#define     ss          second
#define print(p) for(auto x:p){cout<<x<<" ";}









int main(){
    fast()
    int n;
    cin>>n;
    vector<int>a(n+5);

    for(int i=0;i<n;i++){
            cin>>a[i];
    }
    int p=-1,q=-1;
    for(int i=0;i<n-1;i++){
            if(a[i]>a[i+1]&&p==-1){
               p=i;
            }
             if(a[i]>a[i+1]&&p!=-1){
               q=i+1;
            }

    }
 
    swap(a[p],a[q]);

    for(int i=0;i<n-1;i++){
            if(a[i]>a[i+1]){cout<<"NO"<<endl;
    return 0;
            }

    }
    cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 256
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n,k = mp()
dt = {}
for i in range(1,n+1):
    dt[i] = 0
for i in range(k):
    d = inp()
    x = ip()
    for i in x:
        dt[i] = 1
print(list(dt.values()).count(0))

Measured memory_bytes: 67580
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int n=N;
		int sum=0;
		while(n>0) {
			sum+=n%10;
			n=n/10;
		}
		if(N%sum==0) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 22868
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  int n,o[100005]={},e[100005]={};
  cin >> n;
  for(int i=0; i<n; i++) {
    int a;
    cin >> a;
    if((i+1)%2==1) {
      o[a]++;
    }
    else {
      e[a]++;
    }
  }
  int Me=0,Mo=0,ei,oi;
  for(int i=1; i<=100000; i++) {
    if(Me<e[i]) {
      Me=e[i],ei=i;
    }
    if(Mo<o[i]) {
      Mo=o[i],oi=i;
    }
  }
  sort(e,e+100005,greater<int>());
  sort(o,o+100005,greater<int>());
  if(ei==oi) {
    cout << min(n-e[0]-o[1],n-e[1]-o[0]) << endl;
  }
  else {
    cout << n-e[0]-o[0] << endl;
  }
}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
/*文字列内に出てこない辞書順最小の文字をくっつける
文字列内にすべての文字がある場合は後ろから文字を見ていって
文字が前のものより小さくなったらその文字を
そこで見た中で一番小さい文字に変える ←違う
*/
int main()
{
    string s;cin >> s;
    if(s=="zyxwvutsrqponmlkjihgfedcba"){
        cout << -1 << "\n";
        return 0;
    }
    string ans=s;
    string s1;
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    set<char> c;
    REP(i,SZ(s)){
        char si = s[i];
        c.insert(si);
    }
    if(SZ(s)!=26){
        REP(i,26){
            if(!c.count(alphabet[i])){
                s += alphabet[i];
                cout << s << "\n";
                break;
            }
        }
    }else{
        char pre = 'a';
        string min_s="";

        IREP(i, SZ(s))
        {
            //cout << i <<"  "<<pre << "\n";
            //cout << min_s << "\n";
            
            if(s[i]<pre){
                s1=s.substr(0, i);
                //cout << "s=" << s << "\n";
                sort(ALL(min_s));
                REP(j,SZ(min_s)){
                    //cout << min_s[j] <<"1"<<s[i]<<"2";
                    if(min_s[j]>s[i]){
                        s1 += min_s[j];
                        break;
                    }
                }
                break;
            }
            pre = s[i];
            min_s += s[i];
        }
        cout << s1 << "\n";
    }
    

    return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import Text.Printf

readInt = ( readLn :: IO Int )
getInts = map ( read :: String -> Int ) . words <$> getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ n, a, b ] <- getInts
	ts <- replicateM n readInt
	print $ length $ filter ( \t -> t < a || b <= t ) ts


Measured memory_bytes: 1020
#include<stdio.h>
#define rep(i,n) for(int i=0;i<n;++i)
int a[1<<18],v[1<<18][2],l[1<<18],n,m,q,c;
main(){
	scanf("%d %d %d",&n,&m,&q);
	rep(i,n)rep(j,2)v[i][j]=(i+n+1-2*j)%n;
	rep(i,m){
		scanf("%d",a+i);
		rep(j,a[i])c=v[c][a[i]&1];
		l[c]=1;
		rep(j,2)v[v[c][j^1]][j]=v[c][j];
		c=v[c][0];
	}
	rep(i,q) scanf("%d",&c),printf("%d\n",1-l[c]);
}

Measured memory_bytes: 4884
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] * 5
for i in range(5):
    A[i] = ir()

mi = min(A)
plus = -(-N//mi)
answer = 4 + plus
print(answer)


Measured memory_bytes: 3060
//FIRST THINK THEN CODE.

#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
#define MOD 998244353
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define endl "\n"

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1LL;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}


 
ll poww(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;

}

template<typename T,typename F>
void chmax( T &a,F b){
  if(b>a)a=b;
}

template<typename T,typename F>
void chmin( T &a,F b){
  if(b<a)a=b;
}

const ll N=1e6+5;

char a[10][10];

int main()
{ 

  IOS;

ll n;cin>>n;

vl a(n+1);

for(int i=1;i<=n;i++){
  cin>>a[i];
}

sort(a.begin()+1,a.end(),greater<>());


ll pos=(n+1)/2;

ll ans=0;

for(int i=1;i<pos;i++){
  ans+=a[i];
}

ll rem=n-pos;

for(int i=2;i<=pos;i++){
  rem--;
  ans+=a[i];
}

if(rem==1)ans+=a[pos];

cout<<ans<<endl;

return 0;
 
}



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

int main() {
    int n, d, x;
    cin >> n >> d >> x;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int ans = x;
    for(int i = 0; i < n; ++i) {
        ans += 1 + (d - 1) / a[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

@SuppressWarnings("unchecked")
public class Main {

  private void solve(Scanner in, PrintWriter out) {
    int N = in.nextInt();
    int M = in.nextInt();

    FenwickTree bit = new FenwickTree(M + 2);

    ArrayList<Integer>[] multipliers = new ArrayList[M + 1];
    for (int i = 1; i <= M; i++) {
      multipliers[i] = new ArrayList<>();
      for (int j = i; j <= M; j += i) {
        multipliers[i].add(j);
      }
    }

    int[] l = new int[N];
    int[] r = new int[N];
    ArrayList<Integer>[] buckets = new ArrayList[M + 1];
    for (int i = 1; i <= M; i++) {
      buckets[i] = new ArrayList<>();
    }

    for (int i = 0; i < N; i++) {
      l[i] = in.nextInt();
      r[i] = in.nextInt();
      int w = r[i] - l[i] + 1;
      buckets[w].add(i);
    }

    int gone = 0;
    for (int d = 1; d <= M; d++) {
      for (int i : buckets[d]) {
        gone++;
        bit.add(l[i], 1);
        bit.add(r[i] + 1, -1);
      }

      int ans = N - gone;
      for (int m : multipliers[d]) {
        ans += bit.sum(m + 1);
      }

      out.println(ans);
    }
  }

  public class FenwickTree {

    int N;
    long[] data;

    FenwickTree(int N) {
      this.N = N + 1;
      data = new long[N + 1];
    }

    void add(int k, long val) {
      for (int x = k; x < N; x |= x + 1) {
        data[x] += val;
      }
    }

    // [0, k)
    long sum(int k) {
      if (k >= N) {
        k = N - 1;
      }
      long ret = 0;
      for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) {
        ret += data[x];
      }
      return ret;
    }

    // [l, r)
    long sum(int l, int r) {
      return sum(r) - sum(l);
    }

    long get(int k) {
      assert (0 <= k && k < N);
      return sum(k + 1) - sum(k);
    }

    int getAsSetOf(int w) {
      w++;
      if (w <= 0) {
        return -1;
      }
      int x = 0;
      int k = 1;
      while (k * 2 <= N) {
        k *= 2;
      }
      for (; k > 0; k /= 2) {
        if (x + k <= N && data[x + k - 1] < w) {
          w -= data[x + k - 1];
          x += k;
        }
      }
      return x;
    }
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(in, out);
    in.close();
    out.close();
  }
}


Measured memory_bytes: 163388
//
//  main.cpp
//  1234
//
//  Created by Moha Jain on 14/04/20.
//  Copyright © 2020 Moha Jain. All rights reserved.
//
 
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<math.h>
#include <iomanip>
#include <numeric>
#define _USE_MATH_DEFINES
 
using namespace std;
 

 
int main()
{
    int n;cin>>n;
    string s[n];
    
    unordered_map<string,int>mp;
    for(int i=0;i<n;i=i+1){cin>>s[i];mp[s[i]]++;}
    
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;
    
    

}





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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef vector< vector<int> > vvi;


int bfs(vvi &adj, int s, int k, int e){

	int ret = 0;

	int dist = 0;

	queue<int> q;
	q.push(s);
	unordered_set<int> visited;

	if(e != -1) visited.insert(e);

	while(!q.empty()){

		int n = (int)q.size();

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

			int curr = q.front(); q.pop();

			if(visited.count(curr)) continue;

			// cout << curr + 1 << endl;

			for(int child : adj[curr]){
				if(!visited.count(child)) q.push(child);
			}

			ret++;
			visited.insert(curr);
		}

		// cout << ret << ' ' << dist << endl;

		if(dist == k) break;

		dist++;
	}

	return ret;
}


void solve(){

	int n, k;
	cin >> n >> k;
	
	vvi adj(n);

	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int maxC = 0;

	if(k % 2 == 0){

		//Each Vertex
		for(int i = 0; i < n; i++){
			int covered = bfs(adj, i, k / 2, -1);
			maxC = max(maxC, covered);
		}

	}else{

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

			for(int v : adj[i]){

				int c1 = bfs(adj, i , k / 2, v);
				int c2 = bfs(adj, v , k / 2, i);

				// string line = "(" + to_string(i + 1) + ", " + to_string(v + 1) + ")";
				// cout << line << ": " << (c1 + c2) << endl;

				maxC = max(maxC, c1 + c2);

			}
		}
	}

	cout << n - maxC << endl;

}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;
}

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

	int main(){
      string a,b;
      cin >> a >> b;
      if (a.size()==b.size()){
        list<string>  S;
        S={a,b};
        S.sort();
        list<string>::iterator i;
        i=S.begin();
        if (*i==a){
          i++;
          if (*i==a){
            cout << "EQUAL" << endl;
          }
          else{
            cout << "LESS" << endl;
          }
        }
        else{
          cout << "GREATER" << endl;
        }
      }
      if (a.size()>b.size()){
        cout << "GREATER";
      }
      if (a.size()<b.size()){
        cout << "LESS";
      }
    }


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

int main() {
	string c;

	cin >> c;

	if (c == "a" || c == "e" || c == "i" || c == "o" || c == "u") {
		cout << "vowel" << endl;
	}
	else {
		cout << "consonant" << endl;
	}
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define whole(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

const int N = (int)1e5 + 2;
const int LG = 20;
const ll mod = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const ll linf = 1e13;
const ld pi = acos(-1);
const int base = 10;
const ld EPS = 1e-9;

int n, m, d[N];
bool used[N];
vector < int > g[N];

void dfs (int v)
{
    used[v] = true;
    for (int to : g[v])
    {
        if (!used[to]){
            dfs(to);
        }
    }
    for (int to : g[v])
    {
        d[v] = max(d[v], d[to] + 1);
    }
}

int main ()
{
    scanf ("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        g[x].pb(y);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!used[i]) dfs(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, d[i]);
    printf ("%d\n", ans);
    return 0;
}


Measured memory_bytes: 8192
#include <iostream>
#include <iterator>
#include <cmath>
#include <vector>
#define MAX_HP 1000000000

int main(void)
{
    using namespace std;
    int N;
    int A;
    vector<int> An;

    cin >> N;

    for ( int i =0; i < N; i++) {
        cin >> A;
        /*cout << A % 2;
        cout << (A % 3);
        cout << (A % 5);*/
        if(A % 2 == 0){
            if(( (A % 3) != 0) && ( (A % 5) != 0)){
                cout << "DENIED";
                return 0;
            }
        }
    } 

    cout << "APPROVED";

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;


int main() {
    ll N, M;
    cin >> N >> M;

    vector<pair<ll, ll>> shop(N);
    for(ll i=0; i<N; i++) {
        ll a, b;
        cin >> a >> b;
        shop.push_back(make_pair(a, b));
    }
    sort(shop.begin(), shop.end());

    ll count = 0;
    ll cost = 0;

    for(auto s : shop) {
        if(count + s.second >= M) {
            cost += (M-count) * s.first;
            cout << cost << endl;
            return 0;
        }
        else {
            cost += s.second * s.first;
            count += s.second;
        }
    }
}

Measured memory_bytes: 6356
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...) 0
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string foo;
    cin >> foo;
    ll n = foo.size();
    vector<ll> s(n + 2);
    rep(i, 0, n) s[i] = foo[n - 1 - i] - '0';
    vector<vector<ll>> dp(n + 2, vector<ll>(2, 1e18));
    dp[0][0] = 0;
    rep(i, 0, n + 1) {
        dp[i + 1][0] = min(dp[i][0] + s[i], s[i] + dp[i][1] + 2);
        dp[i + 1][1] = min(dp[i][1] + 9 - s[i], dp[i][0] + 9 - s[i]);
    }
    cout << dp[n + 1][0] << endl;
    debug(dp);
    return 0;
}


Measured memory_bytes: 63772
from collections import defaultdict
import bisect

s = input()
t = input()

n = len(s)
m = len(t)

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i+n)

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        i = bisect.bisect_right(l, pos)
        ind = l[i]
        if ind >= n:
            pos = ind - n
            ans += n
        else:
            pos = ind    
    else:
        ans = -1
        break

print(ans if ans==-1 else ans+pos+1)




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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

/* debugging */
#define TRACE

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


#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int32_t main(){
    boost;
    //code
    int n , m , t;
    cin >> n >> m;

    set<int> s;
    for(int i = 0 ; i < m ; ++i){
    	cin >> t;
    	s.insert(t);
    }

    int p[n+1];

    p[0] = 0;
    p[1] = 1;
    p[2] = 2;
    
    if(s.find(1) != s.end()){
    	p[1] = 0;
    	p[2] = 1;
    }

    if(s.find(2) != s.end()){
    	p[2] = 0;
    }

    for(int i = 3 ; i <= n ; ++i){
    	if(s.find(i) != s.end()){
    		p[i] = 0;
    	}
    	else{
    		p[i] = (p[i-1] + p[i-2])%mod;
    	}
    }
    cout << p[n]%mod;

    return 0;
}

Measured memory_bytes: 5760
x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])

Measured memory_bytes: 8708
#include<iostream>
#include<cstring>
using namespace std;
string a,b="CF"; 
int al,bl;
int main()
{
    getline(cin,a);
    al=a.size();
    for(int i=0;i<al;i++)
        if(a[i]==b[bl])
		{ 
            bl++;
            if(bl==2)  
                break;
        }
    if(bl==2) cout<<"Yes"; 
    else cout<<"No";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe

readInts :: IO [Integer]
readInts = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readStrings :: IO [BS.ByteString]
readStrings = BS.words <$> BS.getLine

main :: IO ()
main = do
  (k:x:_) <- readInts
  putStrLn $ solve k x


solve k x
  | k * 500 >= x = "Yes"
  | otherwise = "No"

Measured memory_bytes: 380
#define _CRT_SECURE_NO_WARNINGS
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


int h, w;
char c[500][500];
bool red[500][500];
bool blue[500][500];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w;
	rep(i, h)rep(j, w) {
		cin >> c[i][j];
		if (c[i][j]== '#')red[i][j] = blue[i][j] = true;
	}
	rep(i,h)rep(j,w) {
		if (i == 0) {
			red[i][j] = true;
		}
		else if (i == h - 1) {
			blue[i][j] = true;
		}
		else if (j%3==0||j%3==2) {
			blue[i][j] = true;
		}
		else {
			red[i][j] = true;
		}
	}
	rep(i, h) {
		rep(j, w) cout << (red[i][j] ? '#' : '.');
		cout << endl;
	}
	cout << endl;
	rep(i, h) {
		rep(j, w) cout << (blue[i][j] ? '#' : '.');
		cout << endl;
	}

	/*cout << endl;
	rep(i, h) {
		rep(j, w) cout << (blue[i][j]&&red[i][j] ? '#' : '.');
		cout << endl;
	}*/

	return 0;
}

Measured memory_bytes: 1536
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<assert.h>
#include<set>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<iostream>
#include<bitset>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
#define per(i,j,k) for(int i=(int)(j);i>=(int)(k);i--)
using namespace std;
typedef long long LL;
//template
typedef double db;
const db eps=1e-10;
const db pi=acosl(-1.0);
int sign(db x){if(x<-eps)return -1;if(x>eps)return 1;return 0;}
int cmp(db x,db y){return sign(x-y);}
struct po{
	db x,y;
	po(db _x=0,db _y=0):x(_x),y(_y){}
};
po operator +(const po &a,const po &b){return po(a.x+b.x,a.y+b.y);}
po operator -(const po &a,const po &b){return po(a.x-b.x,a.y-b.y);}
po operator *(const po &a,const db &b){return po(a.x*b,a.y*b);}
po operator /(const po &a,const db &b){return po(a.x/b,a.y/b);}
db operator *(const po &a,const po &b){return a.x*b.x+a.y*b.y;}
db operator ^(const po &a,const po &b){return a.x*b.y-a.y*b.x;}
db mo2(po a){return a*a;}
db mo(po a){return sqrt(a*a);}
po proj(po x,po y){//proj x to y
	return y*((x*y)/mo2(y));
}
//template
int main(){
	po p1,p2;
	scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
	int t;scanf("%d",&t);
	while(t--){
		po x;scanf("%lf%lf",&x.x,&x.y);
		po rp=proj(x-p1,p2-p1)+p1;
		printf("%.10lf %.10lf\n",rp.x,rp.y);
	}
	return 0;
}












Measured memory_bytes: 3252
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define N 100000
#define Q 50000
int main(){
  int i,n,q,j,S[N],T[Q],AI=0,left,right,mid;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<q;i++){
    left=0;
    right=n;
    while(left<right){
      mid=(left+right)/2;
      if(T[i]==S[mid]){
	AI++;
	break;
      }
      if(T[i]>S[mid])
	left=mid+1;
      else if(T[i]<S[mid])
	right=mid;
    }
  }
  printf("%d\n",AI);
  
  
  return 0;
}

Measured memory_bytes: 1188
N = int(input())
As = list(map(int,input().split()))
c = 0
nums = [0]*(10**5+1)
for a in As:
    nums[a]+=1

for i in range(1,len(nums)):
    if i == len(nums)-1:
        t = nums[i - 1] + nums[i]
    else:
        t = nums[i-1]+nums[i]+nums[i+1]
    c = max(c,t)
print(c)




Measured memory_bytes: 84216
from collections import defaultdict as dd
N,M=map(int,input().split())
h = list(map(int, input().split()))
ab = [list(map(int,input().split())) for _ in range(M)]
res = [1]*N

for ls in ab:
    a,b = ls[0]-1,ls[1]-1
    if h[a] < h[b]:
        res[a] = 0
    elif h[a] > h[b]:
        res[b] = 0
    else:
        res[a] = 0
        res[b] = 0
print(sum(res))



Measured memory_bytes: 32332
#include<cstdio>
#include<algorithm>
#include<bitset>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=2000+10;
bitset<maxn*maxn> f;
int a[maxn];
int i,j,k,l,t,n,m;
int main(){
	scanf("%d",&n);
	f[0]=1;
	fo(i,1,n){
		scanf("%d",&a[i]);
		m+=a[i];
		f=f|(f<<a[i]);
	}
	m=(m+1)/2;
	while (!f[m]) m++;
	printf("%d\n",m);
}

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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979323846

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




ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int ans = 0;
int N, M, Q;

template<typename T>
void showall(vector<T> v){
  rep(i, 0, v.size()){
    cout << v[i] << " ";
  }
  cout << endl;
}

template<typename T>
ll com(T n, T m, T mod){
  ll a = 1, b = 1, ans;
  if(n == m || m == 0){
    ans = 1;
  }else{
    for(ll i = 0;i < m; i++){
      a *= n-i;
      a %= mod;
      b *= i+1;
      b %= mod;
    }
    ans = (a * powmod(b, mod-2, mod)) % mod;
  }
  
  return ans;
}


 
int main() {
  int X, N;
  cin >> X >> N;

  set<int> p;

  rep(i, 0, N){
    int a;
    cin >> a;

    p.insert(a);
  }
  int check_p = X;
  int check_m = X;
  int dis = 0;
  while(true){
    check_p = X + dis;
    check_m = X - dis;
    if(!(p.find(check_m) != p.end())){
      cout << X - dis << endl;
      return 0;
    }else if(!(p.find(check_p) != p.end())){
      cout << X + dis << endl;
      return 0;
    }

    dis++;

  }


  
  // cout << setprecision(8) << ans << endl;  // For double
}



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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, k;
  cin >> n >> k;
  map<int, int> mp;
  rep(i, 0, n) {
    int a;
    cin >> a;
    mp[a]++;
  }
  vector<int> v;
  for(auto i = mp.begin(); i != mp.end(); i++) {
    v.pb(i->second);
  }
  sort(v.begin(), v.end());
  int ans = 0;
  int c = v.size() - k;
  rep(i, 0, c) {
    ans += v[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 10744
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
int main(){
	int A,B,V,W,T;
	cin>>A>>V>>B>>W>>T;
	if (V<=W) puts("NO"); 
	else {
		if (1ll*abs(A-B)<=1ll*(V-W)*T) puts("YES");
		else puts("NO");
	}
	return 0;
}




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

int main(){
	int mountains[10];
	for(int i = 0; i < 10; i ++ ){
		cin >> mountains[i];
	}
	sort(mountains, mountains + 10);
	cout << mountains[9] << endl;
	cout << mountains[8] << endl;
	cout << mountains[7] << endl;
	
	return 0;
}


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

using namespace std;

int main()
{
 int r,D,xi,xf;
 cin>>r>>D>>xi;
 if(r>=2&&r<=5&&D<=100&&D>=1&&xi>D&&xi<=200){
     for (int j=1;j<11;j++){
        xf=(r*xi)-D;
        xi=xf;
        cout<<xf<<endl;
     }
     
 }
    return 0;
}

Measured memory_bytes: 3640