akhauriyash/Code-Regression huggingface dataset:
import java.io.InputStream
import java.math.BigDecimal
import java.math.BigInteger

fun main(args: Array<String>) = input.run {
    val n = nextInt();
    val c = nextInt();
    val k = nextInt();
    val t = nextInts(n);
    t.sort()
    var time = 0
    var left = 0
    var ans = 0
    t.forEach {
        if (left < 1 || time < it) {
            time = it + k
            left = c
            ans++
        }
        left--
    }
    println(ans)
}

val input = FastScanner()

fun String.toBigInteger() = BigInteger(this)
fun String.toBigDecimal() = BigDecimal(this)

class FastScanner(private val input: InputStream = System.`in`) {
    private val sb = StringBuilder()
    private val buffer = ByteArray(4096)
    private var pos = 0
    private var size = 0

    fun next(): String? {
        var c = skipWhitespace()
        if (c < 0) return null

        return sb.run {
            setLength(0)

            do {
                append(c.toChar())
                c = read()
            } while (c > ' '.toInt())

            toString()
        }
    }

    fun nextLine(): String? {
        var c = read()
        if (c < 0) return null

        return sb.run {
            setLength(0)

            while (c >= 0 && c != '\n'.toInt()) {
                append(c.toChar())
                c = read()
            }

            toString()
        }
    }

    fun nextLong(): Long {
        var c = skipWhitespace()

        val sign = if (c == '-'.toInt()) {
            c = read()
            -1
        } else 1

        var ans = 0L

        while (c > ' '.toInt()) {
            ans = ans * 10 + c - '0'.toInt()
            c = read()
        }

        return sign * ans
    }

    fun nextInt() = nextLong().toInt()
    fun nextDouble() = next()?.toDouble() ?: 0.0
    fun nextBigInteger(): BigInteger = next()?.toBigInteger() ?: BigInteger.ZERO
    fun nextBigDecimal(): BigDecimal = next()?.toBigDecimal() ?: BigDecimal.ZERO

    fun nextInts(n: Int) = IntArray(n) { nextInt() }
    fun nextLongs(n: Int) = LongArray(n) { nextLong() }
    fun nextDoubles(n: Int) = DoubleArray(n) { nextDouble() }
    fun nextBigIntegers(n: Int) = Array<BigInteger>(n) { nextBigInteger() }
    fun nextBigDecimals(n: Int) = Array<BigDecimal>(n) { nextBigDecimal() }

    fun nextInts(n: Int, m: Int) = Array(n) { nextInts(m) }
    fun nextLongs(n: Int, m: Int) = Array(n) { nextLongs(m) }
    fun nextDoubles(n: Int, m: Int) = Array(n) { nextDoubles(m) }
    fun nextBigIntegers(n: Int, m: Int) = Array(n) { nextBigIntegers(m) }
    fun nextBigDecimals(n: Int, m: Int) = Array(n) { nextBigDecimals(m) }

    private fun skipWhitespace(): Int {
        while (true) {
            val c = read()
            if (c > ' '.toInt() || c < 0) return c
        }
    }

    private fun read(): Int {
        while (pos >= size) {
            if (size < 0) return -1
            size = input.read(buffer, 0, buffer.size)
            pos = 0
        }
        return buffer[pos++].toInt()
    }
}


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

using namespace std;

const int N = 1e5 + 10;

struct Edge {
  long long w;
  int a, b;
  bool operator<(Edge x) const {
    return make_pair(w, make_pair(a, b)) < make_pair(x.w, make_pair(x.a, x.b));
  }
};

int n;
int fa[N];
int x[N], y[N];
set < pair <int, int> > st, st2;
set <Edge> stx, sty;

/*
void print(Edge &e) {
  cout << "Edge " << e.w << " " << e.a << " " << e.b << endl;
}*/

int find(int x) {
  return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

void mrg(int x, int y) {
  x = find(x), y = find(y);
  if (x != y) {
    fa[x] = y;
  }
}

Edge get(set <Edge> &a) {
  auto it = a.begin();
  while (it != a.end()) {
    auto e = *it;
    if (find(e.a) != find(e.b)) {
      return e;
    }
    it = a.erase(it);
  }
  return Edge{-1, -1, -1};
}

Edge get(set < pair <int, int> > &st, pair <int, int> x) {
  auto it = st.lower_bound(x);
  if (it == st.begin()) {
    return Edge{-1, -1, -1};
  }
  auto itx = it--;
  itx++;
  if (itx == st.end()) {
    return Edge{-1, -1, -1};
  }
  Edge a;
  a.w = itx->first - it->first;
  a.a = itx->second;
  a.b = it->second;
  return a;
}

void go(int a) {
  Edge nx = get(st, make_pair(x[a], a));
  Edge ny = get(st2, make_pair(y[a], a));
  st.erase(make_pair(x[a], a));
  st2.erase(make_pair(y[a], a));
  if (nx.w != -1) {
    stx.insert(nx);
  }
  if (ny.w != -1) {
    sty.insert(ny);
  }
}

void erase(set <Edge> &a) {
  auto e = *a.begin();
  a.erase(a.begin());
  mrg(e.a, e.b);
  //go(e.a);
  //go(e.b);
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", x + i, y + i);
  }
  for (int i = 0; i < n; ++i) fa[i] = i;
  for (int i = 0; i < n; ++i) {
    st.insert(make_pair(x[i], i));
    st2.insert(make_pair(y[i], i));
  }
  pair <int, int> old(-1, -1);
  for (auto p : st) {
    if (old.first == -1) old = p;
    else {
      stx.insert(Edge{p.first - old.first, p.second, old.second});
      old = p;
    }
  }
  old = make_pair(-1, -1);
  for (auto p : st2) {
    if (old.first == -1) old = p;
    else {
      sty.insert(Edge{p.first - old.first, p.second, old.second});
      old = p;
    }
  }
  int sz = n - 1;
  long long ans = 0;
  while (sz--) {
    Edge e1 = get(stx);
    Edge e2 = get(sty);
    if (e1.w == -1) {
      erase(sty);
      //print(e1);
      ans += e2.w;
    } else if (e2.w == -1) {
      erase(stx);
      //print(e1);
      ans += e1.w;
    } else {
      if (e1.w < e2.w) {
	erase(stx);
	//print(e1);
	ans += e1.w;
      } else {
	erase(sty);
	ans += e2.w;
	//print(e2);
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 23296
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	int i, j;
	char s[11];
	int len;
	long long sum[11][10], num[11][10];
	long long ans;

	scanf("%s%n", s, &len);

	sum[1][0] = s[0] - '0';
	num[1][0] = 1;

	for (i = 2; i <= len; i++) {
		for (j = 0; j < i - 1; j++) {
			char tmp[11];
			strcpy(tmp, s + j);
			tmp[i - 1 - j] = '\0';
			sum[i][j] = sum[i - 1][j] + num[i - 1][j] * (atoll(tmp) * 9 + s[i - 1] - '0');
		}
		sum[i][i - 1] = 0;
		for (j = 0; j < i - 1; j++)
			sum[i][i - 1] += num[i - 1][j];
		sum[i][i - 1] *= s[i - 1] - '0';
		for (j = 0; j < i - 1; j++)
			sum[i][i - 1] += sum[i - 1][j];

		num[i][i - 1] = 0;
		for (j = 0; j < i - 1; j++) {
			num[i][j] = num[i - 1][j];
			num[i][i - 1] += num[i - 1][j];
		}
	}

	ans = 0;
	for (i = 0; i < len; i++)
		ans += sum[len][i];

	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#define BIG 2000000007
 
#define MOD 1000000007
typedef unsigned long long ull;
typedef   signed long long sll;
 
typedef struct {
	int a;
	int b;
} hw;
 
#define N_MAX 100000
#define M_MAX 100000
 
ull n, m, k;
ull h, w;
ull va, vb, vc, vd;
// ull a[N_MAX];
// sll a[N_MAX];
// ull b[N_MAX];
// ull dp[N_MAX][M_MAX + 1];
// char s[N_MAX + 1];
// char t[N_MAX + 1];
// hw arr[N_MAX];
 
void swap_adj(ull *a, ull *b){
	ull tmp = *b;
	*b = *a;
	*a = tmp;
	return;
}

ull divide(ull a, ull b){
	ull x = MOD - 2;
	ull ans = 1;
	while (x) {
		if (x & 1) ans = (ans * b) % MOD;
		b = (b * b) % MOD;
		x /= 2;
	}
	return (a * ans) % MOD;
}
 
int digits(ull x){
	int i = 1;
	while (x >= 10) {
		x /= 10;
		i++;
	}
	return i;
}
 
int min(ull x, ull y){
	return (x < y) ? x : y;
}
 
ull gcd(ull x, ull y){
	if (x < y) {
		return gcd(y, x);
	} else if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}
 
ull bitpow(ull a, ull x){
	ull result = 1;
	while (x) {
		if (x & 1) {
			result *= a;
			result %= MOD;
		}
		x /= 2;
		a = (a * a) % MOD;
	}
	return result;
}

int comp(const void *left, const void *right){
	if ((*(int*)left) < (*(int*)right)) {
		return -1;
	} else if ((*(int*)left) > (*(int*)right)) {
		return +1;
	} else {
		return 0;
	}
}

// int nextroute(int arr[]){
// 	int i = n - 1;
// 	int j, x;
// 	while (arr[i - 1] > arr[i]) i--;

// 	x = n;
// 	for (j = i; j < n; j++) {
// 		if (arr[j] < arr[i - 1]) continue;
// 		if (x == n || arr[x] > arr[j]) x = j;
// 	}
// 	arr[i - 1] ^= arr[x];
// 	arr[x] ^= arr[i - 1];
// 	arr[i - 1] ^= arr[x];

// 	qsort(&arr[i], n - i, sizeof(int), comp);
// 	return 0;
// }

ull solve(){
	int i, j;

	return 0;
}
 
int main(void){
	int i, j;
	const int x[] = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
	char si, sj;


	scanf("%c %c", &si, &sj);

	// solve();

	if (si == sj) {
		puts("H");
	} else {
		puts("D");
	}

	return 0;
}


Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	text := stdin.Text()
	max := 0
	len := 0
	for _, c := range text {
		if c == 'A' || c == 'C' || c == 'G' || c == 'T' {
			len++
		} else {
			if max < len {
				max = len
			}
			len = 0
		}
	}
	if len != 0 && max < len {
		max = len
	}
	fmt.Println(max)
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> veci;
typedef pair<int,int> pri;
typedef vector<long long> vecll;
typedef pair<long long,long long> prill;

#define REP(i,a,b) for (int i = a; i < b; i++)

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

    int t;
    cin>>t;
    int a[t];
    REP(i,0,t)
    {
        cin>>a[i];
    }
    int c=0;
    for(int i=0;i<t;i++)
    {
        for(int j=i+1;(j<t);j++)
        {
            for(int k=j+1;(k<t);k++)
            {
                if(a[i]!=a[j] && a[j]!=a[k] &&a[k]!=a[i]){
                if((a[k]<(a[i]+a[j])) && (a[j]<(a[i]+a[k])) && (a[i]<(a[k]+a[j])))c++;}
            }
        }
    }
    cout<<c;
}

Measured memory_bytes: 3648
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N, M;
  cin>>N>>M;
  int a[N], b[N];
  for(int i=0;i<N;++i) {
    cin>>a[i]>>b[i];
  }
  int ans[N];
  int c[M], d[M];
  int tmp;
  for(int i=0;i<M;++i) cin>>c[i]>>d[i];
  for(int i=0;i<N;++i) {
    tmp = inf;
    for(int j=0;j<M;++j) {
      tmp = min(tmp, abs(a[i]-c[j])+abs(b[i]-d[j]));
    }
    for(int j=0;j<M;++j) {
      if(tmp==abs(a[i]-c[j])+abs(b[i]-d[j])) {
        ans[i] = j+1;
        break;
      }
    }
  }
  for(int i=0;i<N;++i)cout<<ans[i]<<endl;
}



Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include <vector>

#define LL long long

using namespace std;



const int INF = 100000000;

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

	bool flag = false;
	int a, b, c;
	cin >> a >> b;
	 
	for (int i = 1; i <= 3; i++) {
		c = i;
		if (a*b*c % 2 == 1) {
			cout << "Yes" << endl;
			flag = true;
			return 0;
		}
	}
	if (!flag) {
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include <sstream>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
#include <iomanip>
#include <regex>
#include <initializer_list>
#include <deque> 
#define DBL_MIN 0.000000000000001

#include <iostream>
using namespace std;



int main(void){
    long N,M;
    cin >> N;
    map<int,int> good;
    for(int i = 0; i < N; i++){
        int tmp =~ 0;
        cin >> tmp;
        good[tmp]++;
    }

    int sum = 0;
    for(auto it = good.begin(); it != good.end(); ++it){
        if(it->first > it->second){
            sum += it->second;
        }else if(it->second > it->first){
            sum += it->second - it->first;
        }
    }
    cout << sum << endl;


    return 0;
}



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

int main(void) {
	int n;

	while(cin >> n, n) {
		int ptA(0), ptB(0);
		for(int i = 0; i < n; i++) {
			int A, B;
			cin >> A >> B;

			if(A == B) {
				ptA += A;
				ptB += B;
			}
			else if(A > B)
				ptA += A + B;
			else
				ptB += A + B;
		}

		cout << ptA << " " << ptB << endl;
	}
}

Measured memory_bytes: 1160
#include<stdio.h>
#include<math.h>
int main(void)
{
	int a,b,X;
	scanf("%d",&X);
	for(a=-118;a<=119;a++){
		for(b=-119;b<=118;b++) {
			if((pow(a,5)-pow(b,5))==X) {
			printf("%d %d",a,b);
			return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2556
#include<stdio.h>

int main(){
  int year, month, day, heisei, showa, taisho, meiji, year2;

  while(scanf("%d %d %d", &year, &month, &day) != EOF){
    heisei = 0;
    showa = 0;
    taisho = 0;
    meiji = 0;

    if(year > 1989){
      heisei++;
    }else if(year == 1989){
      if(month > 1){
	heisei++;
      }else{
	if(day >= 8){
	  heisei++;
	}else{
	  showa++;
	}
      }
    }else if(year > 1926){
      showa++;
    }else if(year == 1926){
      if(month < 12){
	taisho++;
      }else{
	if(day >= 25){
	  showa++;
	}else{
	  taisho++;
	}
      }
    }else if(year > 1912){
      taisho++;
    }else if(year == 1912){
      if(month > 7){
	taisho++;
      }else if(month == 7){
	if(day >= 30){
	  taisho++;
	}else{
	  meiji++;
	}
      }else{
	meiji++;
      }
    }else if(year > 1868){
      meiji++;
    }else if(year == 1868){
      if(month > 9){
	meiji++;
      }else if(month == 9){
	if(day >= 8){
	  meiji++;
	}
      }
    }

    if(heisei == 1){
      year2 = year - 1988;
      printf("heisei %d %d %d\n", year2, month, day);
    }else if(showa == 1){
      year2 = year - 1925;
      printf("showa %d %d %d\n", year2, month, day);
    }else if(taisho == 1){
      year2 = year - 1911;
      printf("taisho %d %d %d\n", year2, month, day);
    }else if(meiji == 1){
      year2 = year - 1867;
      printf("meiji %d %d %d\n", year2, month, day);
    }else{
      printf("pre-meiji\n");
    }
  }

  return 0;
}

Measured memory_bytes: 0
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define INF 1e+9


int main() {
	int n;
	cin >> n;
	double a, ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> a;
		ans += (double)1 / a;
	}
	ans = (double)1/ans;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main ()
{
	
	int h, n, suma=0;
	cin>>h>>n;
	int a[n];
	for (int i=0; i<n; i++)
	{
		cin>>a[i];
		suma+=a[i];
	}
	
	if (h<=suma) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 640
c1 = list(input())
c2 = list(input())

m1 = "".join(c1)
m2 = "".join(c2)

a1 = list(reversed(c1))
a2 = list(reversed(c2))

r1 = "".join(a2)
r2 = "".join(a1)


if r1 == m1 and r2==m2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 38256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N;
  cin >> N;
  cout << N * N * N << endl;
  return 0;
}

Measured memory_bytes: 3572
#include "bits/stdc++.h"
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define vv vector
#define exist(s,e) (s.find(e)!=s.end())
#define sz(x) ((int)(x).size())
#define int ll
#define el '\n'
typedef long long ll; typedef long double ld; typedef double dd;typedef vector<int> vi; typedef pair<int, int> pii;typedef pair<ll,ll> pll;
const ll INFLL=0x7f7f7f7f7f7f7f7f, MOD=1e9+7; const int INF=0x7f7f7f7f;
///if(///////////////// DEBUG /////////////////////////////////////////
#define D(x) cerr<<#x<<" is:\t"<<x<<'\n';
#define DD(x,y) cerr<<'('<<#x<<','<<#y<<") are:\t"<<x<<' '<<y<<'\n';
#define DDD(x,y,z) cerr<<'('<<#x<<','<<#y<<','<<#z<<") are:\t"<<x<<' '<<y<<' '<<z<<'\n';
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vv<vv<int>> adj; vi vis, color; 
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1},dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
inline ll mexp(ll x,ll n,ll m=MOD){ll res=1;x%=m;while(n){if(n&1)res=(res*x)%m;n>>=1;x=(x*x)%m;}return res;}
inline ll gcd(ll a, ll b){while (a>0 && b>0){if(a>b)a%=b;else b%=a;}return a+b;}


///////////////////// MAIN STARTS //////////////////////////////////
int32_t main(void){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
cout<<fixed;cerr<<fixed; cout<<setprecision(10); cerr<<setprecision(3);
mt19937 genr(chrono::high_resolution_clock::now().time_since_epoch().count());

const int NN=3e5+10;
int n; cin>>n;
vv<ll> c(NN,-1), dp(n+1,0);
dp[0]=1;
for(int i=1;i<=n;++i){
	int t; cin>>t;
	if(c[t]!=-1 && c[t]!=i-1){
		dp[i]=dp[c[t]];
	}
	c[t]=i;
	dp[i]=(dp[i]+dp[i-1])%MOD;
}
cout<<dp[n]<<el;



return 0;
}


Measured memory_bytes: 4224
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

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

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    ll tmp = 0, ans = -1;
    for(int i = 0; i < n; i++){
        cin >> h[i];
        if(i != 0){
            if(h[i] <= h[i-1]) {
                tmp++;
                //cout << "tmp: " << tmp << endl;
            }
            else{
                //cout << "i: " << i << endl;
                ans = max(ans, tmp);
                //cout << ans << endl;
                tmp = 0;
            }
        }
    }
    ans = max(ans, tmp);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3792
#include <stdio.h>
   
int par[100001];
int sib[100001];
int deg[100001];
int n;
   
int depth(int i) {
  if(par[i] == -1) return 0;
  return depth(par[i]) + 1;
}
   
int height(int i) {
  int j, h = 0;;
  
  for(j = 0; j < n; ++j) {
    if(par[j] == i) {
      int tmp = height(j) + 1;
      if(tmp > h) h = tmp;
    }
  }
  return h;
}
   
int main(int argc,char *argv[]) {
  int i,j;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) {
    par[i] = -1;
    sib[i] = -1;
    deg[i] = 0;
  }
  for(i = 0; i < n; ++i) {
    int id, left, right;
    scanf("%d %d %d", &id, &left, &right);
    if(left != -1) {
      par[left] = id;
      sib[left] = right;
      deg[id]++;
    }
    if(right != -1) {
      par[right] = id;
      sib[right] = left;
      deg[id]++;
    }
  }
   
  for(i = 0; i < n; ++i) {
    int dep = depth(i);
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
           i, par[i], sib[i], deg[i], dep, height(i));
    if(dep == 0) {
      printf("root\n");
    } else if(deg[i] == 0) {
      printf("leaf\n");
    } else {
      printf("internal node\n");
    }
  }
  return 0;
}

Measured memory_bytes: 620
#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)
//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;
    string w[n];
    rep(i, n)   cin >> w[i];
    bool shiritori = true;
    
    string tmp_word = w[0];
    int tmp_size = w[0].size();
    
    FOR(i, 1, n){
        //cout << i << endl;
        //cout << tmp_word[tmp_size - 1] << " " << w[i][0] << endl;
        if(tmp_word[tmp_size - 1] != w[i][0]){
            //cout << "miss" << endl;
            shiritori = false;
        }
        
        rep(j, i){
            if(w[i] == w[j]){
                //cout << "two" << endl;
                shiritori = false;
                break;
            }
        }
        
        if(!shiritori){
            cout << "No" << endl;
            return 0;
        }
        tmp_word = w[i];
        tmp_size = w[i].size();
    }
    
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const ll INF = LLONG_MAX/3;

int main(){
    int n;
    cin >>n;
    vector<ll> a(n);
    rep(i,n) cin >>a[i];

    vector<ll> e(n+1);
    rep(i,n){
        if(a[i]==0) e[i] = 2;
        else if(a[i]%2==1) e[i] = 1;
    }
    rep(i,n) e[i+1] += e[i];

    auto EV = [&](int r){
        if(r==0) return 0LL;
        return e[r-1];
    };

    vector<ll> o(n+1);
    rep(i,n){
        if(a[i]%2==0) o[i]++;
    }
    rep(i,n) o[i+1] += o[i];

    auto OD = [&](int r){
        if(r==0) return 0LL;
        return o[r-1];
    };

    vector<ll> dp(n+1,0);
    ll s = 0;
    rep(i,n){
        s += a[i];
        dp[i+1] = s;
    }

    // 0 | ev
    vector<ll> nx(n+1,INF);
    ll val = INF;
    rep(i,n+1){
        val = min(val, dp[i]-EV(i));
        nx[i] = min(nx[i], val+EV(i));
    }
    dp = nx;

    // ev | od
    nx = vector<ll>(n+1,INF);
    val = INF;
    rep(i,n+1){
        val = min(val, dp[i]-OD(i));
        nx[i] = min(nx[i], val+OD(i));
    }
    dp = nx;

    // od | ev
    nx = vector<ll>(n+1,INF);
    val = INF;
    rep(i,n+1){
        val = min(val, dp[i]-EV(i));
        nx[i] = min(nx[i], val+EV(i));
    }
    dp = nx;

    // ev | 0
    ll ans = INF;
    s = 0;
    for(int i=n; i>=0; --i){
        ans = min(ans, dp[i]+s);
        if(i>0) s += a[i-1];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
int main(){
  int K;
  cin >> K;
  int64_t ans = 0;
  for(int i=1; i<=K; i++){
    for(int j=i; j<=K; j++){
      for(int k=j; k<=K; k++){
        int x = gcd(gcd(i,j),k);
        if(i == j && j == k){
          ans += x;
        }
        else if((i == j && j != k) || (i != j && j == k)){
          ans += x*3;
        }
        else{
          ans += x*6;
        }
      }
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        if (s.contains("AC"))   {
            System.out.println("Yes");
        } else  {
            System.out.println("No");
        }
    }
}


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

using namespace std;

const int MAXN = 100010;

vector<int> g[MAXN];
bool in_cycle[MAXN], used[MAXN];
int cycle_start = -1;
bool back_to_start = false;

void dfs(int node, int prev){
    used[node] = true;
    for(int next: g[node]){
        if(next == prev) continue;
        if(used[next]){
            in_cycle[next] = true;
            in_cycle[node] = true;
            cycle_start = next;
        }else{
            dfs(next, node);
            if(node == cycle_start){
                back_to_start = true;
            }
            if(in_cycle[next] && !back_to_start){
                in_cycle[node] = true;
            }
        }
    }
}

int main(){
    int n,a,b;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }

    fill(in_cycle, in_cycle+n, false);
    fill(used, used+n, false);

    dfs(0, -1);

    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> a >> b;
        if(in_cycle[a-1] && in_cycle[b-1]){
            cout << 2 << endl;
        }else{
            cout << 1 << endl;
        }
    }
}


Measured memory_bytes: 15060
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll n;
    cin >> n;

    string str;
    cin >> str;

    vector<ll> a(n+1,0),b(n+1,0);

    for(int i = 0; i < n; i++){
        a[i+1] = a[i];
        b[i+1] = b[i];
        if(str[i] == '.'){
            a[i+1]++;
        }else{
            b[i+1]++;
        }
    }

    ll ans = INF;

    for(int i = 0; i <= n; i++){
        ans = min(ans,b[i] + a[n] - a[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    vector<int> x(n+1);
    FOR(i,1,n+1){
      cin>>x[i];
    }
    int ans=0;
    FOR(i,1,n+1){
      if(x[i]<abs(k-x[i])){
        ans+=2*x[i];
      }else{
        ans+=2*abs(k-x[i]);
      }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  string s;
  cin >> s;

  char now = s[0];
  int res = 0;
  for (int i = 1; i < s.length(); i++)
  {
    if (now != s[i])
    {
      res++;
    }

    now = s[i];
  }

  cout << res << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M; cin >> N >> M;
  vector<int> town(N, 0);
  for(int i = 0; i < M; i++) {
    int a, b; cin >> a >> b; a--; b--;
    town.at(a)++; town.at(b)++;
  }
  for(int i = 0; i < N; i++) {
    cout << town.at(i) << endl;
  }
}

Measured memory_bytes: 256
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,X,Y,Z=MI()
t=1<<(X+Y+Z)
haiku=( (1<<(X+Y+Z)) + (1<<(Y+Z)) + (1<<Z) )>>1
dp=[0]*t
dp[0]=1


for i in range(n):
    tm=[i for i in dp]
    dp=[0]*t
    for k in range(t):
        for d in range(10):
            m=((k<<(d+1))+(1<<d))
            if m&haiku == haiku:
                continue
            else:
                dp[int(m)%t]+=tm[k]
                dp[int(m)%t]%=mo
sub=0
for i in range(t):
    sub+=dp[i]
ans=pow(10,n,mo)-sub
print(ans%mo)

show(ans,sub)
show(dp)
show(n,t,n*t*10)


Measured memory_bytes: 118400
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int n=s.length();

    int count=0;
    int test=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='g')
        {
            if(count>0)
            {
                count--;
                test++;
            }
            else
                count++;
        }
        else
        {
            if(count>0)
                count--;
            else
            {
                test--;
                count++;
            }
        }
    }
    cout<<test<<endl;

    
    return 0;   
}




 
 


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

int main()
{
    int n, min, ans = 1;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    min = p[0];
    for (int i = 1; i < n; i++)
    {
        if (p[i] < min)
        {
            min = p[i];
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>                           
#include <vector>                             
#include <cmath>                              
                                              
bool is_prime(int n)                          
{                                             
    if (n == 1)                               
        return false;                         
    if (n == 2)                               
        return true;                          
    if (n % 2 == 0)                           
        return false;                         
    int sqrt_n = std::sqrt(n);                
    for (int i = 3; i <= sqrt_n; i += 2) {    
        if (n % i == 0) {                     
            return false;                     
        }                                     
    }                                         
    return true;                              
}                                             
                                              
int main()                                    
{                                             
    int n;                                    
    std::vector<int> a{};                     
    std::cin >> n;                            
    int cnt = 0;                              
    int k = 1;                                
    while (1) {                               
        if (is_prime(30 * k + 1)) {           
            a.push_back(30 * k + 1);          
            cnt++;                            
            if (cnt == n) {                   
                for (int i = 0; i < n; i++) { 
                    std::cout << a[i] << " "; 
                }                             
                std::cout << std::endl;       
                return 0;                     
            }                                 
        }                                     
        k++;                                  
    }                                         
                                              
    return 0;                                 
}                                             


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

int main() {
    char t;
    cin>>t;
    if(t=='A')cout<<"T";
    else if(t=='T')cout<<"A";
    else if(t=='C')cout<<"G";
    else if(t=='G')cout<<"C";
	return 0;
}

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

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

const ll INF = 1LL<<60;

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    if(a + b + c >=22) {
        cout << "bust" << endl;
    } else {
        cout << "win" << endl;
    }

    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
  #define N 10000
  int main(void){
    int n,i,color[N],g;
    g=0;
    for(i=0;i<N;i++){
      color[i]=0;
    }
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&color[i]);
  }
  for(i=0;i<n-1;i++){
    if(color[i]==color[i+1]){
      color[i+1]=10001;
      g++;
    }
  }
  printf("%d",g);
  return 0;
  
  }


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        int N = sc.nextInt();
        var a = sc.ArrayInt(N);

        var ans = int.MaxValue;
        for (int i = -100; i <= 100; i++) {
            var cost = 0;
            for (int j = 0; j < N; j++) {
                cost += (int)Math.Pow(a[j] - i, 2);
            }
            ans = Math.Min(ans, cost);
        }
        WriteLine(ans);

    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


Measured memory_bytes: 11092
//Program.cpp
//Author : Aaryan Srivastava 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define pb push_back
#define popb pop_back
#define ull unsigned long long  
#define beg begin
#define mp make_pair
#define pii pair<int, int>
#define piii pair<pii,int>
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second 
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using ll = long long;
#define int ll
const int N = 1e5 + 5 ;
const int mod = 1e9 + 5 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace std;
#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#define AaryanS 0 
#endif

#define debug(x) mycout << #x << " "  << x << endl ;

void solve()
{
	int n ;
	cin >> n ;
	int dp[n+1] , arr[n+1];
	rep(i,n)
	 cin >> arr[i] ;
	dp[n] = dp[n-1] = 0 ; 
	repD(i,n-2,0)
		dp[i] = min(abs(arr[i] - arr[i+1]) + dp[i+1], abs(arr[i] - arr[i+2])  + dp[i+2]) ;
	cout << dp[0] << endl ;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
   // cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case " << t << ":\n" ;
        solve();
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}

Measured memory_bytes: 1792
N = int(input())
SP = []
for i in range(N):
    S, P = input().split()
    P = int(P)
    SP.append([S, P, i+1])

SP.sort()

while SP:
    restaurant = SP.pop(0)
    city = restaurant[0]
    point_num = [[restaurant[1], restaurant[2]]]
    while SP and SP[0][0] == city:
        restaurant = SP.pop(0)
        point_num.append([restaurant[1], restaurant[2]])

    point_num.sort(reverse=True)
    for i in point_num:
        print(i[1])


Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef map<int, int> mii;
    typedef map<char,int> mci;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef vector<ll> vll;
    typedef vector<pair<int,int>> vii;
    typedef vector<char> vc;
    typedef vector<vc> vcc;
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define pb push_back
    #define mp make_pair
    #define F first
    #define S second
    #define in insert
    #define sz(v) v.size()
    #define mina(a,b) (a)=min((a),(b));
    #define maxa(a,b) (a)=max((a),(b));
    const int INF = 1e9 + 5;
    bool f(pair<string,int> l, pair<string,int> r){
        if(l.F<r.F) return true;
        if(l.F>r.F) return false;
        if(l.S>r.S) return true;
        return false;
    }
    void solve(){
        int n; cin>>n;
        vector<pair<string,int>> v,c;

        for(int i = 0; i < n; i++){
            string s;
            int score;
            cin>>s>>score;
            v.pb({s,score});
        }
        c=v;
        sort(all(v),f);
        vi ans;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(v[i]==c[j]) ans.pb(j+1);
            }
        }
        for(int i:ans) cout<<i<<endl;
    }
    int main(){
        int T=1;
        //cin>>T;
        for(int i = 0; i < T; i++) solve(); 
    }

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, K;
    cin >> N >> K;

    vector<ll> p(N);
    rep (i, N) {
        cin >> p[i];
    }

    vector<double> sum(N+1);
    sum[0] = 0;
    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i-1]+p[i-1];
    }

    double ans = 0;
    for (int i = K; i <= N; i++) {
        ans = max(ans, sum[i]-sum[i-K]);
    }

    cout << fixed << setprecision(12) << (ans+K)/2.0 << endl;
    return 0;
}

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

using namespace std;

bool comp(pair<int, int> a, pair<int, int> b)
{
	if( a.first > b.first or (a.first == b.first and a.second < b.second) )
	{
		return true;
	}
	
	return false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	bool flag;
	int n, k, i, weight, value, j;
	vector<pair<int, int>> w;
	
	cin >> n >> k;

	long long int dp[k+1];

	memset(dp, 0, sizeof(dp));

	for(i=0; i<n; i++)
	{
		cin >> weight >> value;
		
		w.push_back(make_pair(weight, value));
	}

	for(j=0; j<n; j++)
	{
		for(int x=k; x>=w[j].first; x--)
		{
		 	dp[x] = max(dp[x], dp[x-w[j].first]+w[j].second);
		}	
	}
	
	cout << dp[k];

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define int long long
#define for0(i,n) for (int i=0; i<n; i++)
#define iter(c) for(auto it=c.begin(); it!=c.end(); it++)
#define vec(x) vector< x >
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define sqr(x) 1LL*(x)*(x)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif

using namespace std;

typedef long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

int freq[200005];
int depth[200005];

int32_t main()
{
    #ifdef DEBUG
    freopen("C.txt","r",stdin);
    //freopen("","w",stdout);
    #endif

    int n,m;
    read(n); read(m);
    vector<int> nums;
    for0(i,n) {
        int x;
        read(x);
        nums.pb(x);
    }

    ms(freq,0);
    ms(depth,0);
    iter(nums) {
        freq[*it]++;
    }
    for (int i=1; i<=n; i++) {
        for (int j=i; j>max(0,i-freq[i]); j--)
            depth[j]++;
    }
    //printa(depth,n+1)
    int ans = 0;
    for (int i=1; i<=n; i++) {
        if (depth[i] == 0)
            ans++;
    }
    //prl(ans)

    for0(i,m) {
        int idx,x;
        read(idx); read(x);
        idx--;
        int prev = nums[idx];
        nums[idx] = x;

        if (prev-freq[prev]+1 > 0) {
            depth[prev-freq[prev]+1]--;
            if (depth[prev-freq[prev]+1] == 0)
                ans++;
        }
        freq[prev]--;
        freq[x]++;
        if (x-freq[x]+1 > 0) {
            if (depth[x-freq[x]+1] == 0)
                ans--;
            depth[x-freq[x]+1]++;
        }
        cout<<ans<<endl;
        //nl
    }
    return 0;
}


Measured memory_bytes: 6256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class d{
  public static void Main(){
    long n = long.Parse(Console.ReadLine());
    IEnumerable<long> prime = calcprime(n);
    //Console.WriteLine("{0} = {1}",n, string.Join("x", prime));
    long ans = 0;
    long count = 0;
    long div;
    List<long> list = new List<long>();
    foreach(long i in prime){
      list.Add(i);
    }
    if(list.Count == 0){
      list.Add(1);
    }
    bool first = true;
    long temp = 0;
    for(int i=0; i<list.Count; i++){
      if(first){
        count = 1;
        temp = list[i];
        first = false;
        continue;
      }
      if(temp == list[i]){
        count++;
        continue;
      }
      else{
        //Console.WriteLine(count);
        div = 0;
        //Console.WriteLine("count: {0}",count);
        for(int j=1; count > 0; j++){
          count -= j;
          if(count >= 0){
            div++;
          }
        }
        ans += div;
        count = 1;
        temp = list[i];
      }
    }
    if(count != 0){
      div = 0;
      //Console.WriteLine("count: {0}",count);
      for(int j=1; count > 0; j++){
        count -= j;
        if(count >= 0){
          div++;
        }
      }
      ans += div;
    }
    if(n == 1){
      ans = 0;
    }
    Console.WriteLine(ans);
  }
  public static IEnumerable<long> calcprime(long n){
    long i=2;
    long temp = n;
    while(i*i <= n){
      if(temp%i == 0){
        temp /= i;
        yield return i;
      }
      else{
        i++;
      }
    }
    if(temp != 1){
      yield return temp;
    }
  }
}


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

int N;
int A[1010];
int ans = 0;

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < 2 * N; i++)scanf("%d",A + i);
    sort(A,A + 2 * N);
    for(int i = 0; i < 2 * N; i += 2)ans += A[i];
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
N=int(input())
lasta=0
headb=0
spec=0
cnt=0
for _ in range(N):
    s=str(input())
    for i in range(len(s)-1):
        if s[i:i+2]=="AB":
            cnt+=1
    if s[0]=="B" and s[-1]=="A":
        spec+=1
    elif s[-1]=="A":
        lasta+=1
    elif s[0]=="B":
        headb+=1
        
if abs(headb-lasta)>=spec:
    print(min(headb,lasta)+spec+cnt)   
elif lasta==0 and headb==0 and spec>0:
    print(spec-1+cnt)
elif lasta==0 and headb==0 and spec==0:
    print(cnt)
else:
    print(spec-abs(headb-lasta)+max(headb,lasta)+cnt)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int h = scanner.nextInt();
			int w = scanner.nextInt();
			if (h == 0 && w == 0)
				break;
			int[][] map = new int[h][w + 1];

			int wid;
			int max = 0;
			for (int i = 0; i < h; i++) {
				char[] a = scanner.next().toCharArray();
				for (int j = 1; j < w + 1; j++) {
					if (a[j - 1] == '.') {
						wid = Integer.MAX_VALUE;
						map[i][j] = map[i][j - 1] + 1;
						for (int k = 0; k <= i; k++) {
							wid = Math.min(wid, map[i - k][j]);
							if (wid == 0) {
								break;
							}
							max = Math.max(max, wid * (k + 1));
						}
					}
				}
			}
			System.out.println(max);
		}
	}
}

Measured memory_bytes: 28940
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if (A[p-1][0] <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - A[p-1][0]] + A[p-1][1])
# print(dp)
print(dp[N][W])


Measured memory_bytes: 171784