akhauriyash/Code-Regression huggingface dataset:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))

B = [0] * N

for a in A:
    B[a] += 1

ok = True

if N % 2 == 1:
    ok = ok and B[0] == 1
    for i in range(1, N):
        ok = ok and B[i] == (2 if i % 2 == 0 else 0)
else:
    for i in range(N):
        ok = ok and B[i] == (0 if i % 2 == 0 else 2)

ans = 1
MOD = int(1e9) + 7
for _ in range(N // 2):
    ans *= 2
    ans %= MOD

print(ans if ok else 0)


Measured memory_bytes: 20884
function Main(input) {
	input = input.trim().split("\n").map(function(x) { return x.split(" ")});    
	let C = 1e9 + 7;
	let H = parseInt(input[0][0], 10);
	let W = parseInt(input[0][1], 10);
	let DP = [];
	for (let i = 0; i < H; i++){
		DP.push(Array.from({length: W}, () => 0));
	}
	DP[0][0] = 1;
	for (let i = 1; i < H + W - 1; i ++){
		for (let j = 0; j <= Math.min(i, H - 1); j++){
			// console.log(i, j);
			if (input[j + 1][0][i - j] === '#' || i - j >= W) continue;
			if (j > 0 && i - j > 0) {
				DP[j][i - j] = (DP[j - 1][i - j] + DP[j][i - j - 1]) % C;
			} else if (j > 0){
				DP[j][i - j] = DP[j - 1][i - j];
			} else {
				DP[j][i - j] = DP[j][i - j - 1];
			}
			// console.log(DP);
		}
	}
	// console.log(DP);
	console.log(DP.pop().pop());
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 47396
d = int(input())
dd = d * (d + 1) // 2
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]


def calc_score(T):
    L = [-1 for j in range(26)]
    X = [0 for j in range(26)]
    score = 0
    for i in range(d):
        score += S[i][T[i]]
        X[T[i]] += (d - i) * (i - L[T[i]])
        L[T[i]] = i
    for j in range(26):
        score -= C[j] * (dd - X[j])
    return score


T = [int(input()) - 1 for i in range(d)]
m = int(input())
PQ = [tuple(map(int, input().split())) for k in range(m)]
PQ = [(p - 1, q - 1) for p, q in PQ]

for p, q in PQ:
    T[p] = q
    print(calc_score(T))


Measured memory_bytes: 97588
N=int(input())
S=list(int(input()) for _  in range(N))
S=sorted(S)
ans=0
if sum(S)%10!=0:
  ans=sum(S)
else:
    for i in range(N):
      if (sum(S)-S[i])%10!=0:
        ans=sum(S)-S[i]
        break
    
print(ans)

Measured memory_bytes: 3060
#include <stdio.h>

int main() {
    int n;
    int i;
    int a[1000000];
    
    scanf("%d", &a[1]);
    
    for (n = 2 ;n <= 1000000; n ++) {
        if (a[n-1] % 2 == 0) {
            a[n] = a[n-1] / 2;
        } else {
            a[n] = 3 * a[n-1] + 1;
        }
        
        for (i = 0; i < n; i ++) {
            if (a[i] == a[n]) {
                printf("%d\n", n);
                return 0;
            }
        }
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
  vector<int> r;
  int a, b;
  char op;

  while(1) 
  {
    scanf("%d %c %d", &a, &op, &b);
    if (op == '?')
    {
      break;
    }
    switch(op)
    {
      case '+':
        r.push_back(a + b);
        break;
      case '-':
        r.push_back(a - b);
        break;
      case '*':
        r.push_back(a * b);
        break;
      case '/':
        r.push_back(a / b);
        break;
      default:
        break;
    }
  }

  for (int i = 0; i < r.size(); i++)
  {
    printf("%d\n", r[i]);
  }

  return 0;
}


Measured memory_bytes: 2764
while True:
    ts = {}
    c = input()
    if c == 0: break
    for i in range(c):
        f = raw_input().split()
        ts[f[0]] = int(f[1])
    for i in range(input()):
        f = raw_input().split()
        m =0
        for j in range(int(f[1])):
            h = ts[f[j+2]] if f[j+2] in ts else 0
            m+= h
        ts[f[0]] = ts[f[0]] if m > ts[f[0]] else m
    print ts[raw_input()]

Measured memory_bytes: 4256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
//#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define maxe max_element
#define mine min_element
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<ll,ll>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define SIZE 5000 + 1
const ll MAX=1e9;
const ll mod=1e9;

ll expo(ll x,ll n){
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%mod;}
                x=(x*x)%mod;
                n>>=1;
    }
    return ans;
}

vl adj[200001];
void solve()
{
    ll n,i;
    cin>>n;
    vl a(n);
    ll sum=0;
    fs(i,1,n){cin>>a[i];adj[a[i]].pb(i);}
    fs(i,1,n+1)
    {
        cout<<adj[i].size()<<endl;
    }

}

int main()
{
  boost;
  ll t=1;
 // cin>>t;
  while(t--)
  {

      solve();
  }
}


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

char grid[1010][1010];
int dp[1010][1010];
const int mod = 1000000007;
int main(){

    int h, w;
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> grid[i][j];
        }
    }

    memset(dp, 0, sizeof(dp));
    dp[0][1] = 1;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++ ){
            if(grid[i-1][j-1] != '#')
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
            else
                dp[i][j] = 0;
        }
    }

    cout << dp[h][w] << endl;


    return 0;
}



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

using namespace std;

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

int main() {
  while (true) {
    int n, s;
    cin >> n >> s;
    if (n == 0 && s == 0) break;
    vector<int> r;
    rep (i, n) {
      int rr;
      cin >> rr;
      r.push_back(rr);
    }
    int res = 0;
    sort(r.begin(), r.end());
    rep (i, n) {
      if (r[i] + r[i] > s) --res;
      res += r.end() - upper_bound(r.begin(), r.end(), s - r[i]);
    }
    cout << res / 2 << endl;
  }
  return 0;
}

Measured memory_bytes: 1324
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    int n,i,A[55],B[55];
    ll C[55],sum=0;
    cin>>n;
    for(i=0; i<n; i++)
        cin>>A[i];
    B[n-1]=A[n-1];
    for(i=n-2; i>=0; i--)
        B[i]=B[i+1]+A[i];
    for(i=1; i<n; i++)
        C[i-1]=B[i]*A[i-1];
    for(i=0; i<n-1; i++)
        sum=sum+C[i];
    cout<<sum<<endl;
    return 0;
}


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

def path(sx, sy, tx, ty):
  res = ''
  y = ty - sy
  res += abs(y) * ('U' if y > 0 else 'D')
  x = tx - sx
  res += abs(x) * ('R' if x > 0 else 'L')
  return res

ans = ''
ans += path(sx, sy ,tx ,ty)
ans += path(tx, ty, sx, sy)
ans += 'L'
ans += path(sx - 1, sy, tx, ty + 1)
ans += 'DR'
ans += path(tx + 1, ty, sx, sy - 1)
ans += 'U'
print(ans)


Measured memory_bytes: 3064
fn main(){
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    let n = n.trim().parse::<i32>().unwrap();
    let mut a:Vec<i32> = Vec::with_capacity(n as usize);
    let mut a_s = String::new();
    std::io::stdin().read_line(&mut a_s).unwrap();
    for i in a_s.split_whitespace() {
        a.push(i.trim().parse::<i32>().unwrap());
    }
    let mut r_cumgcd:Vec<i32> = Vec::with_capacity((n+1) as usize);
    let mut l_cumgcd:Vec<i32> = Vec::with_capacity((n+1) as usize);
    r_cumgcd.push(0);
    l_cumgcd.push(0);
    for i in 0..n {
        let ri:usize = n as usize - i as usize - 1_usize;
        let i = i as  usize;
        let r_gcd = gcd(*(r_cumgcd.last().unwrap()),*(a.get(ri).unwrap()));
        let l_gcd = gcd(*(l_cumgcd.last().unwrap()),*(a.get(i).unwrap()));
        r_cumgcd.push(r_gcd);
        l_cumgcd.push(l_gcd);
    }
    let mut ans:Vec<i32> = Vec::with_capacity(n as usize);
    for i in 0..n {
        ans.push(gcd(*(l_cumgcd.get(i as usize).unwrap()),*(r_cumgcd.get((n-i-1) as usize)).unwrap()));
    }
    println!("{}",ans.iter().max().unwrap());
}

fn gcd(a:i32,b:i32) -> i32 {
    let mut max = if a < b {b}else{a};
    let mut min = if a > b {b}else{a};
    let mut r;
    while min != 0{
        r = max;
        r %= min;
        max = min;
        min = r;
    }
    max
}

Measured memory_bytes: 8444
function main(input) {
    var a = input[0].split(" ")[0]-0;
    var b = input[0].split(" ")[1]-0;
    var ans = "";
    if(a>b){
        for(var i=0;i<a;i++){
            ans += b.toString();
        }
    }else{
        for(var i=0;i<b;i++){
            ans += a.toString();
        }
    }
    console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"))


Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
const int vy[] = {-1, 1, 0, 0}, vx[] = {0, 0, 1, -1};

int main()
{
  int R, N;
  cout << fixed << setprecision(10);

  while(cin >> R >> N, R) {
    int left[44] = {}, right[44] = {};
    while(N--) {
      int l, r, h;
      cin >> l >> r >> h;
      l += 22, r += 22;
      for(int j = l; j < r; j++) left[j] = max(left[j], h);
      for(int j = r; j > l; j--) right[j] = max(right[j], h);
    }
    double ret = 1e9;
    for(int i = -R + 1; i < R; i++) {
      ret = min(ret, min(left[i + 22], right[i + 22]) + R - sqrt(R * R - i * i));
    }
    cout << ret << endl;
  }

}

Measured memory_bytes: 1236
n,m=map(int,input().split())
edge=[[] for i in range(n)]
kara=[]
to=[0]*n
for i in range(m):
  x,y=map(int,input().split())
  edge[x-1].append(y-1)
  to[y-1]+=1
for j in range(n):
  if to[j]==0:
    kara.append(j)
dp=[0]*n
while len(kara):
  go=kara.pop()
  for e in edge[go]:
    to[e]-=1
    if to[e]==0:
      kara.append(e)
    dp[e]=max(dp[e],dp[go]+1)
print(max(dp))

Measured memory_bytes: 22704
#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long
#define pb push_back
#define ff first
#define INF INT_MAX
#define ss second
#define fr(i, j, a) for (int i = j; i < a; i++)
#define cnt_ones(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<ipair>
#define ar array
#define IOS                                                                    \
  std::ios::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
int n, m;
vi par, sze;
void make_set() {
  for (int i = 0; i < n; i++) {
    par[i] = i;
    sze[i] = 1;
  }
}
int find_set(int u) {
  if (u == par[u])
    return u;
  return par[u] = find_set(par[u]);
}

void union_set(int a, int b) {
  int x = find_set(a), y = find_set(b);
  if (x != y) {
    if (sze[y] > sze[x])
      swap(x, y);
    par[y] = x;
    sze[x] += sze[y];
  }
}
void init() {
  cin >> n >> m;
  par.resize(n), sze.resize(n);
  make_set();
  while (m--) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    union_set(a, b);
  }
  int mx = 1;
  for (int i = 0; i < n; i++)
    mx = max(mx, sze[find_set(i)]);
  cout << mx << endl;
}
int32_t main() {
  IOS;
  init();
  return 0;
}


Measured memory_bytes: 6360
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int main(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> cnt(3,0);
    REP(i,n){
        cnt[s[i]-'a']++;
    }
    SORT(cnt);
    if(cnt[2]-cnt[0]<=1){
        put("YES");
    }else{
        put("NO");
    }
    return 0;
}


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

int main(){
	int n; scanf("%d",&n);
	string s; cin >> s;
	char a = s[0];
	int cnt = 1;
	for(int i = 1;i < s.size();i++){
		char c = s[i];
		if(c != a) cnt++;
		a = c;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD1 1000000007

int main() {
  int A,N;
  cin >> N >> A;
  if(N % 500 <= A) cout << "Yes" << endl;
  else cout << "No" << endl;

}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
def saiki(count,price,lis):
    if count==N:
        judge=True
        for item in lis:
            if item<X:
                judge=False
        if judge:
            ans.append(price)
    else:
        temp=[lis[i]+note[count][i+1] for i in range(M)]
        saiki(count+1,price,lis)
        saiki(count+1,price+note[count][0],temp)

N,M,X=map(int,input().split())

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

ans=[]
saiki(0,0,[0]*M)

print(min(ans) if len(ans)!=0 else -1)

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


int main(){

    int n;
    cin>>n;
    string s;
    cin>>s;

    if ( s.length() <= n)
        cout<<s<<endl;

    else {
        for(int i=0;i<n;i++){
            cout<<s[i];
        }
        cout<<"..."<<endl;
    }




    return 0;
}

Measured memory_bytes: 3612
#include <stdio.h>
int main(void)
{ 
	int n, p[21], a, b = 0;
	
	scanf("%d", &n);
	for(a = 1; a <= n; a++){
		scanf("%d", &p[a]);
	}
	
	for(a = 1; a <= n; a++){
		if(a != 1 && a != n){
			if((p[a] < p[a - 1] && p[a] >= p[a + 1])||
			   (p[a] >= p[a - 1] && p[a] < p[a + 1])||
			   (p[a] < p[a - 1] && p[a - 1] == p[a + 1])){
			   	b = b + 1;
			   }
		}
	}
	
	printf("%d", b);
	
	return 0;
}

Measured memory_bytes: 128
N = int(input())
N_1 = len(str(N))
if(N_1 == 1 ):
  print(N)
elif (N_1 == 2):
  print(9)
elif(N_1 == 3):
  print(N-99+9)
elif(N_1 == 4):
  print(909)
elif(N_1 == 5):
  print(N-9999+909)
else:
  print(90909)

Measured memory_bytes: 3060
#include<stdio.h>

int main(){
  int si,i,j,n,sq[5000],m,prev,sum,max,k;
  do{
    scanf("%d",&n);
    if(!n) break;
    for(si=0,i=0,prev=2,sq[0]=0,j=0;i<n;i++){
      scanf("%d",&m);
      if(prev*m>=0){
	if(prev==2) prev=1;
	sq[si]+=m;
      }else{
	if(prev!=2){
	  si++;
	  sq[si]=m;
	  prev*=-1;
	}
      }
      if(prev==2){
	if(j==0||m>j){
	  j=m;
	}
      }	
    }
    if(prev==2){
      printf("%d\n",j);
      continue;
    }
    if(sq[si]<0) si--;
    n=si+1;
    for(sum=0,i=0;i<n;i++){
      sum+=sq[i];
    }
    max=sum;

    for(i=n-2;i>0;i-=2){
      for(j=0;j<((n-i)/2+1);j++){
	for(k=0,sum=0;k<i;k++){
	  sum+=sq[k+j*2];
	}
	if(sum>max) max=sum;
      }
    }
    printf("%d\n",max);
  }while(1);
  return 0;
}

Measured memory_bytes: 420
import math

N = int(input())

def F(a, b):
    a = len(str(a))
    b = len(str(b))
    if a > b:
        return a
    elif a < b:
        return b
    else:
        return b

elements = []

for i in range(1, math.ceil(math.sqrt(N+1))):
    if N % i == 0: elements.append(i)

a = elements[-1]
b = N // a
print(F(a,b))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin >> n;
  vector<int64_t> a(n),b(n);
  rep(i,n){
    cin >> a.at(i);
  }
  int ans=0;
  rep(i,n){
    if(a.at(i)%4==0){
      b.at(i)=2;
    }else if(a.at(i)%2==0){
      b.at(i)=1;
    }
    ans+=b.at(i);
  }
  rep(i,n){
    if(a.at(i)%4==0 && n%2==1){
      ans++;
    }
  }
  if(ans>=n){
    cout << "Yes";
  }else{
    cout << "No";
  }
}

Measured memory_bytes: 1792
N = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = []

for i in range(N):
    c.append(a[i]-b[i])

#print (c)

mi = 0
pl = 0

for i in c:
    if i < 0:
        mi += abs(i) // 2
    else:
        pl += i

if mi < pl:
    print ("No")
else:
    print ("Yes")


Measured memory_bytes: 40560
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i >= 1; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> p;


int main() {
	int n,ans=0;
	cin >> n;
	int i = 0;
	while (ans <= n) {
		ans = pow(2, i);
		i++;
	}
	cout << ans/2;
	return 0;
}

//Ctrl+Aを使わない

Measured memory_bytes: 384
n, c, k = map(int, input().split())
dat = []
for _ in range(n):
    dat.append(int(input()))
dat.sort()
cn = 1
nt = dat[0] + k
res = 1
for i in range(1, n):
    #print("i", i, "res", res)
    # もう前のバスがいっぱい
    if cn == c:
        #print("full")
        cn = 1
        nt = dat[i] + k
        res += 1
        continue
    if dat[i] > nt:
        #print("gogogo")
        cn = 1
        nt = dat[i] + k
        res += 1
        continue
    cn += 1
print(res)


Measured memory_bytes: 50392
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define endl '\n'

const int max4 = 10004;
const int maxx = 100005;
const int max6 = 1000006;
const int lg5 = 17;

const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;

/***************/

int powmod (int a, int b, int mod) {
    int res = 1; a %= mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
    }
    return res;
}
#define ll long long
ll gcd (ll a, ll b) {
    while (b > 0) {
        ll t = a % b;
        a = b, b = t;
    }
    return a;
}

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

int is_prime (int n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/******Don't forget to use long long when needed!!******/

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long n, k;
    cin >> n >> k;
    cout << 3LL * (n - gcd(n, k)) << endl;
    return 0;
}


Measured memory_bytes: 256
/// Thank you tanakh!!!
///  https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!(q: usize, ab: [(usize, usize); q]);
    for &(a, b) in ab.iter() {
        let (a, b) = if a > b { (b, a) } else { (a, b) };
        if a == b {
            println!("{}", 2 * a - 2);
        } else if a + 1 == b {
            println!("{}", 2 * a - 2);
        } else {
            let c = ((a * b) as f64).sqrt() as usize;
            assert!(c * c <= a * b);
            let c = if c * c == a * b { c - 1 } else { c };
            if c * (c + 1) >= a * b {
                println!("{}", 2 * c - 2);
            } else {
                println!("{}", 2 * c - 1);
            }
        }
    }
}


Measured memory_bytes: 4352
#include <iostream>
using namespace std;
typedef long long ll;
int N;
ll field[101][101];
int main(){
  cin>>N;
  ll sum=0;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin>>field[i][j];
  for(int i=0;i<N;i++)
    for(int j=i+1;j<N;j++)
      sum+=min(field[i][j],field[j][i]);
  cout<<sum<<endl;
  
  return 0;
}

Measured memory_bytes: 1244
#include<cstdio>
#include<utility>
#include<queue>
using namespace std;int i,n,L,t,a[99999],s;int main(){typedef pair<int,int>y;priority_queue<y>q;y p;for(scanf("%d%d",&n,&L);i++<n;)scanf("%d",a+i);for(;--i;)a[i]>a[i-1]&a[i]>a[i+1]?q.push(y(a[i]-L,i)),a[i]=L:0;for(;!q.empty();n&&n!=L&n>a[s+2]?q.push(y(t-L+n,s+1)),a[s+1]=L:0)p=q.top(),q.pop(),t=p.first,a[s=p.second]=0,n=a[s-1],n&&n!=L&n>a[s-2]?q.push(y(t-L+n,s-1)),a[s-1]=L:0,n=a[s+1];printf("%d\n",-t);}

Measured memory_bytes: 1580
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(c) (c).begin(), (c).end()
#define pb push_back
#define eb emplace_back
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値;
using ll = long long;
using P  = pair<int, int>;
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int MAX = 101010;
vector<int> is_prime(MAX, 1);
int main()
{
    is_prime[0] = 0, is_prime[1] = 0;
    for (int i = 2; i < MAX; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i*2; j < MAX; j += i) is_prime[j] = 0;
    }
    vi L(MAX, 0);
    rep2(i, 2, MAX){
        L[i] += L[i-1];
        if(i%2 == 0) continue;
        if(is_prime[i] &is_prime[(i+1)/2]){
            L[i]++;
        }
    }
    int q;
    cin >> q;
    vi l(q), r(q);
    
    rep(i, q){
        cin >> l[i] >> r[i];
    }
    rep(i, q){
        cout << L[r[i]] - L[l[i]-1] << endl;;
    }
    return 0;
}

Measured memory_bytes: 4828
#include<cstdio>
#include<iostream>
using namespace std;
#define LL long long

LL n, m;

int main() {
    cin>>n>>m;
    if( 2*n >= m ) {
        cout<<m/2<<endl;
    } else {
        LL ans = n;
        m -= 2*n;
        ans += m/4;
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for(ll (i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); (i)++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

ll gcd(ll a, ll b) {
    return b != 0 ? gcd(b, a % b) : a;
}

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

int main()
{	
    char c;
    cin >> c;
    if (isupper(c))  cout << "A" << endl;
    else cout << "a" << endl;
}


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

int main() {
  string S;
  cin >> S;
  if (S == "Sunny") return cout << "Cloudy" << "\n", 0;
  if (S == "Cloudy") return cout << "Rainy" << "\n", 0;
  if (S == "Rainy") return cout << "Sunny" << "\n", 0;
}

Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize -O3
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = double;
using ull = uint64_t;

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    int ans = 1e9 + 20;

    for (int i = 0; i + k <= n; ++i) {
        int l = -x[i], r = x[i + k - 1];
        if (l < 0) l = 0;
        if (r < 0) r = 0;
        ans = min(ans, l + r + min(l, r));
    }

    cout << ans << "\n";
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
//#include <algorithm>

int main(int argc, char* argv[])
{
    long n;
    scanf("%ld", &n);

	long maxh = -1;
	long i_maxh = 0;
	long x[100]={0}, y[100]={0}, h[100]={0};
	long i;
	for(i=0; i<n; i++) {
		scanf("%ld %ld %ld", &(x[i]), &(y[i]), &(h[i]));
		if (maxh < h[i]) {
			maxh = h[i];
			i_maxh = i;
		}
	}

	long xx, yy;
	for(xx=0; xx<=100; xx++) {
		for(yy=0; yy<=100; yy++) {
			long hh = abs(x[i_maxh] - xx) + abs(y[i_maxh] - yy) + h[i_maxh]; 
			for(i=0; i<n; i++) {
				long value = hh - abs(x[i] - xx) - abs(y[i] - yy);
				if ( value < 0 ) {
					value = 0;
				}
				if( value != h[i] ) {
					break;
				}
			}
			if(i==n) {
				printf("%d %d %d\n", xx, yy, hh);
				return 0;
			}
		}
	}

    return 0;
}


Measured memory_bytes: 128
L, R = map(int, input().split())
li = []
li_a =[]
if R-L+1 >= 2019:
  print(0)
else:
  for i in range(L, R+1):
    li.append(i%2019)
  for x in li:
    for y in li:
      if x != y:
        li_a.append((x*y)%2019)
  print(min(li_a))

Measured memory_bytes: 149040
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(void) {
    vector<int> A(3);
    for (int i = 0; i < 3; i++) {
        cin >> A[i];
    }
    
    int ans = 1 << 30;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == j) {
                continue;
            }
            for (int k = 0; k < 3; k++) {
                if (k == i || k == j) {
                    continue;
                }
                ans = min(ans, abs(A[i]-A[j]) + abs(A[j]-A[k]));
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        ok = i
        ng = N
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if L[mid] > L[i] - L[j]:
                ok = mid
            else:
                ng = mid
        if ok > j:
            ans += ok - j
            
print(ans)



Measured memory_bytes: 74236
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 100000000
#define INFLL 100000000000
#define MOD 1000000007
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};



int N;
bool base[30];
int d[60];

int main () {
  cin >> N;
  rep(i, N) {
    int tmp;
    cin >> tmp;

    if (base[tmp]) {
      if (base[24-tmp]) {
        cout << 0 << "\n";
        return 0;
      } else {
        base[24-tmp] = true;
      }
    } else {
      if (tmp == 0) {
        cout << 0 << "\n";
        return 0;
      }
      base[tmp] = true;
    }
  }

  vector<int> v;
  v.push_back(0);

  rep(i, 24) {
    if(base[i]) v.push_back(i);
  }
  sort(All(v));

  int n = v.size();
  int m = 1 << n;

//  Rep(i, n) {
//    cout << v[i] << "\n";
//  }

  int ans = 0;

  bool skip[30];
  for (int i=0;i<=24;++i) {
    if (base[i]) {
      if (i==0 || i== 24 || base[24-i]) {
        skip[i] = true;
      }
    }
  }


  Rep(bits, m) {
    bitset<28> bs(bits);

    int tmp = INF;
    bool flg = false;

    for (int i=0;i<n;++i) {
      for (int j=i+1;j<n;++j) {
        int k;
        if (bs[i]) {
          k = v[i];
        } else {
          if (skip[v[i]]) {
            flg = true;
            break;
          }
          k = 24 - v[i];
        }
        int l;
        if (bs[j]) {
          l = v[j];
        } else {
          if (skip[v[j]]) {
            flg = true;
            break;
          }
          l = 24 - v[j];
        }

        int dis = min(abs(k-l), 24-abs(k-l));

        tmp = min(tmp, abs(dis));
      }

      if (flg) {
        break;
      }
    }

    if(!flg) ans = max(ans, tmp);
  }

  cout << ans << "\n";
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll p, q, r;
    cin >> p >> q >> r;
    ll ans = p+q;
    ans = min(ans, q+r);
    ans = min(ans, r+p);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    String s = sc.next();
    String t = sc.next();
    HashMap<Character, Character> conversion = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      if (
          (conversion.containsKey(s.charAt(i)) && conversion.get(s.charAt(i)) != t.charAt(i)) ||
              (!conversion.containsKey(s.charAt(i)) && conversion.containsValue(t.charAt(i)))) {
        System.out.println("No");
        return;
      }
      conversion.put(s.charAt(i), t.charAt(i));
    }
    System.out.println("Yes");
  }
}


Measured memory_bytes: 26036
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = Math.max(a + b, a - b);
        System.out.println(Math.max(c, a * b));
    }
}


Measured memory_bytes: 21844
def main():
    s = input()
    c = 0
    if s[0] == s[1] == s[2] == "R":
        print(3)
        return
    if s[0] == s[1] == "R" or s[1] == s[2] == "R":
        print(2)
        return
    if s[0] == s[1] == s[2] == "S":
        print(0)
        return

    print(1)
    return

main()



Measured memory_bytes: 9116
#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int v[n];
    int c[n];
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    for(int i=0; i<n; i++){
        cin >> c[i];
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        if(v[i]-c[i]>0){
            ans += v[i]-c[i];
        }
    }

    cout << ans;
    
    return 0;
}

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

int main(){
	int i, n;
	char g;
	int d[4][13] = {{},{},{},{}};
	cin >> n;
	for(int c = 0; c < n; c++){
		cin >> g >> i;
		switch(g){
			case 'S':
				d[0][i-1] = 1;
				break;
			case 'H':
				d[1][i-1] = 1;
				break;
			case 'C':
				d[2][i-1] = 1;
				break;
			case 'D':
				d[3][i-1] = 1;
		}
	}
	for(int y = 0; y < 4; y++){
		for(int x = 0; x < 13; x++){
			if(d[y][x] == 0){
				switch(y){
					case 0:
						cout << "S " << x+1 << endl;
						break;
					case 1:
						cout << "H " << x+1 << endl;
						break;
					case 2:
						cout << "C " << x+1 << endl;
						break;
					case 3:
						cout << "D " << x+1 << endl;
				}
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>
#include <cstring>

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

int main() {
    int k;
    cin >> k;
    if (k % 2 == 0 || k % 5 == 0) {
        cout << -1 << endl;
        return 0;
    }
    ll num = 7;
    ll ans = 0;
    while(1) {
        if (num % k == 0) break;
        num = (num % k) * 10 + 7;
        ++ans;
    }
    cout << ans + 1LL << endl;
    return 0;
}


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

using namespace std;

int main(int argc, char const *argv[])
{
    int N, K, Q;
    
    cin >> N >> K >> Q;
    int temp = K - Q;

    vector<int> Person(N, temp);

    for (int i = 0; i < Q; i++)
    {
        cin >> temp;
        Person[temp - 1]++;
    }
    
    for (auto &&p : Person)
    {
        cout << ((p > 0)? "Yes": "No") << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
AB = [[int(i) for i in input().split()] for j in range(n)]
CD = [[int(k) for k in input().split()] for l in range(m)]

ans = [0]*n
for ab in AB:
    a,b = ab[0],ab[1]
    distance = 1000000000
    for cd in CD:
        c,d = cd[0], cd[1]
        if distance > abs(a-c) + abs(b-d):
            distance = abs(a-c) + abs(b-d)
            ans[AB.index(ab)] = CD.index(cd)+1
        
for _ in ans:
    print(_)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
#define rep(i,n)for(int i=0;i<n;i++)
vector<int>E[100000];
int u[200000], v[200000], r[200000], ans[200000], d[100000], cnt = 1;
char b[200000], ok[100000]{ 1 };
list<int>que;

void bfs(int u, int t) {
	que.emplace_back(u);
	while (!que.empty()) {
		int p = que.front(); que.pop_front();
		for (int v : E[p]) {
			if (t) {
				if (d[v] > d[p] && !ok[v]) {
					ok[v] = 1; cnt++; que.emplace_back(v);
				}
			}
			else if (!~d[v]) {
				d[v] = d[p] + 1; que.emplace_back(v);
			}
		}
	}
}
int main() {
	int n, m, q; reader(n); reader(m); reader(q);
	rep(i, m) {
		reader(u[i]); reader(v[i]);
		u[i]--; v[i]--;
		E[u[i]].emplace_back(v[i]); E[v[i]].emplace_back(u[i]);
	}
	memset(d, -1, sizeof(d));
	d[0] = 0; bfs(0, 0);
	rep(i, m) {
		if (d[u[i]] > d[v[i]])swap(u[i], v[i]);
	}
	rep(i, n)E[i].clear();
	rep(i, q) {
		reader(r[i]); r[i]--;
		b[r[i]] = 1;
	}
	rep(i, m) {
		if (!b[i]) {
			if (d[v[i]] > d[u[i]]) {
				E[u[i]].emplace_back(v[i]);
			}
		}
	}
	bfs(0, 1);
	for (int i = q - 1; i >= 0; i--) {
		ans[i] = n - cnt;
		if (d[v[r[i]]] > d[u[r[i]]] && !ok[v[r[i]]]) {
			E[u[r[i]]].emplace_back(v[r[i]]);
			if (ok[u[r[i]]]) {
				cnt++; ok[v[r[i]]] = 1;
				bfs(v[r[i]], 1);
			}
		}
	}
	rep(i, q)writerLn(ans[i]);
}

Measured memory_bytes: 14736
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template <class T> inline void dump(T &v){irep(i, v){cout<<(*i)<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;






int main() {
    int n,k;
    cin>>n>>k;
    vll v(n);
    rep(i,n)cin>>v[i];
    int l=0,r=k;
    while(r<n){
        Yn(v[l]<v[r]);
        l++;r++;
    }
    
}


Measured memory_bytes: 4788
#include <iostream>
#include <sstream>
using namespace std;
int main(){
  int n;
  int i;
  cin >> n;
  int wari = 0;
  int kouho = 1;
  for(i = 1; i<= n; i++){
    int count = 0;
    int j =i ;
    while (j % 2 == 0){
      count++;
      if(j % 2 == 0){
        j = j / 2;
      }else{
      break;
      }
    }
      if (count > wari){
      wari = count;
      kouho = i;
      }
    }

  cout << kouho << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define cinv(v,n) for(size_t i=0;i<(n);i++){cin>>(v)[i];}
#define nvec(type,v,n) vector<type> v(n);cinv(v,n)
#define npairs(type1,type2,v,n) vector<pair<type1,type2>> v(n);for(size_t i=0;i<(n);i++){cin>>v[i].first>>v[i].second;}
#define ntuples(type1,type2,type3,v,n) vector<tuple<type1,type2,type3>> v(n);for(size_t i=0;i<(n);i++){cin>>get<0>(v[i])>>get<1>(v[i])>>get<2>(v[i]);}

#define min_index(v) size_t(min_element(all(v))-(v).begin())
#define max_index(v) size_t(max_element(all(v))-(v).begin())
#define min_e(v) *min_element(all(v))
#define max_e(v) *max_element(all(v))

#define count_le(v,a) size_t(upper_bound(all(v),a)-(v).begin())
#define count_lt(v,a) size_t(lower_bound(all(v),a)-(v).begin())
#define count_ge(v,a) size_t((v).end()-lower_bound(all(v),a))
#define count_gt(v,a) size_t((v).end()-upper_bound(all(v),a))

#define order(neq_sl) [](const &auto s, const &auto l){return neq_sl;}
#define make_lr(v,type,l,r) vector<type> l(n+1),r(n+1);FOR(i,n){l[i+1]=l[i]+v[i];r[i+1]=r[i]+v[n-1-i];}

#define acm accumulate
#define SUM(v) acm(all(v),0l)


int main() {
  int n;
  cin>>n;
  nvec(int, v, n);
  sort(all(v));
  double s=v[0];
  for (int i = 1; i < n; i++) {
    s=(s+v[i])/2;
  }
  cout<<s;
}


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

int main(){
    int n,value;
    cin>>n;
    for(int i=1;i<=9;i++){
        value=100*i+10*i+i;
        if(value>=n){
            cout<<value<<endl;
            return 0;
        }
    }
}


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

typedef pair<long long, long long> II;
typedef vector< II > VII;
typedef vector<long long> VI;

#define endl "\n"
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (long long)(a.size())
#define ll long long
#define fr(i,n) for(i=0;i<n;i++)

VII v;
ll a[100010],c[100010],b[100010];

long long bsrh(long long l,long long r,long long x)
{
    if(l>r)
        return l;
    long long m=l+(r-l)/2;
    if(v[m].F>=x)
        return bsrh(m+1,r,x);
    return bsrh(l,m-1,x);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    long long tp2,n,h,i,mn,tp;
    cin>>n>>h;
    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        v.PB(MP(b[i],i));
    }
    sort(v.rbegin(),v.rend());
    c[0]=v[0].F;
    for(i=1;i<n;i++)
        c[i]=c[i-1]+v[i].F;
    for(i=0;i<n;i++)
        if(c[i]>=h)
            break;
    if(i<n)
        mn=i+1;
    else
        mn=1e18;
    for(i=0;i<n;i++)
    {
        tp=bsrh(0,n-1,a[i]);
        if(tp>=mn)
            continue;
        tp2=h;
        tp2=tp2-c[tp-1];
        mn=min(mn,tp+(tp2+a[i]-1)/a[i]);
    }
    cout<<mn<<endl;
    return 0;
}


Measured memory_bytes: 4336
#include <bits/stdc++.h> 
using namespace std;   
using ll = long long;
const ll INF = 1e18L + 5;

void min_self(ll& a, ll b) {
	a = min(a, b);
}

int main() 
{ 
	ll n, w; cin >> n >> w;
	vector<int > weight(n), value(n);
	for(int i = 0; i < n; i++) {
		cin >> weight[i] >> value[i];
	}
	int sum_value = 0;
	for(int x : value) {
		sum_value += x;
	}
	vector<ll > dp(sum_value + 1, INF);
	dp[0] = 0;
	for(ll item = 0; item < n; item++) {
		for(ll value_already = sum_value - value[item]; value_already >= 0; value_already--) {
			min_self(dp[value_already + value[item]], dp[value_already] + weight[item]);
		}
	}


	ll answer = 0;
	for(ll i=0; i <= sum_value; i++) {
		if(dp[i] <= w) {
			answer = max(answer, (ll) i);
		}
		//min_self(answer, dp[i]);
	}
	cout << answer;
    return 0; 
} 

Measured memory_bytes: 1024
N = int(input())

if N < 2:
    print(0)

heights = [int(x) for x in input().split()]

dp = [0] * N
dp[0] = 0
dp[1] = abs(heights[1] - heights[0])

for i in range(2, N):
    dp[i] = min(dp[i-1] + abs(heights[i] - heights[i-1]),
                dp[i - 2] + abs(heights[i] - heights[i - 2]))

print(dp[-1])

Measured memory_bytes: 13928