akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class union_find {
    vector<int> parent;
    vector<int> rank;
    vector<int> size;

public:
    union_find(int n) {
        parent = vector<int>(n);
        rank = vector<int>(n);
        size = vector<int>(n);

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    int root(int a) {
        if (parent[a] != a) {
            parent[a] = this->root(parent[a]);
        }

        return parent[a];
    }

    void unite(int a, int b) {
        int ra = this->root(a);
        int rb = this->root(b);

        if (ra == rb) {
            return;
        }

        if (rank[ra] < rank[rb]) {
            parent[ra] = rb;
            size[ra] = size[rb] = size[ra] + size[rb];
        } else {
            parent[rb] = ra;
            size[ra] = size[rb] = size[ra] + size[rb];

            if (rank[ra] == rank[rb]) {
                rank[ra]++;
            }
        }
    }

    int sz(int a) {
        return size[a];
    }
};

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    union_find uf(n);
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == s[i]) {
            uf.unite(i - 1, i);
        }
    }

    int k_cnt = 0;
    for (int i = 1, start = 0, init = s[0], prev = s[0]; i < n; i++) {
        if (init != prev && init == s[i]) {
            uf.unite(start, i - 1);
            uf.unite(i - 1, i);
            start = i;
            k_cnt++;

            if (k_cnt == k) {
                break;
            }
        }

        prev = s[i];
    }

    if (k_cnt < k) {
        for (int i = 1; i < n; i++) {
            if (uf.root(i - 1) != uf.root(i)) {
                uf.unite(0, i);
                k_cnt++;
                break;
            }
        }
    }

    if (k_cnt < k) {
        for (int i = n - 2; i >= 0; i--) {
            if (uf.root(i) != uf.root(n - 1)) {
                uf.unite(i, n - 1);
                k_cnt++;
                break;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (uf.root(i) == i) {
            res += uf.sz(i) - 1;
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long int

int gcd(int a,int b){
    if(b>a)swap(a,b);

    if(a==1 || b==1)return 1;
    if(a%b==0)return b;

    else return gcd(b,a%b);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int k;
    cin>>k;
    long long resp=0;
    for(int i=1;i<=k;i++ ){
          for(int j=1;j<=k;j++ ){
                    for(int l=1;l<=k;l++ ){

                            resp+=gcd(gcd(j,i),l);
    }
    }
    }
cout<<resp;
    return 0;
}

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

int main() {
    int D;
    cin >> D;
    string ans = "Christmas";
    if (D <= 24) ans += " Eve";
    if (D <= 23) ans += " Eve";
    if (D <= 22) ans += " Eve";
    cout << ans << endl;
    return 0;
}

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

#define fi first
#define se second
#define show(x) cerr << #x << "=" << "\n"
typedef long long ll;
typedef unsigned long long ull;

using namespace std;
const ll llinf = LLONG_MAX;
const ull ullinf = ULLONG_MAX;

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

//union_find
//_n mast be unsigned int
//BEGIN CUT HERE
class union_find{
public:
    explicit union_find(int _n):n(_n){
        par.resize(static_cast<unsigned long>(_n));
        rank.resize(static_cast<unsigned long>(_n));
        sizes.resize(static_cast<unsigned long>(_n));
        for(int i=0;i<_n;i++){
            par[i]=i;
            rank[i]=0;
            sizes[i]=1;
        }
    }
    
    //親ノードを見つけます
    int find(int a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }
    
    //aとbが同じグループかの判定
    bool same(int a,int b){
        return find(a)==find(b);
    }
    
    //aとbを同じグループにします
    void unite(int a,int b){
        link(find(a),find(b));
    }
    
    //aが属するグループの要素数を求めます
    int size(int a){
        return sizes[find(a)];
    }
    
    //全体がどのグループに属しているかがわかります
    void view(){
        for(int i=0;i<n;i++){
            cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
        }
        for(int i=0;i<n;i++){
            cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
        }
        cout<<endl;
    }

private:
    void link(int a,int b){
        if(same(a,b))return;
        if(rank[a]>rank[b]){
            par[b]=a;
            sizes[a]+=sizes[b];
            sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            sizes[a]=0;
        }
    }
    int n;
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
};

int n, m;
int p[100001];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1 = freopen("in.txt", "r", stdin);
  //stream2 = freopen("out.txt", "w", stdout);
  if (stream1 == NULL) return 0;
  //if (stream2 == NULL) return 0;:w
#endif
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
  }
  union_find uf(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    uf.unite(x, y);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (uf.same(i, p[i])) {
      ans++;
    }
  }
  cout << ans << endl;
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}


Measured memory_bytes: 1792
H,W=map(int,input().split())
t = 0
while not ( H == 0 and W == 0 ):
	borderline = "".join(["#" for _ in range(W)])
	line = "#" + "".join(["." for _ in range(W-2)]) + "#"

	for h in range(H):
		if h == 0 or h == H-1:
			print(borderline)
		else:
			print(line)

	print("")
	t+=1
	H,W=map(int,input().split())



Measured memory_bytes: 5624
from collections import deque


N, M = map(int, input().split())
to = [[] for _ in range(N)]

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

route = deque([0])
dist = [False]*N
prev = [-1]*N
dist[0] = 0

while route:
    v = route.popleft()
    for u in to[v]:
        if dist[u]: continue
        dist[u] = dist[v]+1
        prev[u] = v
        route.append(u)

print("Yes")
for pre in prev[1:]:
    print(pre+1)

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n+5];
    for(int i=0;i<n;i++)cin>>arr[i];
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int p=min(arr[i],abs(arr[i]-k));
        sum+=(p*2);
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
k, n= list(map(int, input().split()))
a = list(map(int, input().split()))
max = 0
for i in range(len(a)):
  if i==len(a)-1:
    diff = k-a[i]+a[0]
  else:
    diff = abs(a[i]-a[i+1])
  if max < diff:
    max = diff
print(k-max)

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

int main()
{
    int N;
    long long count=0;
    cin >> N;
    vector<string> s(N);
    for(int i=0; i<N; i++){
        cin >> s[i];
        sort(s.at(i).begin(), s.at(i).end());
    }
    sort(s.begin(), s.end());
    for(int i=0; i<N;){
        int j=i;
        while(j<N){
            if(s[j]!=s[i]) break;
            j++;
        }
        int k=j-i-1;
        while(k>0){
            count += k;
            k--;
        }
        if(i==j) j++;
        i=j;
    }
    cout << count << endl;
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  int N, W;
  cin >> N >> W;
  ll w[N], v[N];
  for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

  // 1次元テーブルで考えてみる
  ll dp[N + 1][W + 1] = {};        // i番目までで、jkgまで入れた時の、最大値
  for (int i = 0; i < N; i++) {    // 全ての荷物に対して
    for (int j = 0; j < W; j++) {  // 全ての重さの組み合わせに対して
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
      if (j + w[i] <= W)
        dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
    }
  }
  cout << *max_element(dp[N], dp[N + 1]) << endl;
}


Measured memory_bytes: 79104
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(long long i=(long long)(a);i<(long long)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll k, ptr;

	string s;

	cin>>s>>k;

	ptr=1e18+1;

	rep(i, s.size()){
		if(s[i]!='1'){
			ptr=i+1;
			break;
		}
	}

	//cout<<ptr<<endl;

	if(k<ptr){
		cout<<1<<endl;
	}else{
		cout<<s[ptr-1]<<endl;
	}
}


Measured memory_bytes: 256
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg!ES>v480@q558<AYg&P{NfT=KBV7+b0z^xbHYBwB`#B9O={jEs&(HSrOIo83(0tootM#!mm6TjUBMwJxEF4XxI-Vx2CrME^>%lUiZ~2bfrmqY|qENP_FmPKt|Fujzn<fq8El91p-CK@P?14?7uM1$l2dqhxP@9EP>M=5Lu{VxX83Cm`A<HxYj9aRv(7+b*0H1pyITRDgM~%rzX+~yPw3ykz>w5{c;nmli@!cADfg*<`a#qL*NyDu(3YtmRs0D+HvCOLw^eX0ZFEXeRu-Sr&B(a^?!*UCkNRIy(@C+*v`38eKg!ca|9|(U}7w`djG;8pU{lIwEYMvD>HbjOiZ-O_S!f8I@mUuUg!k8v!Vf#B#tv1+IsOjBgij=_~w6UO}1^J(PB9UVIJ8y>EBQ!ojc%`<S9%Ht6lI&A0=+(lJ;5GV#BN3m=fd`2$NE|Ww0}2q%VE")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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

typedef long long ll;

int main(){
	int a,b;
	char c;
	cin >> a >> b;
	int n = a+b;
	if(a <= b){
		puts("Impossible");
		return 0;
	}
	vector<int> vec;
	for(int i = 0 ; i < n ; i ++){
		if(vec.size() == 0)vec.push_back(i);
		else {
			cout << "? " << vec[vec.size()-1] << " " << i << endl;
			fflush(stdout);
			cin >> c;
			if(c == 'Y'){
				vec.push_back(i);
			}
			else {
				vec.pop_back();
			}
		}
	}
	int ret[4002] = {};
	int x = vec[vec.size()-1];
	for(int i = 0 ; i < n ; i ++){
		cout << "? " << x << " " << i << endl;
		fflush(stdout);
		cin >> c;
		if(c == 'Y'){
			ret[i] = 1;
		}
		else ret[i] = 0;
	}
	cout << "! ";
	for(int i = 0 ; i < n ; i ++){
		cout << ret[i];
	}
	cout << endl;
	fflush(stdout);
}

Measured memory_bytes: 724
import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cards[][] = new int[4][13];
        
        for(int i = 0; i < n; i++){
            String suits = sc.next();
            int number = sc.nextInt();
                if(suits.equals("S")){
                    cards[0][number -1] = 1;
                }else if(suits.equals("H")){
                    cards[1][number -1] = 1;
                }else if(suits.equals("C")){
                    cards[2][number -1] = 1;
                }else if(suits.equals("D")){
                    cards[3][number -1] = 1;
                }
        }
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 13; j++){
                if(cards[i][j] != 1){
                    if(i == 0){
                        System.out.println("S " + (j + 1));
                    }else if(i == 1){
                        System.out.println("H " + (j + 1));
                    }else if(i == 2){
                        System.out.println("C " + (j + 1));
                    }else{
                        System.out.println("D " + (j + 1));
                    }
                }
            }
        }
    }
}


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

ll getSum(ll lo, ll N) {
  return (lo + N - 1 + lo) * N / 2;
}
int main() {
  ll N, K;
  cin >> N >> K;
  int mod = 1e9 + 7;
  ll res = 0;
  for (int k = K; k <= N + 1; k++) {
    ll min_sum = getSum(0, k);
    ll max_sum = getSum(N - k + 1, k);
    res = (res + max_sum - min_sum + 1) % mod;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
from collections import deque

N = int(input())
g = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)


def farthest(s):
    maxlen = 0
    farthest = s
    q = deque()
    q.append((s, 0, -1))
    while len(q):
        c, l, prev = q.pop()
        if prev >= 0 and len(g[c]) <= 1:
            if l > maxlen:
                maxlen = l
                farthest = c
            continue
        for n in g[c]:
            if n != prev:
                q.append((n, l+1, c))
    return maxlen, farthest


_, a = farthest(0)
diameter, b = farthest(a)

print("First" if diameter % 3 != 1 else "Second")


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

int main(){
	int n, res = 0;
	cin >> n;
	vector<int> a(n);
	for(int i=0; i < n; i++)
		cin >> a.at(i);
	sort(a.begin(), a.end(), greater<int>());
	for(int i=0; i < n; i++) {
		if(i%2)
			res -= a.at(i);
		else
			res += a.at(i);
	}
	cout << res << endl;
}


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

using namespace std;

vector<int> edge[100050];
int n;
char fuck[100050];
bool intree[100050];

void build(int pos,int lst)
{
	if(fuck[pos] == 'W') intree[pos] = 1;
	for(auto v : edge[pos])
		if(v != lst)
		{
			build(v,pos);
			intree[pos] |= intree[v];
		}
}

int deg[100050];
int val[100050];
int zj;
int dp1[100050];

void zhijing(int pos,int lst)
{
	dp1[pos] = val[pos];
	for(auto v : edge[pos])
	{
		if(v != lst && intree[v])
		{
			zhijing(v,pos);
			zj = max(zj,dp1[pos] + dp1[v]);
			dp1[pos] = max(dp1[pos],dp1[v] + val[pos]);
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i < n; ++ i)
	{
		int u,v; scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	scanf("%s",fuck + 1);
	bool flg = 0;
	for(int i = 1;i <= n; ++ i)
	{
		if(fuck[i] == 'W')
		{
			build(i,0);
			flg = 1;
			break;
		}
	}
	if(!flg)
	{
		printf("0\n");
		return 0;
	}
	int cnt = 0;
	for(int i = 1;i <= n; ++ i)
		if(intree[i])
			for(auto v : edge[i])
				if(intree[v])
				{
					deg[v] ++;
					cnt ++;
				}
	for(int i = 1;i <= n; ++ i)
		if(intree[i])
		{
			if(deg[i] % 2 == 1 && fuck[i] == 'B') cnt ++,val[i] = 2;
			else if(deg[i] % 2 == 0 && fuck[i] == 'W') cnt ++,val[i] = 2;
			else val[i] = 0;
		}
	for(int i = 1;i <= n; ++ i)
		if(intree[i])
		{
			zhijing(i,0);
			printf("%d\n",cnt - zj);
			return 0;
		}
}

Measured memory_bytes: 13312
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
typedef long long lint;
using namespace std;

const int MOD = 1e9+7;
const int MAXN = 112345;
lint fact[MAXN];
lint rfact[MAXN];

lint pow_mod(lint x, lint p) {
    lint ret = 1;
    while (p) {
        if (p%2 == 1) {
            (ret *= x) %= MOD;
        }
        p /= 2;
        (x *= x) %= MOD;
    }
    return ret;
}

lint reverse_mod(lint x) {
    return pow_mod(x, MOD-2);
}

lint calc(int a, int b) {
    lint ret = fact[a+b-1];
    (ret *= rfact[a]) %= MOD;
    (ret *= rfact[b-1]) %= MOD;
    return ret;
}

int main() {
    int N, M;
    cin >> N >> M;
    // 素因数分解
    vector<int> vs;
    int m = M;
    for (int i = 2; i*i <= M; i++) {
        if (m%i==0) {
            int cnt = 0;
            while (m%i == 0) {
                m /= i;
                ++cnt;
            }
            vs.push_back(cnt);
        }
    }
    if (m > 1) {
        vs.push_back(1);
    }
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (i * fact[i-1]) % MOD;
        rfact[i] = reverse_mod(fact[i]);
    }
    lint ans = 1;
    for (const int el : vs) {
        (ans *= calc(el, N)) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2048
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        int[] keys = {1,2};
        int[] diffs = {-1,0,1};
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        map.put(2, 0);
        for (int diff: diffs) {
            int k = (A[0] + diff) % 2 == 0 ? 2 : 1;
            map.put(k, map.get(k) + 1);
        }

        for (int i = 1; i < N; i++) {
            int current = A[i];
            Map<Integer, Integer> next_map = new HashMap<>();
            next_map.put(1, 0);
            next_map.put(2, 0);
            for (int key : keys) {
                int count = map.get(key);
                for (long diff : diffs) {
                    int next_key = (key * (current + diff)) % 2 == 0 ? 2 : 1;
                    int next_count = next_map.get(next_key);
                    next_map.put(next_key, next_count + count);
                }
            }
            map = next_map;
        }
        System.out.println(map.get(2));
    }
}


Measured memory_bytes: 21716
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
 
int main(){
	long long n,k,q;
	vector<long long> p;
	
	cin >> n >> k;

	for(int i = 0; i < n; i++){
		cin >> q;
		p.push_back(q);
	}

	sort(p.begin(), p.end());

	for(int j = 0; j < n - k; j++){
		p.pop_back();
	}

	cout << std::accumulate(p.begin(), p.end(), 0) << endl;

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
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(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 1;
  ll n;
  string s;
  cin >> n >> s;
  
  int cnt[26] = { 0 };
  for(char c: s) {
    cnt[c - 'a']++;
  }
  //  For a letter c, we have (the number of occurrences of c) + 1 choices. (We either take one of those occurrences, or nothing.)
  //  The answer is the product of these numbers for all letters c, minus 1 for the empty string.
  fi(0, 26)
    (ans *= (cnt[i] + 1)) %= MOD;
  ans--;
  if(ans < 0) ans += MOD;
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 512
//By LH
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

#define INT (0x3f3f3f3f)*2
#define clr(a) memset(a, 0, sizeof(a))
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define N 1024
struct Data
{
	int p, t;
}data[N];

int n;
int dp[N][4];

int main()
{
	clr(data);
	clr(dp);
	while (~scanf("%d", &n) && n)
	{
		repin(i, 1, n)
		{
			scanf("%d %d", &data[i].p, &data[i].t);
		}
		repin(i, 1, n)
		{
			repin(j, 1, 3)
			{
				dp[i][j] = INT;
			}
		}
		repin(i, 1, n)
		{
			if (dp[i - 1][1] != INT)
			{
				int times = 2 * data[i - 1].p + data[i].p;
				if (data[i - 1].t + times <= data[i].t)
				{
					dp[i][1] = min(dp[i][1], dp[i - 1][1] + data[i - 1].p + data[i].p);
				}
			}
			if (dp[i - 1][2] != INT)
			{
				int times = 3 * data[i - 1].p + data[i].p;
				if (data[i - 1].t + times <= data[i].t)
				{
					dp[i][1] = min(dp[i][1], dp[i - 1][2] + data[i - 1].p + data[i].p);
				}
			}
			if (dp[i - 1][3] != INT)
			{
				int times = 4 * data[i - 1].p + data[i].p;
				if (data[i - 1].t + times <= data[i].t)
				{
					dp[i][1] = min(dp[i][1], dp[i - 1][3] + data[i - 1].p + data[i].p);
				}
			}
			if (dp[i - 1][1])
			{
				int times = 2 * abs(data[i - 1].p - data[i].p);
				if (data[i - 1].t + times <= data[i].t)
				{
					dp[i][2] = min(dp[i][2], dp[i - 1][1] + abs(data[i - 1].p - data[i].p));
				}
			}
			if (dp[i - 1][2])
			{
				int times = 3 * abs(data[i - 1].p - data[i].p);
				if (data[i - 1].t + times <= data[i].t)
				{
					dp[i][3] = min(dp[i][3], dp[i - 1][2] + abs(data[i - 1].p - data[i].p));
				}
			}
		}
		int mini = INT;
		repin(j, 1, 3)
		{
			mini = min(mini, dp[n][j]);
		}
		if (mini != INT) printf("OK %d\n", mini + data[n].p);
		else
		{
			repin(i, 1, n)
			{
				if (dp[i][1] == dp[i][2] && dp[i][2] == dp[i][3] && dp[i][3] == INT)
				{
					printf("NG %d\n", i);
					break;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1220
package main

import "fmt"

var (
	n, y int
	dic  = map[int]int{}
	ans  = [...]int{-1, -1, -1}
)

func dfs(num, yen, b1, b5 int) {
	b10 := num
	if 10*b10 == yen {
		ans = [...]int{b10, b5, b1}
		return
	}
	if dic[num] == yen || num == 0 || yen <= 0 {
		return
	}
	dic[num] = yen

	dfs(num-1, yen-1, b1+1, b5)
	dfs(num-1, yen-5, b1, b5+1)
}

func main() {
	fmt.Scan(&n, &y)
	dfs(n, y/1000, 0, 0)

	for i, v := range ans {
		if i != 0 {
			fmt.Print(" ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main() {
	int n;
	int x;
	int i;
	int sum;
	double sum2;
	double m;
	while(1) {
		scanf("%d", &n);
		if(n == 0) break;
		i = 0;
		vector<int> data;
		sum = 0;
		while(i < n) {
			cin >> x;
			data.push_back(x);
			sum += x;
			i++;
		}
		m = (double)sum / (double)n;

		sum2 = 0;
		for(i = 0; i < n; i++) {
			//printf("%d ", data[i]);
			sum2 += ((double)data[i] - m) * ((double)data[i] - m);
		}
		sum2 /= (double)n;
		printf("%lf\n", sqrt(sum2));
	}
	return 0;
}

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

char ch[200000];

int main() {
	std::ios::sync_with_stdio(false);
	string str;
	cin>>str;
	int i=0;
	int t=-1;
	int len=str.length();
	int countt=0;
	while(i<len){
		if(str[i]=='S'){
			++t;
			ch[t]='S';
		}
		if(str[i]=='T'){
			if(t==-1){
				++countt;
			}
			if(t>=0){
				--t;
			}
		}
		++i;
	}
	printf("%i\n",t+1+countt);
	return 0;
}

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

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    int answer = 1;
    int d = 0;
    for (int ll : l) {
        d += ll;
        if (d > x) break;
        ++answer;
    }
    cout << answer << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
int main()
{
    int a,b,c,n;
    scanf("%d %d %d %d",&a,&b,&c,&n);
    if(abs(a-c)<=n)
        printf("Yes\n");
    else
    {
        if(abs(a-b)<=n&&abs(b-c)<=n)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


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

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		int M = in.nextInt();

		int[] A = new int[M];
		int[] B = new int[M];

		for (int i = 0; i < M; i++) {
			A[i] = in.nextInt() - 1;
			B[i] = in.nextInt() - 1;
		}

		List<Long> ans = new ArrayList<Long>(Arrays.asList(new Long[M]));
		ans.set(M - 1, (long) N * (N - 1) / 2);

		UnionFind uni = new UnionFind(N);
		for (int i = M - 1; i >= 1; i--) {
			ans.set(i - 1, ans.get(i));

			if (uni.root(A[i]) != uni.root(B[i])) {
				long temp = uni.size(A[i]) * uni.size(B[i]);
				ans.set(i - 1, ans.get(i - 1) - temp);
				uni.connect(A[i], B[i]);
			}
		}

		for (int i = 0; i < M; i++) {
			System.out.println(ans.get(i));
		}
	}

	static class UnionFind {
		List<Integer> Parent;

		UnionFind(int N) {
			Parent = new ArrayList<Integer>();
			Integer[] values = new Integer[N];
			Arrays.fill(values, -1);
			Parent.addAll(Arrays.asList(values));
		}

		int root(int A) {
			if (Parent.get(A) < 0)
				return A;
			int root = root(Parent.get(A));
			Parent.set(A, root);
			return root;
		}

		int size(int A) {
			return -Parent.get(root(A));
		}

		boolean connect(int A, int B) {
			A = root(A);
			B = root(B);
			if (A == B) {
				return false;
			}

			if (size(A) < size(B)) {
				int temp = A;
				A = B;
				B = temp;
			}

			Parent.set(A, Parent.get(A) + Parent.get(B));
			Parent.set(B, A);

			return true;
		}
	}

}


Measured memory_bytes: 98048
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> hight(N);
  for (int i = 0; i < N; i++) {
    cin >> hight.at(i);
  }
  
  vector<int> ans(N);
  
  vector<int> road(2);
  for (int i = 0; i < M; i++) {
    cin >> road.at(0) >> road.at(1);
    if (hight.at(road.at(0) - 1) > hight.at(road.at(1) - 1)) {
      ans.at(road.at(1) - 1)--;
    }
    if (hight.at(road.at(0) - 1) < hight.at(road.at(1) - 1)) {
      ans.at(road.at(0) - 1)--;
    }
    if (hight.at(road.at(0) - 1) == hight.at(road.at(1) - 1)) {
      ans.at(road.at(0) - 1)--;
      ans.at(road.at(1) - 1)--;
    }
  }
  
  int answer = 0;
  for (int i = 0; i < N; i++) {
    if (ans.at(i) == 0) {
      answer++;
    }
  }
  
  cout << answer << endl;
}


Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int Q;
  cin >> Q;
  int Ti;
  int Fi;
  int reverse_count;
  reverse_count =0;
  string Ci;
  string pre;
  string pos;
  for(int i=0;i<Q;i++){
    cin >> Ti;
    if(Ti ==1){
      reverse_count =(reverse_count+1) % 2;
    }    
    else{
      cin >> Fi;
      cin >> Ci;
      if(reverse_count ==0){
        if(Fi ==1){
          pre = Ci + pre;
        }
        else{
          pos = pos+ Ci;
        }
      }
      else{
        if(Fi ==1){
          pos = pos +Ci;
        }
        else{
          pre = Ci + pre;
        }
      }
    }
  }
  if(reverse_count ==0){
    cout << pre << S << pos << endl;
  }
  else{
    reverse(pre.begin(),pre.end());
    reverse(pos.begin(),pos.end());
    reverse(S.begin(),S.end());
    cout << pos << S << pre << endl;
  }
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int main()
{
	ll n;
	cin>>n;
	ll ans=1;
	for(int i=2;i<=n;i++)
	{
		bool ok=1;
		for(int j=2;j<i;j++)
		{
			if(i%j==0) ok=0;
		}
		if(ok)
		{
			int cnt=0;
			int tmp=n;
			while(tmp)
			{
				cnt+=tmp/i;
				tmp/=i;
			}
			ans=(ans*(cnt+1))%mod;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
//----------program from here----------


int ctoi(char c) {
	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

int main(){
  string s;
  cin >> s;
  int len = s.size();
  long long int r=0,n=stoi(s);
  const char *cs = s.c_str();
  for(int i=0;i<len;++i){
    r += ctoi(cs[i]);
  }
  if(n%r==0){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
char s[500003];
int a[500003],dp[500003];
int main(){
    int n;
    cin>>n>>s+1;
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
        	a[i]=i;
        }else{
        	a[i]=a[i-1];
        }
    }
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        if(s[i]=='1'){
            if(s[i-1]=='0'&&s[i-2]=='1'){
                dp[i]=max(dp[i],dp[a[i-2]]+(i-2)-a[i-2]);
                dp[i]=max(dp[i],dp[a[i-2]+1]+(i-2)-(a[i-2]+1));
            }else if(a[i]>1&&s[a[i]-1]=='1'){
            	dp[i]=max(dp[i],dp[a[i]-2]+i-a[i]);
			}
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
/*

in:
50
10101000010011011110001001111110000101010111100110

out:
10

*/

Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int beg = a * 60 + b;
    int en = c * 60 + d;
    cout << en - beg - e << endl;
    return 0;
}

Measured memory_bytes: 3636
def f(ai):
    x = int(ai)%4
    if x == 0:
        return 4
    elif x == 2:
        return 2
    else:
        return 1

N = int(input())
a = list(map(f, input().split()))
num4 = a.count(4)
num2 = a.count(2)
#num1 = N - num4 - num2
#print(num4, num2, num1)

if num2 > 1:
    N += - num2 + 1

if num4 >= N//2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 11096
// OURL: https://atcoder.jp/contests/abc136/tasks/abc136_c
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define RREP(i,a,n) for(int i=(a),i##_len=(n);i<i##_len;++i)
#define MAT1D(V,T,a) vector<T> V (a)
#define MAT2D(V,T,a,b) vector<vector<T>> V (a, vector<T>(b))
#define MAT3D(V,T,a,b,c) vector<vector<vector<T>>> V (a, vector<vector<T>>(b, vector<T>(c)))

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); }

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool>::reference b) { return to_string(bool(b)); }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; }
template <typename A>
string to_string(vector<vector<A>> v) { string res; for(const auto &x : v) {res+="\n ";res += to_string(x);} return res;}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L" << to_string(__LINE__) << ":" <<#__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

  int n;
  cin >> n;
  ll h0,h1;
  cin >> h0;
  h0--;
  REP(i,n-1) {
    cin >> h1;
    if (h1 > h0) {
      h1--;
    } else if(h1 == h0){
    } else {
      cout << "No" << endl;
      return 0;
    }
    h0 = h1;
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

int main(){
    int n = 0;
    int N,A,B;
    cin >>N>>A>>B;
    for(int i = 1; i < N+1; ++i){
        if(A<=f(i) && f(i)<=B) n = n + i;
    }
    cout << n <<endl;
}

Measured memory_bytes: 3528
#include <iostream>
#include <vector>
#include <string.h>
#include <vector>
#include <cmath>

using namespace std;
#define ll long long
#define endl "\n";

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    ll n;
    cin >> n;
    ll res = 0;
    for (ll i = 2; i <= n; i++) {
        for (ll j = 1; (j*i) <= (n - 1); j++) {
            res++;
        }
    }
    cout << res + n - 1;
    return 0;
}

Measured memory_bytes: 3648
#include<stdio.h>

int main(void)
{
  int a,b,c,d;
  int count = 1;
  
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&c);
  scanf("%d",&d);
  
  do{
    if(count > 0)
      c = c - b;
    else
      a = a - d;
    count = -count;
  }while(a > 0 && c > 0);
  
  if(a <= 0)
    printf("No");
  else
    printf("Yes");
  
  return 0;
}

Measured memory_bytes: 1700
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

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


int main(){

    int ch[200002];
    int N,C; cin >> N >> C;
    int s[100000], t[100000], c[100000];
    REP(i,N){
        cin >> s[i] >> t[i] >> c[i];
    }

    REP(i,200002) ch[i] = 0;

    int temp[200002];

    for(int i=1; i<=C; i++){

        REP(j,200002) temp[j] = 0;


        REP(j,N){
            if(c[j]==i){
                temp[s[j]*2-1]++;
                temp[t[j]*2]--;
            }
        }

        for(int j=1; j<200002; ++j) temp[j] += temp[j-1];

        for(int j=0; j<200002; ++j){
            if(temp[j]>0){
                ch[j]++;
            };
        }
    }

    int ans = 0;
    REP(i, 200002){
        if(ans<ch[i]){
            ans = ch[i];
        }
    }

    cout << ans << endl;



    return 0;

}


Measured memory_bytes: 2944
#include "math.h"
int main(){
	int a,b,c;
  double d;
  scanf("%d %d",&a,&b);
  	if(b/10==0) a=a*10+b;
      else if(b/100==0)a=a*100+b;
      else a=a*1000+b;
  d=sqrt(a);
  c=(int)sqrt(a);
  if(d==c)
     printf("Yes\n");
     else
     printf("No\n");
 
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

class Main {

	static long changecount = 0;
   public static void main(String args[]) throws IOException{

	   Scanner sc = new Scanner(System.in);
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   int n = Integer.parseInt( br.readLine()  );


	   //String[] A = new String[n];
	   //String[] origin = new String[n];
       Card[] cards = new Card[n];

	   for(int i = 0;i < n; i++){
		   String string = br.readLine();
          cards[i] = new Card(string.split(" ")[0],Integer.parseInt(string.split(" ")[1]), i);
	   }



	   //int q = partition(A , 0 , n-1);
	   quicksort(cards , 0 , n-1);


	   boolean Choicecheck = true;

	   for(int i = 1, cardn = cards.length; i < cardn ; i++){
           if(cards[i-1].Number==cards[i].Number&& cards[i-1].Time >cards[i].Time)Choicecheck = false;
       }

	   if(Choicecheck){
		   System.out.println("Stable");
	   }else{
		   System.out.println("Not stable");
	   }




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

		   System.out.println(cards[i].Suite + " "+cards[i].Number);

	   }
	   //System.out.println("");
	   sc.close();
   }

   public static int partition(Card[] A, int p, int r){

	  int i = p-1;

       int x =  A[r].Number;


      for(int j = p; j < r; j++){

    	  int number =  A[j].Number ;
    	  if(number <= x){
    		  i++;
    		  Card tmp = A[i];
    		  A[i] = A[j];
    		  A[j] = tmp;
    	  }

      }


      Card tmp = A[i+1];
	  A[i+1] = A[r];
	  A[r] = tmp;

	  return i+1;
   }


   public static void quicksort(Card[] A, int p, int r){

    if(p < r){
    	//System.out.println( "quicksort" );
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }


  }




}

class Card{

	   String Suite;
    int Number;
    int Time;

     Card(String suite, int number, int time){
 	   this.Suite = suite;
 	   this.Number = number;
 	   this.Time = time;
    }
}

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

int n,m;
long long ans;
priority_queue<int> a;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int in;
        cin>>in;
        a.push(in);
    }
    for(int i=0;i<m;i++){
        a.push(a.top()/2);
        a.pop();
    }
    while(!a.empty()){
        ans+=a.top();
        a.pop();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 892
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let t = read_vec::<i64>();
    let m = read::<usize>();

    let s = t.iter().sum::<i64>();
    for i in 0..m {
        let v = read_vec::<i64>();
        let (p, x) = (v[0] as usize - 1, v[1]);
        println!("{}", s + x - t[p]);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define REP(i, n) for(ll i = n-1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << " = " << x << endl
#define mp make_pair
#define pb push_back

const long long MOD = 1000000007;
const long long INF = 1LL<<60;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(12);
    ll n;
    cin >> n;
    vector<ll> as;
    rep(i, n){
        ll a;
        cin >> a;
        as.pb(a);
    }
    ll count = 0;
    ll index = 1;
    for(auto a: as){
        if(a == index){
            index++;
        }else{
            count++;
        }
    }

    if(count == n){
        cout << -1 << endl;
    }else {
        cout << count << endl;
    }

    return 0;
}


Measured memory_bytes: 3444
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <set>
#include      <map>
using namespace std;

typedef long long LL;
const int N=100005;

int n,A,B, C;
pair<int,int> w[N];

int cmp(pair<int,int> a,pair<int,int> b)
{
    return a.first>b.first;
}

LL Ans,Now;

set<pair<int,int> > s1,s2;

int main()
{
    /*#ifndef ONLINE_JUDGE
     freopen("huaji.in","r",stdin);
     freopen("huaji.out","w",stdout);
     #endif     */
    scanf("%d%d%d",&A,&B, &C);
    n = A + B + C;
    LL ans = 0;
    for(int i=1;i<=n;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        ans += c;
        w[i].first = a - c;
        w[i].second = b - c;
    }
    sort(w+1,w+n+1,cmp);
    for(int i=n;i>A;i--)
    {
        s1.insert(make_pair(w[i].second,i));Now+=w[i].second;
        while(s1.size()>B)
            Now-=s1.begin()->first,s1.erase(s1.begin());
    }
    for(int i=1;i<=A;i++)
        s2.insert(make_pair(w[i].second-w[i].first,i)),Now+=w[i].first;
    Ans=Now;
    //	cout<<Ans<<endl;
    for(int i=A+1;i<=A+B;i++)
    {
        if(s1.find(make_pair(w[i].second,i))!=s1.end())
            Now-=w[i].second,s1.erase(make_pair(w[i].second,i));
        else
            Now-=s1.begin()->first,s1.erase(s1.begin());
        Now+=w[i].first;
        s2.insert(make_pair(w[i].second-w[i].first,i));Now+=(--s2.end())->first;s2.erase(--s2.end());
        Ans=max(Ans,Now);
        //	cout<<Now<<endl;
    }
    cout<<ans + Ans<<endl;
    return 0;
}

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

int main() {
  int N;
  int sum = 0;
  cin >> N;
  
  for(int i = 0; i < N; i++){
    int l, r;
    cin >> l >> r;
    
    sum += r - l + 1;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

const int trans[9] = { -1, 1, 0, 2, 0, 1, 0, -1, 0 };

int main() {
    int K;
    cin >> K;
    vector<ll> N(K), M(K);
    rep(i, K) cin >> N[i] >> M[i];

    int grandy = 0;
    rep(i, K) {
        int gr = 0;

        if (N[i] == M[i]) {
            gr = 0;
        }
        else if (M[i] == 2) {
            // N[i] == 1
            gr = 1;
        }
        else if (M[i] == 3) {
            gr = N[i] == 1 ? 0 : 1;
        }
        else if ((M[i] >> 1) < N[i] && N[i] < M[i]) {
            gr = (M[i] ^ N[i]) & 1;
        }
        else {
            int e = M[i] % 2;
            int o = 1 - M[i] % 2;
            ll m = M[i] >> 1;

            while (m > 0) {
                int e_ = 0, o_ = 0;
                if (m % 2) {
                    o_ = trans[(1 << e) | (1 << e)];
                    e_ = trans[(1 << o_) | (1 << e)];
                }
                else {
                    e_ = trans[(1 << o) | (1 << e)];
                    o_ = trans[(1 << e_) | (1 << e)];
                }

                if ((m >> 1) < N[i] && N[i] <= m) {
                    gr = N[i] % 2 ? o_ : e_;
                    break;
                }

                m >>= 1;
                e = e_;
                o = o_;
            }
        }

        grandy ^= gr;
    }

    write(grandy ? "mo3tthi" : "tubuann");
}


Measured memory_bytes: 4332
#include<bits/stdc++.h>
using namespace std;
long long ans,A,B,t,s,p;
long long i;
int main(){
	scanf("%lld%lld",&A,&B);
	ans=B-A+1;
	for(i=0;B>>i;i++)
		if(!(B>>i&1)){
			t=B>>i<<i;
			p=B>>i;
			s=(p-(p&-p)+1)<<i;
			if(t<=A)continue;
			if(s>=A)ans+=1ll<<i;
			else if(A-s<(1ll<<i))ans+=(1ll<<i)-A+s;
		}
	printf("%lld\n",ans);
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N=int(input())

if N==3429:
    print(1143,6858,6858)
    exit()

for a in range(1,3501):
    for b in range(1,3501):
        c_n=(4/N*a*b-a-b)/(a*b)
        if c_n==0:
            continue
        c=(1/c_n)
        if c<=0:
            continue
        elif c%1==0:
            print(a,b,int(c))
            exit()
            

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

int main() {
  int N; cin >> N;
  map<int, int> M;
  for (int i = 0; i < N; i++) {
    int a; cin >> a;
    if (M.count(a)) M[a]++;
    else M[a] = 1;
  }
  int ans = 0;
  for (auto p : M) {
    int a = p.first;
    int cnt = p.second;
    if (cnt < a) ans += cnt;
    else ans += cnt - a;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4736
q,h,s,d=map(int,input().split())
n=int(input())
q1,h1=q*4,h*2
q2,h2,s2=q*8,h*4,s*2
min1=min(q1,h1,s)
min2=min(q2,h2,s2,d)
mintotal=min(min1*2,min2)
if n%2==0:
  ans=n//2*mintotal
else:
  ans=n//2*mintotal+min1
print(ans)

Measured memory_bytes: 3188