akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

vector<int> operator *(vector<int> a, vector<int> b) {
	int n = b.size();
	vector<int> res(n);
	rep(i, n) res[i] = a[b[i]];
	return res;
}

void operator *=(vector<int> &a, vector<int> b) {
	a = a * b;
}

vector<int> perm_pow(vector<int> base, ll k) {
	int n = base.size();
	vector<int> ans(n);
	rep(i, n) ans[i] = i;
	while (k) {
		if (k & 1) ans *= base;
		base *= base;
		k >>= 1;
	}
	return ans;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n; ll k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) {
		cin >> a[i]; a[i]--;
	}
	a = perm_pow(a, k);
	cout << a[0] + 1 << '\n';
}

Measured memory_bytes: 8744
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
    long long dp[2005]={},s;
	cin>>s;
	for(int i=3;i<=s;i++){
		dp[i]=1;
	}
	for(int i=3;i<=s;i++){
		for(int j=3;j<=s-3;j++){
			if(i-j>=3){
				dp[i]+=dp[j];
			}
			dp[i]%=1000000007;
		}
	}
	cout<<dp[s]<<endl;
  return(0);
}

Measured memory_bytes: 3644
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, M, S):
    ans = []
    i = N
    while i > 0:
        for j in range(max(0, i - M), i):
            if S[j] == '0':
                ans.append(i - j)
                i = j
                break
        else:
            print(-1)
            return
    print(*list(reversed(ans)))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().rstrip()
    main(N, M, S)


Measured memory_bytes: 74416
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,c,n,k,ans=0;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&n);
	for(int i=0;i<=a;i++)	
		for(int j=0;j<=b;j++)
			for(int l=0;l<=c;l++){
				k=500*i+100*j+50*l;
				if(k==n) ++ans;
				if(k>n) break;
			}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
require 'prime'
loop do
  m, a, b = gets.split.map(&:to_i)
  break if m == 0
  ans = [0, 0]
  prod = 0
  Prime.each.take_while{ |p| p <= Math.sqrt(100000).to_i && p * p <= m }.each do |p|
    q = Prime.each.take_while{ |q| a * q <= b * p && p * q <= m }.drop_while{ |q| q < p  }.to_a.last
    if q && prod < p * q
      ans = [p, q]
      prod = p * q
    end
  end
  puts ans * ' '
end

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

int main()
{
  int d,e;

  while(1){
    cin>>d>>e;
    if(d+e==0)break;
    double ans=1e9;
    for(int i=1;i<=d;i++)ans=min(abs(sqrt(i*i+(d-i)*(d-i))-e),ans);
    printf("%.10f\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1196
import sys
 
n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
    v, d, p = q.pop()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(str, ans)))

Measured memory_bytes: 81824
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
m_A = B[0]

next_idxs = {}
for i in range(n):
    next_idxs[B[i]] = i

ans = 0
is_visited = [False] * n

for i in range(n):
    if is_visited[i]:
        continue
    cur = i
    S = 0
    n2 = 0
    m = A[i]
    while True:
        is_visited[cur] = True
        S = S + A[cur]
        m = min(m, A[cur])
        n2 = n2 + 1
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break
    ans = ans + min(m*(n2-2)+S, m + S + (n2+1)*m_A)

print(ans)


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

#define ll long long
#define ld long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vl vector<ll>
#define vll vector<pll>
#define pb push_back
#define pll pair<ll,ll>
#define sl set<ll>
#define sll set<pll>
#define mp make_pair
#define ff first
#define ss second
#define rep(i,m,n) for(ll i=(m);i<=(n);i++)
#define rem(i,m,n) for(ll i=(m);i>=(n);i--)
#define FOR(i,v) for(auto &(i) : (v))
#define ub upper_bound
#define lb lower_bound
#define mset(x,val) memset((x),(val),sizeof((x)))
#define MAP map<ll,ll>
#define MAPs map<ll,sl>
#define MAPv map<ll,vl>

const ll   INF = 0x7f7f7f7f7f7f7f7f;
const ll NINF = -INF;
const ll MAXN  = 1e+6 + 8;

int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

//<---------------------Declare global variables here------------------>//

//<---------------------Implement functions here------------------------->//



//<----------------------------Start of solve()------------------------------->//

void solve()
{
    ll n,x,t;
    cin>>n>>x>>t;

    ll y = n/x;
    y *= t;
    if(n%x)
    y+=t;

    cout<<y;

}


int main()
{
    fastio;
    ll t = 1;
    //cin>>t;
    while (t--)
    {
        solve();
    }

#ifndef ONLINE_JUDGE
    cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif

    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <iomanip>
using namespace std;
#define Would
#define you
const int INF = 999999999;
const int MOD = 1e9 + 7;

string week[] = { "mon","tue","wed","thu","fri","sat","sun" };
int main() {
	int n;
	cin >> n;
	cout << week[(n + 3) % 7] << endl;
}


Measured memory_bytes: 3224
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<limits>
#include<iomanip>
#include<cmath>
#include<climits>
using namespace std;

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

const int mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int num0=0,num1=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){
            num0++;
        }else{
            num1++;
        }
    }
    cout << min(num0,num1)*2 << endl;
    return 0;
}

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


//SHORTCUTS

#define ll long long
#define endl '\n'
#define i1(a) cin>>a
#define i2(a,b) cin>>a>>b
#define i3(a,b,c) cin>>a>>b>>c
#define o1(a) cout<<a<<endl
#define o2(a,b) cout<<a<<" "<<b<<endl
#define o3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define f(i,a,b) for(int i = a;i<b;i++)
#define fe(i,a,b) for(int i = a;i<=b;i++)
#define fi(i,a,b) for(i=a;i<b;i++)
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair


// DEBUG CODE & FAST OUTPUT

#define printv(a) for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
#define printvl(a) for (int i = 0; i < a.size(); i++) cout << a[i] << endl;
#define printa(a, n) for (int i = 0; i< n; i++) cout << a[i] << ' ';
#define printal(a, n) for (int i = 0; i < n; i++) cout << a[i] << endl;


//DATA STRUCTURES

#define pq priority_queue
#define ms multiset
// #define y0 _y0_
// #define y1 _y1_
// #define div divi

typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;

//IMP CONSTANT
const int mod = 1e9 + 7, inf = 1e9 + 7;
const ll infll = 1e18 + 7;
bool google_contest = false;


//MODULAR OPERATIONS
ll myadd(ll a,ll b){
    ll ans = a+b;
    ans-= ans>=mod ? mod : 0;
    return ans; 
}
ll mysub(ll a, ll b){
    return (a-b+mod)%mod;
}
ll mymul(ll a,ll b){
    return (a*b)%mod;
}
ll mypow(ll a, ll b){
    ll ans = 1;
    while(b>0)
        if(b&1) ans = mymul(ans,a),b--;
        else a = mymul(a,a),b >>= 1;
    return ans;
}
ll nCr(ll n,ll r){
    if(r==0)return 1;
    if(r==1)return n;
    if(n==0)return 0;
    return mymul(n,mymul(nCr(n-1,r-1),mypow(r,mod-2)));
}

//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    | 



int main(){

ios_base::sync_with_stdio(0);
cin.tie(0); 
cout.tie(0);

int t,tt;
t=1;
// i1(t);
if(google_contest)tt=1;

while(t--){

int n;
i1(n);
n = n%10;
string s;
if(n==3)s = "bon";
else if(n==0||n==1||n==6||n==8)s = "pon";
else s = "hon"; 

o1(s);
if(google_contest){
    cout<<"Case "<<tt++<<": ";
}
}

return 0;   
}


//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    |   OVER!!!!


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

const int N=1e5+10;
ll a[N<<4];
int sum[11];
main(){
    ios
    int h,w,n;scanf("%d%d%d",&h,&w,&n);
    h-=2,w-=2;
    int x;int y;
    int cnt=0;
    ll m=(ll)h*w;
    rep(iii,n){
        scanf("%d%d",&x,&y);
        rep(i,3)if( x-i>=1 && x-i<=h){
            rep(j,3)if(y-j>=1 && y-j<=w){
            a[cnt++]=((ll)(x-i)<<32)+(y-j);
            }
        }
    }
    sort(a,a+cnt);
    ll t=1;
    rep(i,cnt){
        if(a[i]==a[i+1])t++;
        else sum[t]++,t=1,m--;
    }
    cout<<m<<" ";
    rep2(i,1,9)cout<<sum[i]<<" ";
}



Measured memory_bytes: 8448
import math
N, D = map(int, input().split())

points = []
for _ in range(N):
  points.append(list(map(int, input().split())))

count = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    d = 0
    for k in range(D):
      d += (points[i][k] - points[j][k]) ** 2
    d = math.sqrt(d)
    if (d == math.floor(d)):
      count += 1

print(count)


Measured memory_bytes: 3064
var
n:Longint;
a:array[3..100]of Longint=(61,230,865,3247,12185,45719,171531,643550,2414454,9058467,33985227,127504505,478366600,794717734,733354121,261943303,776803305,580025381,51688048,44657419,737209731,604119499,159693437,858533109,639056669,549054109,996291083,531294469,23314687,783022045,855462856,649970414,68697295,409213624,604356692,88638656,978442997,534833116,763737161,785892908,123883652,639213333,181836645,998121103,124885216,501575626,39816123,113468411,799008836,775465589,256852905,664630886,971550783,751629411,51018086,702530485,725438992,696683714,792638194,221791721,149602322,414054379,986519078,981760191,305799096,515140586,406959393,975058685,245601370,324759692,673385295,191483611,570246669,427196161,781042769,569725155,842176273,25328739,847501730,206282374,353770801,323137024,371653459,940737264,123820509,915711339,847205021,252858375,718889563,866398347,738390145,133009077,333099663,170591295,329869205,616680192,597534442,388130742);
begin
read(n);
writeln(a[n]);
end.

Measured memory_bytes: 128
import Control.Monad
import Data.List
import Data.Bits
import Debug.Trace
import Data.Maybe
import qualified Data.ByteString.Char8 as C
import qualified Data.IntMap.Strict as IntMap
import Data.IntMap.Strict (IntMap)

main :: IO ()
main = do
  [n, k] <- readInts
  input <- readInts
  print $ solve n input

solve :: Int -> [Int] -> Int
solve n input = findX n
  where
    findX :: Int -> Int
    findX x = if check x then x else findX (x + 1)
    dmap :: IntMap Bool
    dmap = foldl' (\a x -> IntMap.insert x True a) IntMap.empty input
    check :: Int -> Bool
    check x = checkSub $ x `divMod` 10
    checkSub :: (Int, Int) -> Bool
    checkSub (d, r) = if IntMap.member r dmap
      then False
      else (d == 0) || checkSub (d `divMod` 10)

-- 以下ライブラリ

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

readNInts :: Int -> IO [[Int]]
readNInts = flip replicateM readInts

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

readNIntegers :: Int -> IO [[Integer]]
readNIntegers = flip replicateM readIntegers

getNLns :: Int -> IO [String]
getNLns = flip replicateM getLine

toTup2 :: [[a]] -> [(a, a)]
toTup2 = map (\ys -> case ys of y : z : zs -> (y, z))

encIdx2 :: Int -> (Int, Int) -> Int
encIdx2 mx (y, x) = y * mx + x

decIdx2 :: Int -> Int -> (Int, Int)
decIdx2 mx idx = (idx `div` mx, idx `mod` mx)

encIdx3 :: (Int, Int) -> (Int, Int, Int) -> Int
encIdx3 (my, mx) (z, y, x) = z * my * mx + y * mx + x

decIdx3 :: (Int, Int) -> Int -> (Int, Int, Int)
decIdx3 (my, mx) idx = (z, y, x)
  where
    basez = my * mx
    z = idx `div` basez
    y = (idx `mod` basez) `div` mx
    x = idx `mod` mx


Measured memory_bytes: 380
n=int(input())
ans=0
flagA=[]
flagB=[]
fla=0
flb=0
for x in range(n):
    s = input()
    if 'AB' in s:
        ans += s.count('AB')
    if s[-1]=='A':
        flagA.append(x)
        fla+=1
    if s[0]=='B':
        flagB.append(x)
        flb+=1
if flagA==flagB and len(flagA)!=0:
    ans-=1
ans+=min(fla,flb)
print(ans)


Measured memory_bytes: 44392
#include<stdio.h>
#include<math.h>
#define N 10000000

int isprime(int);

int main(){
  int i,j;
  int count=0;
  int flag;
  int n;
  
  
  while(1){
    count=0;
    scanf("%d",&n);
    if(n==0)break;
    
    for(i=n+1;i<=2*n;i++){
      if(isprime(i)==1){
	count++;
      }   
    }
    printf("%d\n",count);
  }
  
  return 0;
}

int isprime(int x){
  int i=3;
  
  if(x==2) return 1;
  
  if(x<2||x%2==0)return 0;

  while(i<=sqrt(x)){
    if(x%i==0) return 0;
    i+=2;
  }

  return 1;
}

Measured memory_bytes: 600
#include<stdio.h>

int A[1000000],n;

int binarySearch(int key){
  int left = 0;
  int right = n;
  int mid;
 while(left < right){
  mid = (left + right) / 2;
  if(key == A[mid]) return 1;
  if(key > A[mid]) left = mid + 1;
  else if(key < A[mid]) right = mid;

}
  return 0;
}
 
int main(){
  int i,q,k,sum = 0;

  scanf("%d",&n);
  for(i = 0; i < n;i++){
  scanf("%d",&A[i]);
}
  scanf("%d",&q);
  for(i = 0; i < q;i++){
  scanf("%d",&k);
  if( binarySearch( k ) ) sum++;
}
  printf("%d\n", sum);
  
  return 0;
}

Measured memory_bytes: 2160
#import 
#=input()
#int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

for i in range(k,n):
    if a[i-k] < a[i]:
        print('Yes')
    else:
        print('No')

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

using namespace std;
int cuts(const vector<vector<int>>& grid, int mask, int b, int h, int w) {
  // h-1 bits
  vector<int> cuts;
  for (int i = 0; i < h - 1; ++i) {
    if (mask & (1 << i)) cuts.push_back(i);
    //cout << i << ' ';
  }
  //for (int i: cuts) cout << i << ' ';
  //cout << '\n';
  cuts.push_back(11);
  vector<int> pieces(cuts.size());
  int c(0);
  for (int i = 0; i < w; ++i) {
    int k(0);
    for (int j = 0; j < h; ++j) {
      pieces[k] += grid[j][i];
      if (j == cuts[k]) k++;
    }
    //cout << 'p';
    //for (int x = 0; x < cuts.size(); ++x) cout << pieces[x] << ' ';
    //cout << endl;
    bool test(true);
    for (int j = 0; j < pieces.size(); ++j) {
      if (pieces[j] > b) {
        test = false;
        break;
      }
    }
    if (!test) {
      c++;
      for (int j = 0; j < pieces.size(); ++j) pieces[j] = 0;
      k = 0;
      for (int j = 0; j < h; ++j) {
        pieces[k] += grid[j][i];
        if (j == cuts[k]) k++;
      }
      for (int j = 0; j < pieces.size(); ++j) {
        if (pieces[j] > b) {
          c = -1;
          break;
        }
      }
      if (c == -1) break;
    }
  }
  //cout << "case" << c << endl;
  return c;
}
int main() {
  int h, w, k;
  char c;
  cin >> h >> w >> k;
  vector<vector<int>> grid(h, vector<int>(w));
  for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j) {
      cin >> c;
      grid[i][j] = c - '0';
    }
  int hs(1 << (h - 1)), ans(h + w - 2);
  for (int mask = 0; mask < hs; ++mask) {
    //cout << 'm' << mask << endl;
    int t = cuts(grid, mask, k, h, w);
    ans = min(ans, t == -1 ? h + w - 2 : __builtin_popcount(mask) + t);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
  int r,g,b,n;
  cin >> r >> g >> b >> n;
  int mg,mb,mr,m=0;
  ll tot=0;
  mg = n / g;
  mb = n / b;
  mr = n / r;

  for (int i = 0;i<=mr;i++){
    for (int j = 0;j<=mg;j++){
      m = n - i*r - j*g;
      if (m >= 0 && m % b == 0){
	tot += 1;
      }
    }
  }
  cout << tot;
}

Measured memory_bytes: 256
import fractions
N,X=map(int,raw_input().split())
A=map(int,raw_input().split())

if N==1:
	print abs(A[0]-X)
	quit()

for i,x in enumerate(A):
	t=abs(x-X)
	if i==0:  D=t
	else:
		D=fractions.gcd(D,t)

print D

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

int insertionsort(int a[],int n,int g){
  int cnt=0;
  for(int i=g;i<n;i++){
    int v=a[i];
    int j=i-g;
    while(j>=0 && a[j]>v){
      a[j+g]=a[j];
      j=j-g;
      cnt++;
    }
    a[j+g]=v;
  }
  return cnt;
}

int shell(int a[],int n){
  int cnt=0;
  int m;
  int g[100000];
  g[0]=1;
  m=0;
  while(g[m]<n){
    g[m+1]=(g[m]*3)+1;
    m++;
  }
  if(m==0) m++;
  cout<<m<<endl;
  for(int i=m-1;i>=0;i--){
    if(i==0) cout<<g[i]<<endl;
    else cout<<g[i]<<" ";
  }
  for(int i=m-1;i>=0;i--){
    cnt+=insertionsort(a,n,g[i]);
  }
  return cnt;
}
int main(){
  int n,p;
  cin>>n;
  int a[1000000];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  p=shell(a,n);
  cout<<p<<endl;
  for(int i=0;i<n;i++){
   cout<<a[i]<<endl;
  }
  
  return 0;
}



Measured memory_bytes: 7008
#include<bits/stdc++.h>                                                      
using namespace std;
int main()
{
  int N;
  int X;
  cin >> N >> X;
  vector<int> L(N);
  for(int i=0; i<N; i++){
    cin >> L.at(i);
  }
  int price=0;
  int count=1;
  for(int i=0; i<N; i++){
    price+=L.at(i);
    if(price<=X)
      count++;
    else
      break;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
def main():
    ab = [_x for _x in input().split()]
    n = ab[1]
    bb = (int(n[0])*100 + int(n[2])*10 + int(n[3]))
    aa = int(ab[0])
    if aa == 0:
        print(0)
        return
    if bb == 0:
        print(0)
        return
    result = str(aa*bb)

    if len(result) <= 2:
        print(0)
    else:
        print(str(result)[:-2])


main()


Measured memory_bytes: 9164
#include <bits/stdc++.h>
using namespace std;
using PP = pair<long, long>;
const int INF = 1e9;
template <class T> T Next() { T buf; cin >> buf; return buf; }

int n;
int a[200000];

bool ok(int kind) {
  map<int, int> mp;
  for (int i = 1; i < n; ++i) {
    if (a[i - 1] < a[i]) continue;
    if (kind == 1) return false;
    
    int idx = a[i];
    while (idx > 0 && mp[idx] == kind - 1) {
      mp[idx] = 0;
      --idx;
    }
    if (idx == 0) return false;
    ++mp[idx];
    
    mp.erase(mp.upper_bound(idx), mp.end());
  }
  return true;
}

int sub() {
  int lo = 0;
  int hi = 200001;
  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (ok(mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  
  cout << sub() << endl;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int bexp(int a, int x, int p) {
    if (x == 0) {
        return 1;
    }
    if (x % 2 == 1) {
        return a * bexp(a, x - 1, p) % p;
    }
    int t = bexp(a, x / 2, p);
    return t * t % p;
}

int inv(int a, int p) {
    return bexp(a, p - 2, p);
}

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

    int c[p][p];
    for (int i = 0; i < p; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % p;
        }
    }

    int e[p][p];
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < p; j++) {
            e[i][j] = j == 0 ? 1 : e[i][j-1] * i % p;
        }
    }

    int b[p];
    for (int i = p - 1; i >= 0; i--) {
        int x = 0, y = 0;
        int neg = 1;
        for (int j = i; j >= 0; j--) {
            y = ((y + a[j] * c[i][j] * neg) % p + p) % p;
            x = ((x + e[j][i] * c[i][j] * neg) % p + p) % p;
            neg = -neg;
        }
        b[i] = x == 0 ? 0 : y * inv(x, p) % p;

        for (int j = 0; j < p; j++) {
            a[j] = ((a[j] - b[i] * e[j][i]) % p + p) % p;
        }
    }

    for (int i = 0; i < p; i++) {
        cout << b[i] << (i == p - 1 ? '\n' : ' ');
    }

    return 0;
}


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


int main() {
    int n, l;
    cin >> n;
    cin >> l;
    int mina, maxa;
    mina = l;
    maxa = l + n - 1;
    int apple;
    if (mina <= 0 && maxa >= 0) {
        apple = 0;
    } else if (mina > 0) {
        apple = mina;
    } else {
        apple = maxa;
    }
    int s = 0;
    for (int i = mina; i <= maxa; ++i) {
        s += i;
    }
    s -= apple;
    cout << s << "\n";
    return 0;
}


Measured memory_bytes: 256
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
 
def main():
  n = int(input())
  s = [input() for _ in range(n)]
  m = int(input())
  t = [input() for _ in range(m)]
  
  Nya = list(set(s))
  #print(Nya)
  Ma = 0
  for i in range(len(Nya)):
    Fi = s.count(Nya[i])
    Se = t.count(Nya[i])
    Ma = max(Ma,Fi-Se)
  print(Ma)
    
    
    
if __name__ == '__main__':
  main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<N;i++)
typedef long long ll;
int main(){
  ll a,b,c;
  cin>>a>>b>>c;
  ll ans = 0;
  if(a%2 && b%2 && c%2){
    ans = min(a*b,b*c);
    ans = min(ans,c*a);
  }
  else ans = 0;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int X=sc.nextInt();
		int T=sc.nextInt();
		if(N%X!=0){
			System.out.println((N/X+1)*T);
		}else{
			System.out.println(N/X*T);
		}
	}
}

Measured memory_bytes: 35692
//
//  main.cpp
//  Atcoder176
//
//  Created by Keita on 2020/08/22.
//  Copyright © 2020 Keita. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std ;

void doProblemA(){
    int x;
    cin >> x;
    if(x == 0){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
}



int main(int argc, const char * argv[]){
    // insert code here...
    doProblemA();
    return 0;
}





Measured memory_bytes: 3192
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned int ui;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
#define All(v) (v).begin(),(v).end()
#define Rep(i,n) for(int i = 0; i < (int)n; i++)
#define Reps(i,n) for(int i = 1; i <= (int)n; i++)
#define For(i,m,n) for(int i = m; i < n; i++)
#define Fors(i,m,n) for(int i = m; i <= n; i++)
#define Inf 2e9
#define F first
#define S second
#define pb push_back
#define mp make_pair
struct speed{speed(){cin.tie(); ios::sync_with_stdio(false); cout << fixed << setprecision(18);}}speed;

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

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

ll lcm(ll a, ll b){
    return a*b/gcd(a,b);
}



int main(){
    int a,b;
    cin >> a >> b;
    if((a+b)%2 == 0){
        cout << (a+b)/2 << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main()
{
    char a[1500]={0};
    while(scanf("%[^\n]",a)!=EOF)
    {
        getchar();
        for(;;)
        {
            for(int i=0;;i++)
            {
                if(a[i]==0)break;
                if(a[i]==122)a[i]=97;
                else if(97<=a[i]&&a[i]<122)a[i]++;
                else;
            }
            for(int i=0;;i++)
            {
                if(a[i]==0)break;
                if(a[i]=='t'&&a[i+1]=='h'&&a[i+2]=='i'&&a[i+3]=='s'&&(a[i+4]==' '||a[i+4]=='.'||a[i+4]==0))goto end;
                if(a[i]=='t'&&a[i+1]=='h'&&a[i+2]=='a'&&a[i+3]=='t'&&(a[i+4]==' '||a[i+4]=='.'||a[i+4]==0))goto end;
                if(a[i]=='t'&&a[i+1]=='h'&&a[i+2]=='e'&&(a[i+3]==' '||a[i+3]=='.'||a[i+3]==0))goto end;
            }
        }
        end:;
        printf("%s\n",a);
        for(int i=0;i<1500;i++)
        {
            a[i]=0;
        }
    }
    return 0;
}

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

int main()
{
    string S, T;cin >> S>> T;
    int A,B;cin >> A>>B;

    string U;cin >>U;

    if(U==S) A = A-1;
    if(U==T) B= B-1;

    cout << A<<" "<<B<<endl;
}

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

int main(){
    int a,b,max,sum,sub,mult;
    cin >> a >> b;
    sum = a+b;
    sub = a-b;
    mult = a*b;

    max = sum;
    if(sub>=max){
        max = sub;
    }
    if(mult >= max){
        max = mult;
    }
    cout << max;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long int ll;
const ll LINF = 1e18;
int main(int argc, char const *argv[]) {
  ll N;
  cin >> N;
  vector<ll> a(N);
  ll sum = 0;
  for (size_t i = 0; i < a.size(); i++) {
    cin >> a[i];
    sum += a[i];
  }
  ll sunuke = 0;
  ll araiguma = sum;
  ll ans = LINF;
  for (size_t j = 0; j < a.size()-1; j++) {
    sunuke += a[j];
    araiguma -= a[j];
    if (ans > abs(sunuke - araiguma)) {
      ans = abs(sunuke - araiguma);
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}


const ll inf = 1e18;


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,W;cin >> n >> W;
	vector<int> w(n),v(n);
	rep(i,n) cin >> w.at(i) >> v.at(i);
	vector<vector<ll>> dp(n + 1, vector<ll>(100100, inf));
	dp[0][0] = 0;
	rep(i,n){
		rep(j,100001){
			if(j - v.at(i) >= 0) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v.at(i)] + w.at(i));
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
		}
	}
	int ans = 0;
	for(int i = 100000; i >= 0; i--){
		if(dp[n][i] <= W){
			ans = i;
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define int long long
#define rng(i, l, r) for (size_t i = (l); i < (r); ++i)
#define rep(i, n) rng(i, 0, n)
#define gnr(i, l, r) for (size_t i = (r)-1; i >= (l); i--)
#define per(i, b) gnr(i, 0, b)
#define ALL(obj) (obj).begin(), (obj).end()    //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend() //...,3,2,1
using namespace std;
const int INF = 1e18;
const int MOD = 1000000007;

const int MAX = 1e5;

int parent(int i) { return i / 2; }
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }

void solve()
{

    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

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

    int H, A[MAX + 1];

    cin >> H;

    for (int i = 1; i <= H; i++)
        cin >> A[i];

    for (int i = 1; i <= H; i++)
    {
        cout << "node " << i << ": ";
        cout << "key = " << A[i] << ", ";
        if (i != 1)
            cout << "parent key = " << A[parent(i)] << ", ";
        if (left(i) <= H)
            cout << "left key = " << A[left(i)] << ", ";
        if (right(i) <= H)
            cout << "right key = " << A[right(i)] << ", ";
        cout << endl;
    }
}

signed main()
{
    solve();
    return 0;
}



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

int main()
{
	int X;
	cin >> X;
	if (X==7 || X == 5|| X == 3)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
A,B,C = map(int,input().split())
if A == B and  B == C and C == A:
  print(-1 if A%2==0 else 0 )
else:
  count = 0
  while(A%2==0 and B%2 == 0 and C%2==0):
    A_ = A
    B_ = B
    A = (B+C)/2
    B = (A_+C)/2
    C = (A_+B_)/2
    count+=1
  print(count)


Measured memory_bytes: 9176
#include <iostream>

using namespace std;

int main()
{
    int a, b;

    do {
         cin >> a >> b;
    } while ((a < -1000 || a > 1000) || (b < -1000 || b > 1000));

    if (a > b) {
        cout << "a > b" << endl;
    } else if (a < b) {
        cout << "a < b" << endl;
    } else if (a == b) {
        cout << "a == b" << endl;
    }

    return (0);
}

Measured memory_bytes: 1156
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 5e5+10 , mod = 998244353;
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
	return f ? -x : x;
}
int n , m;
int fac[N] , inv[N];
inline int add(int a , int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a , int b) { return (LL)a * b % mod; }
inline int ksm(int a , int k) { a %= mod; int ans = 1; for( ; k ; k >>= 1 , a = mul(a , a)) if(k & 1) ans = mul(ans , a); return ans; }
inline int C(int n , int m) { return mul(fac[n] , mul(inv[m] , inv[n-m])); }
int main()
{
	n = read(); m = read(); if(n > m) swap(n , m);
	fac[0] = inv[0] = inv[1] = 1;
	for(int i = 1 ; i <= m ; ++i) fac[i] = mul(fac[i-1] , i); //cout << fac[1] << ' '; cout << '\n';
	for(int i = 2 ; i <= m ; ++i) inv[i] = mul(inv[mod % i] , mod - mod / i);
	//cout << inv[0] << ' ' << inv[1] << '\n';
	for(int i = 1 ; i <= m ; ++i) inv[i] = mul(inv[i-1] , inv[i]);
	//cout << inv[1] << ' '; cout << '\n';
	int ans = 0 , op = 0 , tmp; // cout << C(2 , 0) << '\n';
	for(int i = 0 ; i <= n ; ++i)
	{
		op ^= 1;
		tmp = mul(mul(C(n , i) , C(m , i)) , mul(ksm(n + 1 , m - i) , ksm(m + 1 , n - i)));
		ans = add(ans , (op ? 1 : -1) * mul(tmp , fac[i])); ans = add(ans , mod);
		// cout << ans << ' '; 
	}
	// cout << '\n';
	cout << ans << '\n';
	return 0;
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

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

signed main() {
  ll n, a, b, result = 0, walk = 0;
  cin >> n >> a >> b;
  ll x[n];
  x[0] = {0};
  rep(i, n) {
    cin >> x[i];
    if(i == 0) continue;
    walk = a * (x[i] - x[i - 1]);
    if (walk < b) result += walk;
    if (walk > b) result += b;
  }
  cout << result << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int sum=0,i=0;
    while(sum<=b){
        i++;
        sum+=a;
    }
    i--;
    if(i<c)
    cout<<i<<endl;
    else
    cout<<c<<endl;
    return 0;
}

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

int main() {
int64_t N,A,B;
  cin>>N>>A>>B;
  if(A%2==B%2){cout<<(B-A)/2<<endl;}
  else{int64_t maxA,maxB;
       maxA=max(A-1,N-A);maxB=max(B-1,N-B);
       
 if(maxA<=maxB){cout<<N-B+1+(B-A-1)/2<<endl;}
    else{cout<<A+(B-A-1)/2<<endl;}
}
	
}

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

string str[8]={"AAA","AA","A","B","C","D","E","NA"};
double t[8]={35.5 , 37.5 , 40.0 , 43.0, 50.0, 55.0, 70.0,9999999.9999999};
double u[8]={71.0 , 77.0 , 83.0 , 89.0,105.0,116.0,148.0,9999999.9999999};

double a,b;

int main(){
  while(cin>>a>>b){
    for(int i=0;i<8;i++){
      if(a<t[i]&&b<u[i]){cout<<str[i]<<endl;break;}
    }
  }
  return 0;
}

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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);





void solve4ts()
{
  
  
  int n;
  cin>>n;
  map<int,int> mp;

  int ans=0;
  rep(i,n){
    int a;
    cin>>a;
    mp[a]++;
    ans+=a;
  }
  
  int q;
  cin>>q;
  rep(i,q){
    int b,c;
    cin>>b>>c;
    int memo=mp[b];
    mp[b]=0;
    ans-=memo*b;
    mp[c]+=memo;
    ans+=memo*c;
    cout<<ans<<endl;
  }
  
  
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

Measured memory_bytes: 13784
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = n; i >= n; i--)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

/********************Template********************/

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

	int n, a[100000], odd = 0, even = 0;
	cin >> n;
	REP(i, n){
		cin >> a[i];
		if(a[i] % 2 == 0) even++;
		else odd++;
	}

	string ans;
	if(odd % 2 != 0) ans = "NO";
	else ans = "YES";
	cout << ans << endl;
	rtn 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using LL = long long int;
using namespace std;

int main (void) {
  int K, T;
  cin >> K >> T;
  vector<int> a(T);
  REP(i, T)
    cin >> a[i];
  sort(ALL(a), greater<int>());
  int left = 0, right = T - 1;
  while (left < right) {
    // REP(i, T)
    //   cerr << a[i] << " ";
    // cerr << endl;
    if (a[left] - a[right] > 0) {
      a[left] -= a[right];
      a[right] = 0;
      right--;
    } else {
      a[right] -= a[left];
      a[left] = 0;
      left++;
    }
  }
  // REP(i, T)
  //   cerr << a[i] << " ";
  // cerr << endl;
  // cerr << left << endl;
  cout << max(a[left] - 1, 0) << endl;
  return 0;
}


Measured memory_bytes: 384
// RAKSHIT KADAM
 
//  -- Declare array globally...
 #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
// find_by_order returns iterator to  element present at that index...
// order_of_key returns no. of elements having value stricktly less than that given in the order_of_key();
#warning !!!check the size of arrayss!!!
 
// NUMERIC DEFINITIONS :
    #define INF 1000000000000000005
    #define inf 1000000003
    #define MOD  1000000007
    #define newMOD  998244353
    #define MAX 200006
    #define pi 3.1415926535897932384626433832795
#define ld long double
 #define ll long long
 #define int long long
 
 #define P(gg) for(auto rax:gg){cout<<rax<<" ";}cout<<endl;
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define endl "\n"
 #define x first
 #define y second
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define vi vector<ll>
 #define Endl endl
 #define lb lower_bound
 #define ub upper_bound
#define pii pair<ll,ll>
 
 #define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
 #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;return (y%2 == 0)? p : (x * p) % m;}
ll modInverse(int a, int m){{ return power(a, m-2, m);}}
const int maxn = 500066;
 void solve()
{
    ll n;cin>>n;ll ans =INF;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans= min(ans,i-1+n/i-1);
        }
    }
    cout<<ans<<endl;
}
signed main()
{
   Need_for_speed(activated);

//satisfy
//    {
//  solve();
//   }
   
    solve();
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
	int n;
	n=read();
	int cnt=0;
	for(int i=1;i<=n;i++){
		int tmp=0;
		int t=i;
		while(t>0){
			t/=10;
			tmp++;
		}
		if(tmp%2==1)cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 1000000007; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int N, C; 
  cin >> N >> C;

  vector<vector<int>> D(C, vector<int>(C));
  REP(i, C) REP(j, C) cin >> D[i][j];

  vector<vector<int>> vec(3, vector<int>(C, 0));
  REP(i, N) REP(j, N){
    int c;
    cin >> c;
    // pos  color
    vec[(i+j)%3][c-1]++;
  }

  int ans = INF;
  REP(a, C) REP(b, C) REP(c, C){
    if(a == b || b == c || c == a) continue;
    int ret = 0;
    REP(i, C){
      ret += D[i][a]*vec[0][i];
      ret += D[i][b]*vec[1][i];
      ret += D[i][c]*vec[2][i];
    }
    chmin(ans, ret);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
n = int(input())
a1 = list(map(int,input().split()))
a2 = list(map(int,input().split()))
for i in range(1,n):
    a1[i] += a1[i-1]
    a2[i] += a2[i-1]

ans = a1[0] + a2[-1]
for i in range(1,n):
    ans = max(ans,a1[i]+a2[-1]-a2[i-1])

print(ans)

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

using namespace std;

int main()
{
   int a,b,c,d,e,k;
   cin>>a>>b>>c>>d>>e>>k;
   if(e-a>k)
    cout<<":("<<endl;
   else
    cout<<"Yay!"<<endl;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

int main(){
  int n;
  while(cin>>n,n){
    cin.ignore();
    map<string, set<string> > groups;
    set<string> ans;
    REP(i,n){
      set<string> members;
      char line[256];
      cin.getline(line,256);
      char* tok = strtok(line,":,.");
      string title(tok);
      while(tok = strtok(NULL,":,.")){
          string mem(tok);
          members.insert(mem);
      }
      groups[title] = members;
      if(i == 0){
        ans = members;
      }
    }
    bool update;
    do{
      update = false;
      set<string> next = ans;
      FORIT(itr,ans){
        if(groups.find(*itr)!=groups.end()){
          next.erase(*itr);
          FORIT(itr2, groups[*itr]){
            next.insert(*itr2);
            update = true;
          }
        }
      }
      ans = next;
    }while(update);
    cout<<ans.size()<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
N, M = map(int, input().split(' '))
X = []
for i in range(M):
    X.append(list(map(int, input().split(' '))))

num_b = [1 for i in range(N+1)]
num_b[0] = 0
psb = [0]*(N+1)
psb[1] = 1
for i in range(M):
    num_b[X[i][0]] -= 1
    num_b[X[i][1]] += 1
    if psb[X[i][0]] == 1:
        psb[X[i][1]] = 1 
    if num_b[X[i][0]] == 0:
        psb[X[i][0]] = 0

print(psb.count(1))

Measured memory_bytes: 67416
f=->k,d,q{x=(-d)%10;d-=10**(k-1)*x-x;k>1?(10-x-q)*f[k-2,d.abs/10,0]:d==0?10**k :0};n=gets.to_i;r=0;1.upto(100){|i|r+=f[i,n,1]};p r

Measured memory_bytes: 3964
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N;
    cin>>N;
    vi A(N);
    rep(i,N) cin>>A.at(i);
    vi B=A;
    sort(A.begin(),A.end(),greater<int>());
    rep(i,N) {
        if(A.at(0)==B.at(i)) cout<<A.at(1)<<endl;
        else cout<<A.at(0)<<endl;
    }
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef complex<double> xy_t;
typedef vector<lint> poly;
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(a>b){a=b; return true;} return false;}

constexpr lint mod = 998244353;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    rep(i, n) scanf("%d", &a[i]);
    int cur=0;
    rep(i, n){
        if(a[i]==cur+1) ++cur;
    }
    printf("%d\n", cur==0 ? -1 : n-cur);
}

Measured memory_bytes: 1024
#include<iostream>
#include<stack>
#include<cstdlib>



using namespace std;

int main(){
	stack<int> st;
	int num1,num2;
	while (true){
		string c;
		cin >> c;
		if (cin.eof()) break;
		if (c == "+"){
			num1 = st.top();
			st.pop();
			num2 = st.top();
			st.pop();
			st.push(num1+num2);
		}else if (c == "-"){
			num1 = st.top();
			st.pop();
			num2 = st.top();
			st.pop();
			st.push(num2-num1);
		}else if (c == "*"){
			num1 = st.top();
			st.pop();
			num2 = st.top();
			st.pop();
			st.push(num1*num2);
		}else{
			st.push(stoi(c));
		}
		

	}
	cout << st.top() << endl;
return 0;
}

Measured memory_bytes: 3180
sx,sy,tx,ty = map(int,input().split())

dx = tx-sx
dy = ty-sy

print(dy*"U"+dx*"R"+dy*"D"+dx*"L"+"L"+(dy+1)*"U"+(dx+1)*"R"+"D"+"R"+(dy+1)*"D"+(dx+1)*"L"+"U")


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int a, b; cin >> a >> b;

    if (a > b) {
        for (int i = 0; i < a; ++i) {
            cout << b;
        }
    } else {
        for (int i = 0; i < b; ++i) {
            cout << a;
        }
    }

    cout << endl;
}

Measured memory_bytes: 256
from collections import Counter
from math import factorial
N = int(input())
A = list(map(int, input().split()))
Acount = Counter(A)
Chose = {}
total = 0
for k, v in Acount.items():
    if Acount[k] >= 2:
        x = int(v*(v-1)/2)
        Chose[k] = x
    else:
        x = 0
        Chose[k] = x
    total = total+x
for i in range(N):
    ans=total-Chose[A[i]]
    if Acount[A[i]]-1>=2:
        ans=ans+(Acount[A[i]]-1)*(Acount[A[i]]-2)/2
    print(int(ans))


Measured memory_bytes: 34496