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

using i64 = int64_t;

struct RSQRAQ {
  int n;
  vector<i64> dat, lazy;
 
  RSQRAQ(){}
  RSQRAQ(int n_) {
    n = 1; while(n < n_) n *= 2;
    dat.assign(n*2, 0);
    lazy.assign(n*2, 0);
  }
 
  void eval(int len, int k) {
    if(lazy[k] == 0) return;
    if(k*2+1 < n*2-1) {
      lazy[2*k+1] += lazy[k];
      lazy[2*k+2] += lazy[k];
    }
    dat[k] += lazy[k]*len;
    lazy[k] = 0;
  }
 
  // [a, b)
  i64 update(int a, int b, i64 x, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      lazy[k] += x;
      return dat[k] + lazy[k]*(r-l);
    }
    return dat[k] = update(a, b, x, 2*k+1, l, (l+r)/2) + update(a, b, x, 2*k+2, (l+r)/2, r);
  }
  i64 update(int a, int b, i64 x) { return update(a, b, x, 0, 0, n); }
 
  // [a, b)
  i64 query(int a, int b, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return dat[k];
    i64 vl = query(a, b, 2*k+1, l, (l+r)/2);
    i64 vr = query(a, b, 2*k+2, (l+r)/2, r);
    return vl + vr;
  }
  i64 query(int a, int b) { return query(a, b, 0, 0, n); }
}; 

int main(){
    i64 n, d, a;
    cin >> n >> d >> a;
    vector<pair<i64, i64>> v;
    for(int i=0;i<n;++i){
        i64 x, h;
        cin >> x >> h;
        v.emplace_back(x, h);
    }
    sort(v.begin(), v.end());

    RSQRAQ seg(n);
    for(int i=0;i<n;++i)seg.update(i, i+1, v[i].second);
    i64 ans = 0, right = 0;
    for(int left = 0;left<n;++left){
        i64 hp = seg.query(left, left+1);
        if(hp <= 0)continue;
        i64 num = (hp + a - 1) / a;
        i64 damage = a * num;
        ans += num;
        //cerr << num << " " << damage << endl;
        while(right < n && v[right].first - v[left].first <= 2*d){
            right++;
        }
        seg.update(left, right, -damage);
        /*for(int i=0;i<n;++i){
            cerr << seg.query(i, i+1) << " ";
        }
        cerr << endl;
        */
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12524
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static MyIO;


public class A
{
	public static void Main()
	{
		int N = GetInt();
		int K = GetInt();
		Console.WriteLine(N-K+1);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define ll long long;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
       cin>>a[i];
   int d[n+1]={0};
   d[1]=0;
   d[2]=d[1]+abs(a[2]-a[1]);
  
  for(int i=3;i<=n;i++)
   d[i]=min(d[i-2]+abs(a[i]-a[i-2]),d[i-1]+abs(a[i]-a[i-1]));
   
   cout<<d[n]<<"\n";
}

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

int main(){
	string S;
	cin>>S;
	int a,b;

	a = stoi(S.substr(0,2));
	b = stoi(S.substr(2,2));

	if(a==0){
		if(b==0)
			cout<<"NA"<<endl;
		else if(b<=12)
			cout<<"YYMM"<<endl;
		else if(b>12)
			cout<<"NA"<<endl;
	}
	else if(a<=12){
		if(b==0)
			cout<<"MMYY"<<endl;
		else if(b<=12)
			cout<<"AMBIGUOUS"<<endl;
		else if(b>12)
			cout<<"MMYY"<<endl;
	}
	else{
		if(b==0)
			cout<<"NA"<<endl;
		else if(b<=12)
			cout<<"YYMM"<<endl;
		else if(b>12)
			cout<<"NA"<<endl;
	}
}


Measured memory_bytes: 256
import itertools
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    cities = [list(map(int, input().split())) for _ in range(N)]

    perms = list(itertools.permutations(range(N), N))
    l = 0
    for v in perms:
        for i in range(N-1):
            xi, yi = cities[v[i]]
            xj, yj = cities[v[i+1]]

            l += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5

    ans = l / len(perms)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 8052
IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  indata PIC X(100).
       01  a1 PIC S9(08).
       01  a2 PIC S9(08).
       01  a3 PIC S9(08).
       01  a4 PIC S9(08).
       01  r1 PIC S9(08).
       01  r2 PIC S9(08).
       01  r3 PIC S9(08).
       01  r pic S9(08).
       01 disp pic Z(20)9.
       PROCEDURE DIVISION.
        ACCEPT indata.
        UNSTRING indata DELIMITED BY SPACE INTO a1 a2.
        ACCEPT indata.
        UNSTRING indata DELIMITED BY SPACE INTO a3 a4.

        compute r = (a1 * a2) - (a3 * a2) - (a4 * (a1 - a3) ) 

        MOVE FUNCTION TRIM(r) to disp
        DISPLAY disp

       STOP RUN.


Measured memory_bytes: 384
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    lis=[1]*n
    rlis=[False]*n
    rlis[0]=True
    for i in range(m):
        x,y=map(int,input().split())
        x-=1
        y-=1
        if lis[x]==1:
            lis[x]-=1
            lis[y]+=1
            if rlis[x]:
                rlis[x]=False
                rlis[y]=True
        else:
            lis[x]-=1
            lis[y]+=1
            if rlis[x]:
                rlis[y]=True
    print(rlis.count(True))


if __name__=='__main__':
    main()

Measured memory_bytes: 42604
import numpy as np
# coding: utf-8
# Your code here!
N, M = map(int, input().split())
#S = input()

H = list(map(int, input().split()))
path_list = [[0] for _ in range(N)]

for m in range(M):
    A, B = map(int, input().split())
    path_list[A-1].append(H[B-1])
    path_list[B-1].append(H[A-1])
    

path_max = [np.max(path_list[i]) for i in range(N)]
H = np.array(H)

#print(H)
#print(path_max)
print(len(H)-len(H[H<=path_max]))

Measured memory_bytes: 49296
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int cnt[n][26];
    memset(cnt,0,sizeof(cnt));
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<s.size();j++){
            cnt[i][s[j]-'a']++;
        }
    }
    string ans = "";
    for(int i=0;i<26;i++){
        int minn = INT_MAX;
        for(int j=0;j<n;j++){
            minn = min(minn,cnt[j][i]);
        }
        string s(minn,(char)(i+'a'));
        ans += s;
    }
    sort(ans.begin(),ans.end());
    cout<<ans<<"\n";
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
const int mod = 1000000007;
const int max_n = 200005;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll s,w;cin >> s >>w;
    if(s<=w)cout << "unsafe" <<endl;
    else cout <<"safe" <<endl;
}


Measured memory_bytes: 3632
#include <stdlib.h> 
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std; 

int main()
{
  int x,y;
  
  cin>>x>>y;
  
  if( y % 2 == 0)
  {
  	if(y >= x*2 && y <= x*4)
  	{
  		cout<<"Yes";
  		
  	}
  	else cout<<"No";
  }
  else cout<<"No";
  
  
}


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


using namespace std;


using ll = long long;


int main()
{
    ll N;
    vector<ll> A;
    vector<ll> B;
    vector<ll> C;

    cin >> N;
    ll tmp;
    for (ll i = 0; i < N; i++) {
        cin >> tmp;
        A.push_back(tmp);
    }
    for (ll i = 0; i < N; i++) {
        cin >> tmp;
        B.push_back(tmp);
    }
    for (ll i = 0; i < N; i++) {
        cin >> tmp;
        C.push_back(tmp);
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    ll ans = 0;
    for (auto e : B) {
        ll a, c;
        a = lower_bound(A.begin(), A.end(), e) - A.begin();
        c = C.end() - upper_bound(C.begin(), C.end(), e);
        ans += a * c;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3316
import java.util.*;
 
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] p = new int[N];
		for (int i=0;i<N;i++){
			p[i]=sc.nextInt();
		}
		Arrays.sort(p);
      int x = 0;
      int w = p[N-1];
      for(int i =0;i<N-1;i++){
        x = x + p[i];
      }
      	if(w<x){
          System.out.print("Yes");
        }else{
          System.out.print("No");
        }

	}
}

Measured memory_bytes: 21844
//#include "stdc++.h"
#include<bits/stdc++.h>
#include<iostream>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define pb push_back
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0) return 1;ll p=power(a,n/2,m);p=(p*p)%m;if(n%2) return (p*a)%m;else return p; }
#define flush fflush(stdout)
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

int main()
{
    IOS;//ifstream fin("input.txt");ofstream fout("output.txt");
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    bool dp[k+1][2];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
        if(a[i]<=k)
        {dp[a[i]][0]=1;dp[a[i]][1]=1;
        }
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[j]<=i)
            {
                dp[i][0]=dp[i][0]|(!dp[i-a[j]][1]);
                dp[i][1]=dp[i][1]|(!dp[i-a[j]][0]);
            }
        }
    }
    if(dp[k][0])
        cout<<"First";
    else
        cout<<"Second";
    cout<<endl;
    return 0;
    return 0;
}


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

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main() {
    string s;
    cin >> s;
    if (s == "zyxwvutsrqponmlkjihgfedcba") {
        cout << -1 << endl;
        return 0;
    }
    if (s.size() == 26) {
        set<char> st;
        repr(i, s.size()) {
            auto it = st.upper_bound(s[i]);
            for (; it != st.end(); ++it) {
                char c = *it;
                bool f = true;
                rep(j, i) if (c == s[j]) f = false;
                if (f) {
                    cout << s.substr(0, i) << c << endl;
                    return 0;
                }
            }
            st.insert(s[i]);
        }
        assert(false);
        // cout << -1 << endl;
        return 0;
    }
    set<char> st;
    rep(i, 26) st.insert(('a' + i));
    rep(i, s.size()) {
        st.erase(s[i]);
    }
    cout << s << *st.begin() << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

#define MIN -1000000
#define MAX 1000000

using namespace std;
typedef long long int lint;

void answer()
{
	lint n, min, max, sum;
	lint tmp;

	cin >> n;

	min = MAX; max = MIN; sum = 0;
	for (lint i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp < min) min = tmp;
		if (max < tmp) max = tmp;
		sum += tmp;
	}
	printf("%lld %lld %lld\n", min, max, sum);
}

int main()
{
	answer();
	return 0;
}

Measured memory_bytes: 1148
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int A,B;cin >> A >> B;
    if(A<=5)cout << 0 << endl;
    else if(A<=12)cout << B/2 << endl;
    else cout << B << endl; 
    return 0;
}

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

#define rep(i,s,t) for(int i = s; i <= t; ++ i)
#define fi first
#define se second
const int MaxN = 100050;

int N, ans, s = 1;
char A[MaxN], B[MaxN];
bool ok = false;

int main()
{
    scanf("%d",&N);
    scanf("%s",A+1);
    scanf("%s",B+1);
    ans = N;
        rep(i,1,N) 
        {
        	ok = false;
        	rep(j,1,N)
        		if(B[j] != A[i+j-1] && i + j - 1 <= N)
        		{
        			ok = true;
   					break;
        		}
        	if(!ok) break;
			ans ++; 
		} 
        printf("%d",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
int a,b,ans=6;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(a),read(b);
	print(ans-a-b);
	return 0;
}

Measured memory_bytes: 256
import sys

l, r = [int(x) for x in input().split()]

remainder_list = []

if r - l >= 2019:
    print(0)
    sys.exit()
else :
    for x in range(l, r):
        for y in range(x + 1, r + 1):
            remainder_list.append((x * y) % 2019)

remainder_list.sort()
print(remainder_list[0])


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

int main() {
  int a, b, c, i = 0;
  cin >> a >> b >> c;
  while (a <= b) {
    if (c % a == 0) {
      i++;
      a++;
    } else {
      a++;
    }
  }
  cout << i << endl;
}


Measured memory_bytes: 3108
#include <stdio.h>
int main (){
	int c;
	scanf ("%d", &c);
	int firstNumber = c / 100;
	int secondNumber = (c % 100) / 10;
	int thirdNumber = c % 10;
	if (firstNumber == 7 || secondNumber == 7 || thirdNumber == 7){
		printf ("Yes", c);
	}else{
		printf ("No", c);
	}
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
int main(void){
    char x,y;
    cin >> x >> y;
    if(x<y){
        cout << "<" << endl;
    }
    else if(x>y){
        cout << ">" << endl;
    }
    else{
        cout << "=" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
const ll mod = 1000000007;
const ll INF = 9223372036854775807;
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define Pi acos(-1)

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll d = 0;
  Sort(a);
  rep(i,n-1) {
    if(a[i] == a[i+1]) {
      ++d;
    }
  }
  if (d%2 == 0) n -= d;
  else n -= (d+1);
  cout << n << '\n';
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>  
 
using namespace std;
 
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int par[100001], Rank[100001];

//n????´???§?????????
void init(int n) {
	rep(i, n) {
		par[i] = i;
		Rank[i] = 0;
	}
}

//??¨??????????±???????
int find(int x) {
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}

//x??¨y????±??????????????????????
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(Rank[x] < Rank[y]) par[x] = y;
	else par[y] = x;
	if(Rank[x] == Rank[y]) ++Rank[x];
}

//x??¨y???????????????????±????????????????
bool same(int x, int y) {
	return find(x) == find(y);
}

struct edge {int u, v, cost; };
int N, M;
edge es[100000];

bool comp(const edge &a, const edge &b){
	return a.cost < b.cost;
}

int kruskal() {
	sort(es, es + M, comp);
	init(N);
	int res = 0;
	rep(i, M) {
		edge &e = es[i];
		if(!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}

int main() {
    while(scanf("%d", &N), N) {
    	scanf("%d", &M);
    	rep(i, M) {
    		int a, b, c;
    		scanf("%d,%d,%d", &a, &b, &c);
    		c = c / 100 - 1;
    		edge tmp = {a, b, c};
    		es[i] = tmp;
    	}
        printf("%d\n", kruskal());
    }
	return 0;
}

Measured memory_bytes: 3228
#include <iostream>

using namespace std;

int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
while(a>0 && c>0){
a-=d;
c-=b;
}
if((a<=0 && c<=0)||c<=0) cout<<"Yes";
    else cout<<"No";
return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<P> p(m);
  rep(i,m) cin >> p[i].first >> p[i].second;//左からfirst桁目がsecond(数字)
  rep(x,1000){
    int keta=1;//0が1桁だから1を初期値にしている
    int nx=x/10;//nx=計算用の変数
    vector<int> d(1,x%10);
    //nxが0になるまで割る10を繰り返す
    while (nx) {
      keta++;
      d.push_back(nx%10);
      nx/=10;
    }
    //この操作では例えば702が合ったら2,0,7の順番で取り出されるからそれを逆順に並び替えれば復元される 
    reverse(d.begin(),d.end());
    if (keta!=n) continue;
    bool ok=true;
    rep(i,m){
      if (d[p[i].first-1]!=p[i].second) ok=false;
    }
    if (ok){
      cout << x << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  int n;
  cin >> n;
  vl a(n,0);
  rep(i,n) cin >> a.at(i);
  sort(rrng(a));

  ll ans = 0;
  ans += a.at(0);
  orep(i,n-2) {
    ans += a.at((i+1)/2);
  }
  cout << ans << endl;

  return 0;
}


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

#define foreach(i,v) for(auto&& i: v)
#define all(x) (x).begin(), (x).end()

typedef std::vector< std::string > VS;
typedef std::vector<int> VI;
typedef long long ll;

template <class C> C& mini(C& a, C b) { if (b < a) a = b; return a; }
template <class C> C& maxi(C& a, C b) { if (a < b) a = b; return a; }

using namespace std;

int main(int argc, const char* argv[]) {
	int N;
	scanf("%d", &N);
	VI a(N);
	foreach (x, a)
		scanf("%d", &x);
	sort(all(a));
	int n = a.back();
	a.pop_back();
	int best = n + 1;
	int k = 0;
	foreach (x, a) {
		int t = abs(2 * x - n);
		if (t < best) {
			best = t;
			k = x;
		}
	}
	printf("%d %d\n", n, k);
	return 0;
}


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

int main(){
    int w, h, n;
    cin >> w >> h >> n;

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

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

    for(int i = 0; i < n; i++){
        if(a[i] == 1){
            for(int j = 0; j < h; j++){
                for(int k = 0; k < x[i]; k++){
                    ans[j][k] = 1;
                }
            }
        }else if(a[i] == 2){
            for(int j = 0; j < h; j++){
                for(int k = x[i]; k < w; k++){
                    ans[j][k] = 1;
                }
            }
        }else if(a[i] == 3){
            for(int j = 0; j < y[i]; j++){
                for(int k = 0; k < w; k++){
                    ans[j][k] = 1;
                }
            }
        }else{
            for(int j = y[i]; j < h; j++){
                for(int k = 0; k < w; k++){
                    ans[j][k] = 1;
                }
            }
        }
        //cout << "W" << w << "h" << h << "ans" << ans << endl;
    }

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

        cout << cou << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
 
#define INF (1e9)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
 

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int gcd(int a,int b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}



int N;
int F[100][10];
int P[100][11];
long long ans = -INF;

void dfs(int d,vector<int> p,int flag){
	if(d!=10){
		vector<int> p0(N);
		vector<int> p1(N);
		copy(p.begin(), p.end(), p0.begin());
		copy(p.begin(), p.end(), p1.begin());

		REP(i,N){
			if(F[i][d]==1){
				p1[i] += 1;
			}
		}
		if(flag==1){
			dfs(d + 1, p0,1);
		}else{
			dfs(d + 1, p0,0);
		}
		dfs(d + 1, p1,1);
	}
	else if(flag==1)
	{
		long long cost = 0;
		REP(i,N){
			int n = p[i];
			cost += P[i][n];
		}
		if (cost > ans)
		{
			ans = cost;
		}
	}
}
int main()
{
	cin >> N;
	vector<int> p(N);
	REP(i,N){
		REP(j,10){
			cin >> F[i][j];
			
		}

		p[i] = 0;
	}

	REP(i,N){
		REP(j,11){
			cin >> P[i][j];
		}
	}

	dfs(0, p,0);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int k;
  string s;
  cin >> k >> s;
  if (s.size() <= k)
    cout << s << endl;
  else cout << s.substr(0,k) << "..." << endl;
}


Measured memory_bytes: 3676
import kotlin.math.max

fun main() {
    val (n, k) = nextIntList()
    val p = nextIntList().map { it - 1 }
    val c = nextLongList()

    var res = Long.MIN_VALUE
    repeat(n) {
        var index = p[it]
        val l = mutableListOf<Int>()
        while (index != l.getOrNull(0)) {
            l.add(index)
            index = p[index]
        }

        var v = Long.MIN_VALUE
        var inner = 0L
        l.take(k).forEach { i ->
            inner += c[i]
            v = max(v, inner)
        }

        if (inner > 0 && k > l.size) {
            val num = k.minus(1).div(l.size)
            inner = inner.times(num)
            l.take(k.minus(l.size.times(num))).forEach { i ->
                inner += c[i]
                v = max(v, inner)
            }
        }
        res = max(res, v)
    }
    println(res)
}

// # Utils
// ## Input
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map(String::toInt)
fun nextLongList() = next().split(" ").map(String::toLong)
fun nextDoubleList() = next().split(" ").map(String::toDouble)

// ## Array
inline fun <reified T> sizedArray(size: Int, default: T) = Array(size) { default }
inline fun <reified T> sized2DArray(row: Int, column: Int, default: T) = Array(row) { Array(column) { default } }

// ## mod^-1
//    [NOTE] CANNOT use this for 0, mod, 2mod, 3mod ...(return wrong value)
fun modinv(num: Long, mod: Long): Long {
    var a = num
    var b = mod
    var u = 1L
    var v = 0L
    while (b > 0) {
        val t = a.div(b)
        a -= t * b
        a = b.also { b = a } // swap a and b
        u -= t * v
        u = v.also { v = u } // swap u and v
    }
    u %= mod
    if (u < 0) u += mod
    return u
}

Measured memory_bytes: 64048
#include<bits/stdc++.h>
using namespace std ; 
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fast ios_base:: sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define endl "\n"
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,pair< int , int> >  
long long MOD  = 1e9+7;


signed main(){
    fast;
    int a,b; cin >> a >> b;
    if(2*b>=a){
    	cout << 0 << endl;
    }
    else{
    	cout << a-2*b << endl;
    }
}


Measured memory_bytes: 256
// Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int x, y;
		cin >> x >> y;

		if(x==0&&y==0)
			break;

		int X, Y;
		if(x>=y){
			X = x;
			Y = y;
		}
		else{
			X = y;
			Y = x;
		}

		int cnt = 0;
		do{
			X = X%Y;

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

			cnt++;
		}while(Y!=0);

		cout << X << ' ' << cnt << '\n';
	}

	return 0;
}

Measured memory_bytes: 0
using System;

namespace ABC052WackAndTeleport
{
    class Program
    {
        static void Main(string[] args)
        {
            int N;
            long A, B;
            string[] vals = Console.ReadLine().Split(' ');
            N = int.Parse(vals[0]);
            A = long.Parse(vals[1]);
            B = long.Parse(vals[2]);
            long[] X = new long[N];
            vals = Console.ReadLine().Split(' ');
            for (int i = 0; i < N; i++)
                X[i] = long.Parse(vals[i]);

            long totalCost = 0;
            long walkCost;
            for(int i=0; i< N - 1; i++)
            {
                walkCost = (X[i + 1] - X[i]) * A;
                if (walkCost > B)
                    totalCost += B;
                else
                    totalCost += walkCost;
            }
            Console.WriteLine(totalCost);
        }
    }
}

Measured memory_bytes: 18912
#include<bits/stdc++.h>
#define ull unsigned long long
#define lowbit(x) ((x)&(-x))
#define dis(p,q) sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y))

#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef double db;
using namespace std;

namespace _{
    bool rEOF = 1;//为0表示文件结尾
    inline char nc(){
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2&&rEOF && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? (rEOF = 0, EOF) : *p1++;
    }
    template<class _T>
    inline bool read(_T &num){
        char c = nc(), f = 1; num = 0;
        while (c<'0' || c>'9')c == '-' && (f = -1), c = nc();
        while (c >= '0'&&c <= '9')num = num * 10 + c - '0', c = nc();
        return (bool)(num *= f);
    }
    inline bool need(char &c){ return c >= 'a'&&c <= 'z' || c >= 'A'&&c <= 'Z'; }//读入的字符范围
    inline bool read_str(char *a){
        while ((*a = nc()) && need(*a) && rEOF)++a;
        *a = '\0'; return rEOF;
    }
}using namespace _;

const int N = 2e5+10;		//复杂度O(n)
const ll mod = 1e9 + 7;
int F[N+5], Finv[N+5], inv[N+5];//F是阶乘，Finv是阶乘的逆元
//X 关于 mod 的逆元为 x^(mod - 2);
void init(){
	F[0] = Finv[0] = inv[1] = 1;
	for (register int i = 2; i <= N; i++)
		inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
	for (register int i = 1; i <= N; i++){
		F[i] = F[i - 1] * 1ll * i % mod;
		Finv[i] = Finv[i - 1] * 1ll * inv[i] % mod;
	}
}
int comb(int n, int m){///comb(n, m)就是C(n, m)
	if (m < 0 || m > n) return 0;
	return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}

int main()
{
    ll n,m,k;
    init();
    scanf("%lld%lld%lld",&n,&m,&k);
    ll ans=0;
    for(ll i=1;i<n;i++)
    {
        ans+=(((((m*m*(n-i))%mod)*i)%mod)*comb(m*n-2,k-2))%mod;
        ans%=mod;
    }
    for(ll i=1;i<m;i++)
    {
        ans+=(((((n*n*(m-i))%mod)*i)%mod)*comb(m*n-2,k-2))%mod;
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2560
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val monsters = readLine()!!.split(" ").map { it.toInt() }.toTypedArray()
    val heroPower = readLine()!!.split(" ").map { it.toInt() }.toTypedArray()

    var killSum:Long = 0
    for (i in 0 until n) {
        killSum += Math.min(monsters[i], heroPower[i])
        val remainPower = heroPower[i] - monsters[i]

        if (remainPower > 0) {
            // 勇者パワーが余った場合、次の街のモンスターを倒す
            killSum += Math.min(monsters[i + 1], remainPower)
            if (remainPower - monsters[i + 1] > 0) {
                // 次の街でもオーバーキルだった場合、残った分を全部倒す
                monsters[i + 1] = 0
            } else {
                // 次の街で倒しきれなかった場合は、余剰勇者パワー分だけ倒す
                monsters[i + 1] -= remainPower
            }
        }

    }

    println(killSum)
}


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

#define int long long
#define mod 1000000007
#define p pair<int,int>
#define MAX 1000010

using namespace std;

int a[MAX],b[MAX];
bool vis[MAX];

vector <int> v;
vector <p> vp;
set <int> s;
set <p> sp;
map <int,int> m;
unordered_map <int,int> um;
queue <int> bq;

int32_t main()
{
    um.reserve(1<<15);
    um.max_load_factor(0.25);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin >> n >> m;

    int ans = 1;

    for(int i=1;i*i<=m;i++)
    {
        if(m%i == 0)
        {
            if(i >= n)
                ans = max(ans,m/i);

            if(m/i >= n)
                ans = max(ans,i);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
using System;
using System.Linq;
class P{
  static void Main(){
    var s=int.Parse(Console.ReadLine());
    var l=new string[s];
    l[0]=Console.ReadLine();
    char a=l[0][l[0].Length-1];
    bool f=true;
    for(int i=1;i<s;i++){
      l[i]=Console.ReadLine();
      f=f&&(l[i][0]==l[i-1][l[i-1].Length-1]);
    }
    Console.WriteLine(f&&l.Distinct().Count()==s?"Yes":"No");
  }
}

Measured memory_bytes: 13396
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long k = sc.nextLong();
		long num = 0;
		long cnt = 0;
		long temp = 0;
		int index = 0;
		long mod = 0;

		List<Long> que = new ArrayList<>();

		while(num <= 8) {
			num++;
			que.add(num);
			cnt++;
			if(cnt == k) {
				System.out.println(num);
				return;
			}
		}

		while(true) {
			temp = que.get(index);
			mod = temp%10;

			if(mod-1>=0) {
				num = temp*10 + (mod-1);
				que.add(num);
				cnt++;
				if(cnt == k) {
					System.out.println(num);
					return;
				}
			}

			num = temp*10 + (mod);
			que.add(num);
			cnt++;
			if(cnt == k) {
				System.out.println(num);
				return;
			}

			if(mod+1 < 10) {
				num = temp*10 + (mod+1);
				que.add(num);
				cnt++;
				if(cnt == k) {
					System.out.println(num);
					return;
				}
			}

			index++;
		}
	}
}


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

int main() {
  
  string s;
  cin >> s;
  
  if ( s[5] == '1' || s[6] > 52){
    cout << "TBD" << endl;
  }else{
    cout << "Heisei" <<endl;
  }
  
  
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 305
using namespace std;
 
int n, s;
string a[N];
int f() {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			if (a[i][j] != a[j][i]) return 0;
		}
	}
	return 1;
}
int main()
{
	int i, j, k;
	cin >> n;
	for (i = 0; i <n; i++) {
		cin >> a[i];
	}
	for (i = 0; i < n; i++) {
		s += f() * n;
		for (j = 0; j < n; j++) rotate(a[j].begin(), a[j].begin() + 1, a[j].end());
	}
    cout << s;
    return 0;
}

Measured memory_bytes: 384
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] arg) {

        try (Scanner scanner = new Scanner(System.in)){
            long[] in = Arrays.stream(scanner.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();
            long n = in[0];
            long a = in[1];
            long b = in[2];
            if (n * a > b) System.out.println(b);
            else System.out.println(n * a);
        }

    }
}


Measured memory_bytes: 27092
using System;

class quiz
{
    public int solve(int N, int[] A)
    {
        int now = 0;
        bool gameover = false;

        for (int i = 1; i < N + 2; i++)
        {
            now = -1;
            gameover = false;

            while (!gameover)
            {
                gameover = true;

                if (now + i >= N)
                {
                    return i;
                }

                for (int j = 1; j < i + 1; j++)
                {
                    if (A[now + j] == 0)
                    {
                        gameover = false;
                        now += j;
                        break;
                    }
                }
            }
        }

        return -1;
    }

    public int[] ParseIntBySpace(string str)
    {
        int[] array = new int[str.Length];
        int lastloc = 0, spaceloc = -1;

        for (int i = 0; i < str.Length; i++)
        {
            if (str[i] == ' ')
            {
                array[lastloc++] = int.Parse(str.Substring(spaceloc + 1, i - spaceloc - 1));
                spaceloc = i;
            }
            else if (i == str.Length - 1)
            {
                array[lastloc++] = int.Parse(str.Substring(spaceloc + 1, i - spaceloc));
            }
        }

        Array.Resize(ref array, lastloc);

        return array;
    }
}

class Example
{
    static void Main()
    {
        quiz ex = new quiz();

        //while (true)
        //{
        Console.WriteLine(ex.solve(int.Parse(Console.ReadLine()), ex.ParseIntBySpace(Console.ReadLine())));
        //}
    }
}


Measured memory_bytes: 17928
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using p = pair<int,int>;

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

  int lcm_num;
  lcm_num = lcm(X ,360);
  
  int result;
  result = lcm_num / X;
  cout << result << endl;

}

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

int main() {
  string s;
  cin >> s;
  string ans = "No";
  if (s.at(0) == s.at(1) && s.at(2) == s.at(3) && s.at(0) != s.at(2)) ans = "Yes";
  else if (s.at(0) == s.at(2) && s.at(1) == s.at(3) && s.at(0) != s.at(1)) ans = "Yes";
  else if (s.at(0) == s.at(3) && s.at(1) == s.at(2) && s.at(0) != s.at(1)) ans = "Yes";
  cout << ans << 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 ll long long
#define INF 1000000000000000000

int main(){
  int N;
  cin >> N;
  map<string, int> cnt;
  rep(i, N){
    string s;
    cin >> s;
    cnt[s] += 1;
  }
  int M;
  cin >> M;
  rep(i, M){
    string s;
    cin >> s;
    cnt[s] -= 1;
  }
  
  int max_cnt = 0;
  for (auto p : cnt) {
    max_cnt = max(max_cnt, p.second);
  }
  
  cout << max_cnt << endl;
}

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

using namespace std;

int main() {
    int n,k;
    cin >> n >> k ;
    vector<int> h(n);
    for (int i = 0; i < n; i++)
        cin >> h[i];
    sort(h.begin(), h.end());
    reverse(h.begin(),h.end());
    long long int ans = 0;
    for (int i = k; i < n; i++)
        ans += h[i];
    cout << ans << endl;

}


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

using namespace std;

int f(int n){
    if (n % 2 == 0){
        // 偶数
        return n/2;
    } else {
        // 奇数
        return 3*n + 1;
    }
}

int main(){
    int s;
    cin >> s;
    vector<int> a;

    // a_1
    a.push_back(s);
    int count = 1;

    while (true){
        int val = f(a.at(count-1));

        count++;
        for(int val_in_a: a){
            if (val == val_in_a){
                cout << count;
                return 0;
            }
        }

        a.push_back(val);

    }
}

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

int main(){
	int n;
	cin >> n;
	int ans(0);
	for(int i(1);i<=n;i += 2){
		int cnt(0);
		for(int j(1);j<=i;++j){
			if(i%j == 0) cnt++;
		}
		if(cnt == 8) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n;
  int a[1000000];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  
  int best=0,second=0;
  int number=-1;
  for(int i=0;i<n;i++){
    if(best<a[i]){
      second=best;
      best=a[i];
      number=i;
    }else if(second<a[i]){
      second=a[i];
    }
  }
  
  for(int j=0;j<n;j++){
    if(j==number) printf("%d\n",second);
    else printf("%d\n",best);
  }
  
  return 0;
}

Measured memory_bytes: 3968
#include <stdio.h>
#include <stdlib.h>

int main(void){
	int m,n,ans;
	scanf("%d %d",&m,&n);
	ans=(m-n)*100+n*1900;
	if(n==1){
		printf("%d\n",ans*2);
	}else if(n==2){
		printf("%d\n",ans*4);
	}else if(n==3){
		printf("%d\n",ans*8);
	}else if(n==4){
		printf("%d\n",ans*16);
	}else if(n==5){
		printf("%d\n",ans*32);
	}
	return 0;
}


Measured memory_bytes: 128
import math
N,Q = list(map(int,input().split(" ")))
S = input()
nums = [0] * len(S)
for i,(s1,s2) in enumerate(zip(S[:-1],S[1:])):
    if s1 == "A" and s2 == "C":
        nums[i+1] += nums[i] + 1
    else:
        nums[i+1] += nums[i]
ls = []
rs = []
for i in range(Q):
    l,r = list(map(int,input().split(" ")))
    l -= 1
    r -= 1
    ls.append(l)
    rs.append(r)
for l,r in zip(ls,rs):
    print(nums[r]-nums[l])


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

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

    for(int i = 1;i < n;i++){
        for(int k = 0;k < n - 1;k++){
            cout << a[k] << " ";
        }
        cout << a[n - 1] << endl;
        int v = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > v){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = v;
    }

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

    return 0;
}


Measured memory_bytes: 3104
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const ll INF = 1e9;
inline ll read() {
	ll X = 0,w = 0 ;
	char ch = 0;
	while(!isdigit(ch)) {
		w |= ch == '-';
		ch = getchar();
	}
	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
	return w ? -X : X;
}
ll dat[100005];
pair<ll,ll> p[100005];
ll sz[100005];
ll from[100005];
ll to[100005];
ll n;
int main() {
	cin>>n;
	for(ll i=0; i<n; i++) {
		cin>>dat[i];
		p[i]=make_pair(dat[i],i);
	}
	sort(p,p+n);
	ll id=0;
	ll sum=0;
	for(int i=0; i<n; i++) {
		sz[i]=1;
	}
	for(ll i=n-1; i>=1; i--) {
		ll curid=p[i].second;
		ll tmp=p[i].first;
		ll nx=n-2*sz[curid];
		if(nx<=0) {
			cout<<-1<<endl;
			return 0;
		}
		ll pos=lower_bound(p,p+n,make_pair(tmp-nx,0LL))-p;
		if(p[pos].first!=tmp-nx) {
			cout<<-1<<endl;
			return 0;
		}
		from[id]=p[i].second;
		to[id++]=p[pos].second;
		sum+=sz[curid]*(n-sz[curid])*2;
		sz[p[pos].second]+=sz[curid];
	}
	ll ans=0;
	for(ll i=0; i<n; i++) {
		ans+=dat[i];
	}
	if(sum!=ans) {
		cout<<-1<<endl;
		return 0;
	}
	for(ll i=0; i<id; i++) {
		cout<<from[i]+1<<" "<<to[i]+1<<endl;
	}
	return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int A[3];
	rep(i, 0, 3)
	{
		cin >> A[i];
	}

	sort(A, A + 3);

	cout << A[0] + A[1] << endl;

	return 0;
}

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

using namespace std;
typedef long long ll;

int main() {
    long long n;
    cin >> n;
    set<ll> s;
    for(ll i=2;i<=sqrt(n);i++){
        if(n % i == 0){
            ll nx = n;
            while(nx % i == 0)nx /= i;
            if(nx % i == 1)s.insert(i);
        }
    }
    n--;
    for(ll i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            s.insert(i);
            s.insert(n / i);
        }
    }
    s.insert(n);
    s.insert(n + 1);
    if(n == 1)cout << "1\n";
    else cout << s.size() << '\n';

    return 0;
}


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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    sort(p.begin(), p.end(), greater<int>());
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += p[i];
    }
    int result = sum - (p[0] / 2);
    cout << result << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	int A[n];

	for(int i = 0; i < n; i++) scanf("%d",&A[i]);

	for(int i = n-1; i > 0; i--) printf("%d ",A[i]);
	printf("%d\n",A[0]);
}


Measured memory_bytes: 2748
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

s, t = Ss()
a, b = Is()
u = S()

if u == s:
    print("{} {}".format(a-1, b))
else:
    print("{} {}".format(a, b-1))


Measured memory_bytes: 65004
def bubbleSort(numlist):
    n = len(numlist)
    flag = True
    for i in range(n):
        if flag is False:
            break
        flag = False
        for j in range(n - 1, i, -1):
            if numlist[j][1] < numlist[j - 1][1]:
                numlist[j], numlist[j - 1] = numlist[j - 1], numlist[j]
                flag = True

def selectionSort(numlist):
    n = len(numlist)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if numlist[min_index][1] > numlist[j][1]:
                min_index = j
        
        if min_index != i:
            numlist[min_index], numlist[i] = numlist[i], numlist[min_index]

def print_numlist(numlist):
    if len(numlist) == 1:
        print(numlist[0])
    else:
        n = len(numlist)
        for i in range(n - 1):
            print(numlist[i], end=' ')
        print(numlist[-1])

if __name__ == '__main__':
    n = int(input())
    numlist = [num for num in input().replace('\n', '').split(' ')]
    numlist2 = numlist.copy()
    bubbleSort(numlist)
    print_numlist(numlist)
    print('Stable')
    selectionSort(numlist2)
    print_numlist(numlist2)
    flag = True
    for i in range(len(numlist)):
        if numlist[i] != numlist2[i]:
            flag = False
            break
    if flag:
        print('Stable')
    else:
        print('Not stable')


Measured memory_bytes: 5616