akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: usize = read().unwrap();
    let mut v: Vec<usize> = Vec::new();

    for _ in 0..n {
        v.push(read().unwrap());
    }

    let mut counter = 0;
    for v_i in v.iter() {
        if v_i % 2 == 0 {
            if (v_i % 3 == 0) | (v_i % 5 == 0) {
                counter += 1;
            } else {
                break;
            }
        } else {
            counter += 1;
        }
    }
    if counter == n {
        println!("APPROVED");
    } else {
        println!("DENIED");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mo=1000000007;
int t,b[5005],x,y,n,X,Z,s[5005]; LL f[5005],F[5005],w[5005][5005];
vector <int> a[5005];
LL po(LL x,int y){
	LL z=1;
	for (;y;y>>=1,x=x*x%mo)
	if (y&1) z=z*x%mo;
	return z;
}
void dfs(int x,int y){
	s[x]=1; int z=0;
	for (int i=0;i<a[x].size();++i)
	if (a[x][i]!=y) dfs(a[x][i],x),s[x]+=s[a[x][i]],z=max(z,s[a[x][i]]);
	z=max(z,n-s[x]);
	if (z<Z) Z=z,X=x;
}
LL C(int x,int y){
	return f[x]*F[y]%mo*F[x-y]%mo;
}
int main(){
	scanf("%d",&n); f[0]=1;
	for (int i=1;i<=n;++i) f[i]=f[i-1]*i%mo;
	F[n]=po(f[n],mo-2);
	for (int i=n-1;~i;--i) F[i]=F[i+1]*(i+1)%mo;
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	Z=n+10; dfs(1,0);
	for (int i=1;i<=n;++i)
	if (s[i]*2==n){
		printf("%lld\n",f[s[i]]*f[s[i]]%mo);
		return 0;
	}
	for (int i=0;i<a[X].size();++i) b[++t]=s[a[X][i]];
	for (int i=1;i<=t;++i) if (b[i]>s[X]) b[i]=n-s[X];
	b[++t]=1; X=0; w[0][0]=1;
	for (int i=1;i<=t;++i){
		for (int k=0;k<=b[i];++k)
		for (int j=0;j<=X;++j)
		(w[i][j+k]+=w[i-1][j]*C(b[i],k)%mo*C(b[i],k)%mo*f[k]%mo)%=mo;
		X+=b[i];
	}
	for (int i=0;i<=X;++i) (w[t][i]*=f[n-i])%=mo;
	for (int i=X;~i;--i)
		for (int j=i+1;j<=X;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	--t;
	for (int i=0;i<n;++i) (w[t][i]*=f[n-i-1])%=mo;
	for (int i=n-1;~i;--i)
		for (int j=i+1;j<n;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	printf("%lld\n",((w[t][0]+w[t+1][0])%mo+mo)%mo);
	return 0;
}

Measured memory_bytes: 194560
def input():
    import sys
    return sys.stdin.readline().rstrip()


def main():
    import math
    import collections
    import itertools

    n, m = map(int, input().split())
    ships = collections.defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        ships[a].append(b)
        ships[b].append(a)
        
    for ship_1 in ships[1]:
        if n in ships[ship_1]:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Measured memory_bytes: 51200
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define int long long
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18 * 5;


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

    int H;
    cin >> H;
    while(H != 0){
        vector< vector<int> > p(7, vector<int>(H));
        REP(i, H) p[0][i] = -1;
        REP(i, H)FOR(j, 1, 6) cin >> p[j][H-1-i];      // 列、行
        REP(i, H) p[6][i] = -1;
        
        int ans = 0;
        int tmp = -1;
        while(tmp != 0){
            tmp = 0;
            REP(i, H){
                int ct = 0, now = 0;
                FOR(j, 1, 7){
                    if(p[now][i] != p[j][i]){
                        if(ct >= 3){
                            tmp += ct*p[now][i];
                            FOR(k, now, j){
                                p[k][i] = -2;
                            }
                        }
                        ct = 1;
                        now = j;
                        
                    }else{
                        ct++;
                    }
                }
            }
            FOR(j, 1, 6){
                p[j].erase(remove(All(p[j]), -2), p[j].end());
                while(p[j].size() != H) p[j].pb(0);
            }
            ans += tmp;
        }
        // REP(i, H){
        //     FOR(j, 1, 6) cout << p[j][H-1-i];
        //     cout << "\n";
        // }
        cout << ans << "\n";
        cin >> H;
    }
    return 0;
}


Measured memory_bytes: 3076
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
pair<int,int>a[214514];
signed main(){
	ic(n)
	rep(0,i,n){
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a,a+n);
	rep(0,i,n){
		if(i==a[n-1].second){
			c(a[n-2].first)
		}
		else c(a[n-1].first)
	}		
}	

Measured memory_bytes: 3200
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int[] t = new int[n];
      	for(int i = 0; i < n; i++){
        	t[i] = sc.nextInt();
        }
      	int m = sc.nextInt();
      	int[] p = new int[m];
      	int[] x = new int[m];
      	for(int i = 0; i < m; i++){
        	p[i] = sc.nextInt();
          	x[i] = sc.nextInt();
        }
      
      	for(int i = 0; i < m; i++){
        	int sum = 0;
          	for(int j =0; j < n; j++){
            	if(j == p[i]-1){
                	sum += x[i];
                }else{
              		sum += t[j];
                }
            }
          	System.out.println(sum);
        }
    }
}

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

int main() {
  int n,m;
  cin>>n>>m;
  vector<vector<char>> s(n, vector<char>(m));
  rep(i,n){
    rep(j,m){
      cin>>s[i][j];
    }
  }
  vector<vector<int>> d(n, vector<int>(m)); 
  if(s[0][0]=='#'){
    d[0][0]++;
  }
  rep2(i,1,n){
    if(s[i][0]!=s[i-1][0]){
      d[i][0]=d[i-1][0]+1;
    }
    else{
      d[i][0]=d[i-1][0];
    }
  }
  rep2(j,1,m){
    if(s[0][j]!=s[0][j-1]){
      d[0][j]=d[0][j-1]+1;
    }
    else{
      d[0][j]=d[0][j-1];
    }
  }
  rep2(i,1,n){
    rep2(j,1,m){
      if(s[i-1][j]==s[i][j-1]){
        if(s[i][j]==s[i-1][j]){
          d[i][j]=min(d[i][j-1],d[i-1][j]);
        }
        else{
          d[i][j]=min(d[i-1][j],d[i][j-1])+1;
        }
      }
      else{
        if(s[i][j]==s[i-1][j]){
          int now=d[i][j-1]+1;
          d[i][j]=min(d[i-1][j],now);
        }
        else{
          int now=d[i-1][j]+1;
          d[i][j]=min(d[i][j-1],now);
        }
      }
    }
  }
  cout<<(d[n-1][m-1]+1)/2<<endl;
}      

Measured memory_bytes: 3660
#include <iostream>
#include <cstdio>
#include <list>
using namespace std;
list<int> L;
int main(void) {
  int N;
  int d;
  char command[20];
  scanf("%d",&N);
  for (int i=0; i<N; i++) {
    scanf("%s",command);
    if (command[0]=='i') {
      scanf("%d",&d);
      L.push_front(d);
    } else if (command[6]=='F') {
      L.pop_front();
    } else if (command[6]=='L') {
      L.pop_back();
    } else if (command[0]=='d') {
      scanf("%d",&d);
      for (list<int>::iterator it=L.begin(); it!=L.end(); it++) {
        if (d==*it) {
          L.erase(it);
          break;
        }
      }
    }
  }
  int i=0;
  for (list<int>::iterator it=L.begin(); it!=L.end(); it++) {
    if (i++) {
      printf(" ");
    }
    printf("%d",*it);   
  }
  printf("\n");
}

Measured memory_bytes: 34436
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
const int INF = 0x3f3f3f3f;

bool vis[10];
int ans=INF;
int n,m,r;
int R[10];
int d[205][205];
void dfs(int x,int cur)         //x是地点编号，cur是已经走过的距离
{
    bool flag = 1;
    for(int i=1;i<=r;i++) if(!vis[R[i]]) flag=0 ;
    if(flag&&cur<ans){              //已经经过了所有的r个点
        ans=cur;
        return;
    }

    for(int i=1;i<=r;i++){
        if(vis[R[i]]) continue;
        if(d[x][R[i]]>=INF) continue;
        vis[R[i]]=true;
        dfs(R[i],cur+d[x][R[i]]);
        vis[R[i]]=false;
    }
    return ;
}

int main()
{
    scanf("%d%d%d",&n,&m,&r);
    rep(i,1,r+1) scanf("%d",&R[i]);

    for(int i=0;i<205;i++) for(int j=0;j<205;j++) {
        if(i==j) d[i][j]=0;
        else d[i][j]=INF;
    }

    rep(i,0,m){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        d[u][v]=w;              //bidirectional双向边
        d[v][u]=w;
    }

    for(int k=1;k<=n;k++)       //floyd
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

    memset(vis,0,sizeof(vis));
    for(int i=1;i<=r;i++){      //枚举起点
        vis[R[i]]=true;
        dfs(R[i],0);
        vis[R[i]]=false;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 3988
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int c[3][3];

int main()
{
	rep(i, 3)
	{
		rep(j, 3)
		{
			in >> c[i][j];
		}
	}
	rep(a1, std::min(c[0][0], std::min(c[0][1], c[0][2]))+1)
	{
		rep(a2, std::min(c[1][0], std::min(c[1][1], c[1][2]))+1)
		{
			rep(a3, std::min(c[2][0], std::min(c[2][1], c[2][2]))+1)
			{
				int b1 = std::min(c[0][0]-a1, std::min(c[1][0]-a2, c[2][0]-a3));
				int b2 = std::min(c[0][1]-a1, std::min(c[1][1]-a2, c[2][1]-a3));
				int b3 = std::min(c[0][2]-a1, std::min(c[1][2]-a2, c[2][2]-a3));
				if (c[0][0] == a1 + b1
					&& c[0][1] == a1 + b2
					&& c[0][2] == a1 + b3
					&& c[1][0] == a2 + b1
					&& c[1][1] == a2 + b2
					&& c[1][2] == a2 + b3
					&& c[2][0] == a3 + b1
					&& c[2][1] == a3 + b2
					&& c[2][2] == a3 + b3)
				{
					out << "Yes" << std::endl;
					return 0;
				}

			}
		}
	}
	out << "No" << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC";
    else cout << "ABC";
}


Measured memory_bytes: 3548
#include<cstdio>
using namespace std;
typedef long long ll;

ll t, a, b, c, d;

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

int main() {
  scanf("%lld", &t);
  for (int i = 0; i < t; i++) {
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    ll minas = d % b;
    ll first = (a - c) % b;
    if (first != 0) first -= b;
    first += c;
    if (b > d || a < b || first < 0) {
      printf("No\n");
      continue;
    }
    if (minas == 0) {
      printf("Yes\n");
      continue;
    }
    minas -= b;
    ll g = gcd(-minas, b);
    ll temp = (b - first) % g;
    if (temp == 0) temp = g;
    if (c - (b - temp) < 0) printf("No\n");
    else printf("Yes\n");
  }
}


Measured memory_bytes: 128
/* You are being watched. */


//~ while (clock() <= 69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")

using namespace std;

//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template <typename T>
//~ using ordered_set =
  //~ tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define show(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
//using li = __int128;
//using uli = unsigned __int128;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

set <ll> sq;

bool okay(ll x, ll y, ll p) {
  return x * x * x * x * x - y * y * y * y * y == p;
}

ll get(ll x) {
  return x * x * x * x * x;
}

void solve() {
  int n; cin >> n;
  map <ll, ll> cnt;
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    int x; cin >> x;
    ans += cnt[i - x];
    cnt[x + i]++;
  }
  print(ans);
}

int main() {
  int t; t = 1;
  while(t--) solve();
}

Measured memory_bytes: 26240
import sys

n, k, *aaa = map(int, sys.stdin.buffer.read().split())
shortest = [-1] * n
v = 0
d = 0
while shortest[v] == -1:
    shortest[v] = d
    v = aaa[v] - 1
    d += 1
    if d == k:
        print(v + 1)
        exit()

first = shortest[v]
loop = d - first
remaining = (k - first) % loop
# print(v, first, loop, remaining + first, shortest)
ans = shortest.index(remaining + first) + 1
print(ans)


Measured memory_bytes: 27960
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    int diff = 0;
    for(int i=0; i<N; i++) {
        int p;
        cin >> p;
        if(p != i+1) {
            diff++;
        }
    }
    if(diff <= 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

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

vector<long long> func(long long N, vector<long long> A) {
	vector<long long> res(N);
	res[N - 1] = 0;

	stack<pair<int, int>> S;
	S.push(make_pair(N - 1, N));

	for(int i = N - 2; i >= 0; --i) {
		res[i] = res[i + 1];
		if(A[S.top().first] >= A[i]) {
			S.push(make_pair(i, i + 1));
		} else {
			do {
				while(A[S.top().first - 1] > A[S.top().first]) {
					res[i] += S.top().second - S.top().first;
					A[S.top().first] *= 4;

					if(S.top().second - S.top().first > 1 && S.top().second != N) {
						A[S.top().second - 1] *= 4;
					}
				}
				S.pop();
			} while(!S.empty() && A[S.top().first - 1] > A[S.top().first]);

			if(S.empty()) {
				S.push(make_pair(i, N));
			} else {
				S.push(make_pair(i, S.top().first));
			}
		}
	}

	for(int i = 0; i < N; ++i) {
		res[i] *= 2;
	}

	return res;
}

void solve(long long N, vector<long long> A){
	vector<long long> B = func(N, A);

	reverse(A.begin(), A.end());
	vector<long long> C = func(N, A);
	reverse(C.begin(), C.end());

	/*
	for(int i = 0; i < N; ++i) {
		cerr << B[i] << "," << C[i] << endl;
	}
	*/

	long long res = min(B[0], C[N-1] + N);
	for(int i = 1; i < N; ++ i) {
		res = min(res, i + B[i] + C[i - 1]);
	}
	cout << res << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
	}
	solve(N, A);
	return 0;
}



Measured memory_bytes: 9700
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=1000000007;
int i,j,k,n,m,f[2][4101][2],now,pre,ans,t1,t2;
void upd(int x,int y,int v){
	f[now][x][y]=(f[now][x][y]+v)%mm;
}
int main(){
	scanf("%d%d",&n,&m);memset(f,0,sizeof(f));now=0;pre=1;
	for (i=1;i<=n;i++) f[now][i][0]=1;
f[now][0][1]=1;
	for (i=0;i<m;i++){
		now^=1;pre^=1;memset(f[now],0,sizeof(f[now]));
		for (j=0;j<=n;j++)
		 for (k=0;k<=1;k++){
		 	if (j){
		 		upd(j-1,(j==1)?1:k,f[pre][j][k]);
				upd(j,(j==1)?1:k,f[pre][j][k]);
			}
			if (j<n){
				upd(j+1,(j==0)?1:k,f[pre][j][k]);
				upd(j,(j==0)?1:k,f[pre][j][k]);
			}
		 }
	}
	for (i=ans=0;i<=n;i++) ans=(ans+f[now][i][1])%mm;
	printf("%d\n",ans);
	return 0;
}

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

using namespace std;

int main() {
  long A;
  cin >> A;
  
  long l = static_cast<long>(log10(A));
  long sum = 0;
  for (long unit = 1; unit <= l; unit += 2) {
    long tmp = pow(10, unit);
    sum += tmp - (pow(10, unit - 1));
  }
  if (l % 2 == 0) {
    sum += (A - (pow(10, l) - 1));
  }
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    string a[100], b[100];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<m; i++){
        cin >> b[i];
    }
    bool isok = false;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j+m-1>=n || i+m-1>=n) continue;
            bool match = true;

            for(int y=0; y<m; y++){
                for(int x=0; x<m; x++){
                    if(a[j+y][i+x]!=b[y][x]) match=false;
                }
            }
            if(match) isok = true;

        }
    }

    if(isok){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

vector<int> to[200005];
vector<int> ans;

void dfs(int v, int p=-1) {
    for (int u : to[v]) {
        if (u == p) continue;
        ans[u] += ans[v];
        dfs(u,v);
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    rep(i,n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ans.resize(n);
    rep(i,q) {
        int p, x;
        cin >> p >> x;
        --p;
        ans[p] += x;
    }
    dfs(0);
    rep(i,n) {
        if (i != n-1) cout << ans[i] << " ";
        else cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 23424
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n,p;
	int i,j;
	int score[101];
	cin>>n;
	fill(score,score+101,0);
	for(i=0;i<n;i++){
		cin>>p;
		for(j=1;j<=p;j++){
			score[j]++;
		}
	}
	//cout<<score[100]<<endl;
	for(i=100;i>0;i--){
		if(score[i]>=i){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    string S; cin >> S;
    string pre(1, S[0]);
    string now = "";
    int ans = 1;
    FOR(i, 1, SZ(S)){
        now += S[i];
        if(now != pre){
            ans++;
            pre = now;
            now = "";
        }
    }

    Out(ans);

    return 0;
}


Measured memory_bytes: 720
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int len = S.length();
    cout << S[0] << len - 2 << S[len - 1] << endl;

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    int mode = 0;
    int ans = 0;
    for(int i = 1;i < n;i++)
    {
        if(mode == 0 && a[i] > a[i - 1])
        {
            mode = 1;
        }
        else if(mode == 0 && a[i] < a[i - 1])
        {
            mode = 2;
        }
        if(mode == 1 && a[i] < a[i - 1])
        {
            ans++;
            mode = 0;
        }
        else if(mode == 2 && a[i] > a[i - 1])
        {
            ans++;
            mode = 0;
        }
    }
    cout << ans + 1 << "\n";

    return 0;
}

Measured memory_bytes: 640
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

a = ni()
s = ns()

if a >= 3200:
    print(s)
else:
    print('red')

Measured memory_bytes: 3060
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    s =     _in[0]   # type:str
    t =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    s_arr = [_s for _s in s]
    t_arr = [_t for _t in t]
    s_arr.sort()
    t_arr.sort(reverse=True)
    s = ''.join(s_arr)
    t = ''.join(t_arr)
    if s==t:
        TF = 'Yes' if len(s)<len(t) else 'No'
    else:
        TF = 'Yes' if s<t else 'No'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)


Measured memory_bytes: 38256
use std::collections::HashMap;

use proconio::input;

fn main() {
    const LIMIT: usize = 1_000_000;
    input! {
        n: usize,
        mut a: [usize; n],
    }
    a.sort();
    let mut map = HashMap::new();
    for i in 0..n {
        *map.entry(a[i]).or_insert(0) += 1;
    }

    let mut done = vec![false; LIMIT + 1];
    let mut ret = 0;
    for i in 0..n {
        if done[a[i]] {
            continue;
        }
        if *map.get(&a[i]).unwrap() == 1 {
            ret += 1;
        }

        let mut tmp = a[i];
        while tmp <= LIMIT {
            done[tmp] = true;
            tmp += a[i];
        }
    }
    println!("{}", ret);
}


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

using namespace std;
typedef long long ll;

struct edge {
  int to, cost;
  edge() {}
  edge(int t, int c) : to(t), cost(c) {}
};

vector<edge> G[100010];
int d[100010];

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

  for (int i = 0; i < K; i++) {
    G[i].push_back(edge((i + 1) % K, 1));
    if (i * 10 % K == i) continue;
    G[i].push_back(edge(i * 10 % K, 0));
  }

  deque<int> deq;
  fill(d, d + K, 1 << 30);
  d[1] = 0;
  deq.push_front(1);
  while (!deq.empty()) {
    int v = deq[0];
    deq.pop_front();
    for (int i = 0; i < G[v].size(); i++) {
      edge e = G[v][i];
      if (d[e.to] <= d[v] + e.cost) continue;
      d[e.to] = d[v] + e.cost;
      if (e.cost == 0) {
        deq.push_front(e.to);
      } else {
        deq.push_back(e.to);
      }
    }
  }
  cout << d[0] + 1 << endl;

  return 0;
}

Measured memory_bytes: 6272
#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>

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


using namespace std;

// TC_REMOVE_BEGIN
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
// TC_REMOVE_END


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vector(istream& in, size_t n) {
    vector<T> ret(n);
    for (size_t i = 0; i < n; ++i) {
        ret[i] = next<T>(in);
    }
    return ret;
}


void solve(istream& in, ostream& out) {
    int n = next<int>(in);
    auto v = next_vector<int>(in, n);
    vector<int> temp;
    temp.push_back(v[0]);
    FOR(i, v.size()) if (i) {
        if (v[i] == v[i-1]) continue;
        temp.push_back(v[i]);
    }
    int res = 0;
    v = temp;
    if (v.size() <= 2) {
        out << 1 << endl;
        return;
    }
    int cur = v[1] > v[0] ? 1 : -1;
    for (int i = 2; i < v.size(); ++i) {
        int d = v[i] > v[i-1] ? 1 : -1;
        if (d != cur) {
            ++res;
            if (i + 1 < v.size()) {
                cur = v[i + 1] > v[i] ? 1 : -1;
            } else {
                cur = 0;
            }
        }
    }
    ++res;
    out << res << endl;
}


int main() {
    solve(cin, cout);
    return 0;
}



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

using namespace std;

bool flag = false;
int a, b;
vector<int> Vec(10);

void dfs(int pos)
{
	if(pos >= 10)
	{
		flag = true;
		return;
	}
	if(Vec[pos] > a)
	{
		a = Vec[pos];
		dfs(pos + 1);
	}
	if(Vec[pos] > b)
	{
		b = Vec[pos];
		dfs(pos + 1);
	}
}

void solve()
{
	int N;
	cin >> N;
	while(N--)
	{
		a = 0;
		b = 0;
		flag = false;
		for(int i = 0; i < 10; ++i)
		{
			cin >> Vec[i];
		}
		dfs(0);
		if(flag)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}

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

Measured memory_bytes: 1184
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
int val[maxn];
multiset<int> S;
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &val[i]);
		S.insert(val[i]);
	}
	int res = 0;
	while (!S.empty())
	{
		multiset<int>::iterator it = S.end();
		it--;
		int tmp = *it, need = 1;
		S.erase(S.find(tmp));
		while (need <= tmp) need *= 2;
		if (S.find(need - tmp) != S.end())
		{
			res++;
			S.erase(S.find(need - tmp));
		}
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 10368
#https://atcoder.jp/contests/abc159/tasks/abc159_d

import math

n=int(input())
a=list(map(int,input().split()))

count=[0 for i in range(n)]
for i in range(n):
    count[a[i]-1]+=1

cnb=[0 for i in range(n)]
sum=0
for i in range(n):
    if count[i]>=2:
        cnb[i]=int(count[i]*(count[i]-1)/2)
        sum+=cnb[i]

#print(count)
#print(cnb)
#print(sum)

for k in range(n):
    if count[a[k]-1]<2:
        print(sum)
    else:
        print(sum-cnb[a[k]-1]+int((count[a[k]-1]-1)*(count[a[k]-1]-2)/2))

Measured memory_bytes: 88512
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#include <deque>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <utility>
#include <memory>
#include <valarray>
#include <climits>

using namespace std;

using ll = long long int;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define scanInt(x) int x; scanf("%d", &(x)); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &(x)); getchar();
#define scanVecInt(A, N) vector<int> A(N); REP(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); REP(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    scanVecInt(A, N);
    sort(A.begin(), A.end());
    vector<pair<int, int>> B;
    REP(i, N){
        scanInt(Bi);
        B.emplace_back(Bi, lower_bound(A.begin(), A.end(), Bi) - A.begin());
    }
    sort(B.begin(), B.end(), [](const pair<int, int>& l, const pair<int, int>& r){return l.first < r.first;});
    map<int, ll, greater<int>> D;
    D.emplace(0, 0);
    for (auto& b : B){
        if (D.count(b.first)){
            D[b.first] += b.second;
        }else{
            D.emplace(b.first, b.second + D.upper_bound(b.first)->second);
        }
    }
    ll result = 0;
    REP(i, N){
        scanInt(Ci);
        result += D.upper_bound(Ci)->second;
    }
    cout << result << endl;
}


Measured memory_bytes: 7668
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <cmath>
#include <iomanip>
using namespace std;

int main(int argc, const char * argv[]) {
  int n, m;
  cin >> n >> m;
  vector<long long int> dp(n+1,0);
  vector<bool> a(n+1,true);
  long long int mod = 1e9+7;
  int tmp;
  for(int i = 0; i < m; i++){
    cin >> tmp;
    a.at(tmp) = false;
  }
  dp[0] = 1;
  for(int i = 0; i < n; i++){
    for(int j = i+1; j <= min(n, i + 2); j++){
      if(a.at(j) == true){
        dp[j] += dp[i];
        dp[j] %= mod;
      }
    }
  }
  
  cout << dp.at(n) << endl;
  return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 1001

int main(){
    int N, T;
    cin >> N >> T;
    vector<int> c(N), t(N);

    for (int i = 0; i < N; ++i) cin >> c[i] >> t[i];

    int min_cost = MAX;
    for (int i = 0; i < N; ++i){
        if (t[i] <= T && min_cost > c[i]) min_cost = c[i];
    }

    if (min_cost == MAX) cout << "TLE" << endl;
    else cout << min_cost << endl;

    return 0;
}

Measured memory_bytes: 256
/* ex7_3
  */

#include <stdio.h>
#include <stdlib.h>

int main(void){
    int height, width; //変数の定義
    int i, j;
    char **ptr; //入力の表を記憶する二次元配列
    int *row ,*col;


    scanf("%d %d", &height, &width);

    ptr = (char**)calloc(height, sizeof(char*));
    if(ptr == NULL){
        exit(1);
    }
    for(i = 0; i < height; i++){
        ptr[i] = (char*)calloc(width+1, sizeof(char));
        if(ptr[i] == NULL){
            exit(1);
        }
    }


    for(i=0; i<height; i++){ //入力の表を二次元配列に記憶
        for(j=0; j<width+1; j++){
            scanf("%c", &ptr[i][j]);
        }
    }

    row = (int*)calloc(height, sizeof(int));
    if(row ==NULL){
        exit(1);
    }

    col = (int*)calloc(width, sizeof(int));
    if(col ==NULL){
        exit(1);
    }


    for(i=0; i<height; i++){ //二次元配列を全探索して、#がある行、列を記憶
        for(j=0; j<width+1; j++){
            if (ptr[i][j] == '#'){
                row[i] = 1;
                col[j] = 1;
            }
        }
    }
    for(i=0; i<height; i++){
        if(row[i] == 1){ //i番目の行に#が含まれている
            for(j=0; j<width+1; j++){
                if(col[j] == 1){ //j番目の列にも#が含まれている
                    printf("%c", ptr[i][j]);//出力
                }
            }
            printf("\n"); //一行出力したら改行
        }
    }

    for(i = 0; i < height; i++){
        free(ptr[i]);
    }
    free(ptr);

   
        free(row);
        free(col);
    

    return 0;
}


Measured memory_bytes: 1676
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
using ll=long long;
using namespace std;
int main(){
    int n,t;
    cin >>n >> t;
    vector<ll> vec(n);
    for(int i=0;i<n;i++){
        ll x;
        cin >> x;
        vec[i]=x;
    }
    int count=0;
    int s=0;
    for(int i=0;i<n-1;i++){
       
        if(vec[i+1]-vec[i]>t){
            count += t;
            
        }else{
            count += vec[i+1]-vec[i];
        }
    }
    count += t;
    cout << count <<endl;
}

Measured memory_bytes: 1792
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

constexpr long long INF = 100000000000LL;

int main() {

    long long N, M, R;
    cin >> N >> M >> R;

    vector<int> r(R);
    for (int i = 0; i < R; i++) cin >> r[i], r[i]--;
    sort(r.begin(), r.end());

    vector<vector<long long>> G(N, vector<long long>(N, INF));
    for (int i = 0; i < N; i++) G[i][i] = 0;

    for (int i = 0; i < M; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        G[a][b] = c;
        G[b][a] = c;
    }

    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

    long long ans = LONG_LONG_MAX;
    do {
        long long cost = 0;
        for (int i = 0; i < R - 1; i++) cost += G[r[i]][r[i + 1]];
        ans = min(ans, cost);
    } while (next_permutation(r.begin(), r.end()));

    cout << ans <<endl;

    return 0;
}
































Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include <cmath>
using namespace std;

int main(){
    long int a,b,c;
    cin>>a>>b>>c;
    if (4*a*b<(c-a-b)*(c-a-b)&&c-a-b>0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
A = [None] * 3

for i in range(3):
    A[i] = list(map(int, input().split()))

N = int(input())

for n in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if A[i][j] == b:
                A[i][j] = 0

is_bingo = 'No'

for i in range(3):
    if A[i][0] == A[i][1] == A[i][2]:
        is_bingo = 'Yes'

for j in range(3):
    if A[0][j] == A[1][j] == A[2][j]:
        is_bingo = 'Yes'

if A[0][0] == A[1][1] == A[2][2]:
    is_bingo = 'Yes'

if A[0][2] == A[1][1] == A[2][0]:
    is_bingo = 'Yes'

print(is_bingo)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vii;
const ll INF = 12345678910;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,c;
  cin>>n>>c;
  ll colorCount[3][c+1] = {0}; // For each mod finding the color.
  for(int i=1; i<=c; ++i){
    colorCount[0][i] = 0;
    colorCount[1][i] = 0;
    colorCount[2][i] = 0;
  }
  ll cost[c+1][c+1];
  ll matrix[n+1][n+1];
  for(int i=1; i<=c; ++i){
    for(int j=1; j<=c; ++j){
      cin>>cost[i][j];
    }
  }
  for(int i=1; i<=n; ++i){
    for(int j=1; j<=n; ++j){
      cin>>matrix[i][j];
      colorCount[(i+j)%3][matrix[i][j]]++;
    }
  }
  ll ans = INF;
  ll a1 = 0 , a2 =0, a3= 0;
  for(int c1 = 1; c1<=c ; ++c1){
    for(int c2 = 1; c2 <= c; ++c2){
      for(int c3 = 1; c3 <= c; ++c3){
        if( c1 != c2 and c2 != c3 and c3 !=c1 ){
          ll temp_ans = 0;
          for(int i=1; i<=c; ++i){ temp_ans += (colorCount[0][i]) * (cost[i][c1]);}
          for(int j=1; j<=c; ++j){ temp_ans += (colorCount[1][j]) * (cost[j][c2]);}
          for(int k=1; k<=c; ++k){ temp_ans += (colorCount[2][k]) * (cost[k][c3]);}
          // ans = min(ans, temp_ans);
          if( temp_ans < ans){ ans = temp_ans ; a1 =c1 ; a2 =c2; a3 = c3;}
        }
      }
    }
  }
  cout<<ans<<"\n";
  // cout<<a1<<" "<<a2<<" "<<a3<<"\n";
  return 0;
}


Measured memory_bytes: 2176
#include<iostream>
#include<algorithm>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(),(x).end()

using ll = long long;

using namespace std;

template<typename T>
void dump(T *arr, int h, int w){
	rep(i,h){
		rep(j,w) cout << arr[i][j] << "\t";
		cout << "\n";
	}
}

template<typename T>
void dump(T *arr, int a){
	rep(i,a) cout << arr[i] << "\t";
	cout << "\n";
}

const int INF = 1e5;

int h[INF];
int maxs[INF], mins[INF];

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

	rep(i,n){
		cin >> h[i];
	}

	int tmin = h[n-1] ,tmax = h[0];
	maxs[0] = tmax, mins[n-1] = tmin;
	repi(i,1,n){
		tmin = min(h[n-1-i],tmin);
		tmax = max(h[i],tmax);
		mins[n-1-i] = tmin;
		maxs[i] = tmax;
	}

	rep(i,n){
		if(maxs[i] > mins[i]+1){
			puts("No");
			return 0;
		}
	}
	puts("Yes");

	return 0;
}


Measured memory_bytes: 1408
#![allow(unused_imports)]
#![allow(unused_macros)]
use itertools::Itertools;
use std::cmp::{max, min};
use std::collections::*;
use std::i64;
use std::io::{stdin, Read};
use std::usize;

trait ChMinMax {
    fn chmin(&mut self, other: Self);
    fn chmax(&mut self, other: Self);
}
impl<T> ChMinMax for T
where
    T: PartialOrd,
{
    fn chmin(&mut self, other: Self) {
        if *self > other {
            *self = other
        }
    }
    fn chmax(&mut self, other: Self) {
        if *self < other {
            *self = other
        }
    }
}

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, a: [i64; n]);
    let a: Vec<i64> = a;
    if a.iter().all(|&x| x < n as i64) {
        println!("{}", 0);
        return;
    }
    let mut ok = i64::MAX / 10;
    let mut ng = 0;
    let d = n as i64 + 1;
    let check = |m| {
        let k = n as i64 - m - 1;
        let mut ret = 0;
        for &ai in &a {
            let ai = ai - k;
            if ai > 0 {
                ret += ai / d + if ai % d == 0 { 0 } else { 1 };
            }
        }
        ret <= m
    };
    while ok - ng > 1 {
        let m = (ok + ng) / 2;
        if check(m) {
            ok = m
        } else {
            ng = m
        }
    }
    for i in max(ok - 10000, 0)..ok {
        if check(i) {
            ok = i;
            break;
        }
    }
    println!("{}", ok);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <iostream>

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 1000000007;

class mint{
public:
  ll x;
  mint(ll x=0) : x(x%mod){}
  mint& operator+=(const mint rhs){
    x += rhs.x;
    while(x >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint rhs){
    x -= rhs.x;
    while(x < 0) x += mod;
    return *this;
  }
  mint & operator*=(const mint rhs){
    (x *= rhs.x) %= mod;
    return *this;
  }
  mint operator+(const mint rhs) const {
    mint res(*this);
    return res += rhs;
  }
  mint operator-(const mint rhs) const {
    mint res(*this);
    return res -= rhs;
  }
  mint operator*(const mint rhs) const {
    mint res(*this);
    return res *= rhs;
  }
  bool operator>(const ll rhs) const {
    return x > rhs;
  }
  bool operator<(const ll rhs) const {
    return x < rhs;
  }
  bool operator>=(const ll rhs) const {
    return x >= rhs;
  }
  bool operator<=(const ll rhs) const {
    return x <= rhs;
  }
  bool operator==(const ll rhs) const {
    return x == rhs;
  }
  bool operator!=(const ll rhs) const {
    return x != rhs;
  }
  friend ostream& operator<<(ostream& os,const mint rhs){
    os << rhs.x;
    return os;
  }
};

#define rep(index,num) for(int index=0;index<num;++index)

int main(){
  int N;
  std::cin >> N;
  int n = N%10;
  if(n==2 || n==4 || n==5 || n==7 || n==9) std::cout << "hon" << std::endl;
  else if(n==0 || n==1 || n==6 || n==8) std::cout << "pon" << std::endl;
  else std::cout << "bon" << std::endl;
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 1e6;
    vector<bool> isprime(n, true);
    isprime[1] = false;
    for(int i = 2; i < n; i++)
    {
        if(isprime[i])
        {
            for(int j = 2*i; j < n; j+=i)
            {
                isprime[j] = false;
            }
        }
    }
    vector<int> sum(n, 0);
    for(int i = 1; i < n; i++)
    {
        sum[i] = sum[i-1];
        if(i % 2 == 1 && isprime[i] && isprime[(i+1)/2])
        {
            sum[i]++;
        }
    }
    int q;
    cin >> q;
    vector<int> l(q);
    vector<int> r(q);
    for(int i = 0; i < q; i++)
    {
        cin >> l[i] >> r[i];
    }
    for(int i = 0; i < q; i++)
    {
        cout << sum[r[i]] - sum[l[i]-1] << endl;
    }
}


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

using namespace std;

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

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#ifdef Debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#else
#define dump(x)
#endif

int main(){
	string s;
	while(cin>>s){
		rep(i,3){
			if(  s[i*3]!='s' &&  s[i*3+0]==s[i*3+1] && s[i*3+1]==s[i*3+2] ){
				cout<<s[i*3]<<endl;
				goto next;
			}
		}
		rep(i,3){
			if(  s[i]!='s' &&  s[i]==s[i+3] && s[i+3]==s[i+6] ){
				cout<<s[i]<<endl;
				goto next;
			}
		}
		if( s[4]!='s' ){
			if(s[0]==s[4] && s[4]==s[8]){
				cout<<s[4]<<endl;
				goto next;
			}
			if(s[2]==s[4] && s[4]==s[6]){
				cout<<s[4]<<endl;
				goto next;
			}
		}

		cout<<'d'<<endl;
next:;
	}
	return 0;
}

Measured memory_bytes: 1176
n,l = gets.split.map(&:to_i)
ans = []
(1..n).each do |i|
    ans << l + i - 1
end

if ans.include?(0)
  p ans.inject(:+)
elsif ans.inject(:+) > 0
  p ans.inject(:+) - ans.min
else
  p ans.inject(:+) - ans.max
end

Measured memory_bytes: 1788
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0154

"""
import sys
from sys import stdin
input = stdin.readline


def solve(m, cards, g, guesses):
    ans = []

    cards.append([0, 0])
    cards.sort()
    W = max(guesses) + 1

    dp = [0] * W
    dp[0] = 1
    for i in range(1, m+1):
        card_num = cards[i][0]
        card_rem = cards[i][1]
        for j in range(W-1, 0, -1):
            for k in range(1, card_rem+1):
                if card_num*k <= j:
                    dp[j] += dp[j-card_num*k]

    for gg in guesses:
        ans.append(dp[gg])
    return ans


def main(args):
    # m = 5
    # cards = [[1, 10], [5, 3], [10, 3], [25, 2], [50, 2]]
    # g = 4
    # guesses = [120, 500, 100, 168]

    while True:
        m = int(input())
        if m == 0:
            break
        cards = []
        for _ in range(m):
            a, b = map(int, input().split())
            cards.append([a, b])
        g = int(input())
        guesses = [int(input()) for _ in range(g)]
        ans = solve(m, cards, g, guesses)
        print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])



Measured memory_bytes: 5632
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = sc.nextInt();

		int sum = 0;
		int prev = 0;
		for (int i = 0; i < n; i++) {
			int s = sc.nextInt();
			sum += Math.min(s - prev, t);
			prev = s;
		}

		System.out.println(sum + t);
	}
}

Measured memory_bytes: 62216
/*
  NAME : RISHABH SINGH
  INSTITUTION : DELHI TECHNOLOGICAL UNIVERSITY
*/
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int, int>
#define bi __builtin_inf()
#define ll long long
#define mp make_pair
#define ss second
#define pb push_back
#define ff first
#define speed_cubing ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define um unordered_map
#define us unordered_set
#define bp __builtin_popcount
#define ld long double
#define rep(n) for (int i = 0; i < n; i++)
#define pll pair<ll, ll>
#define mx = 1e18;
#define lb(v, val) (lower_bound(v.begin(), v.end(), val) - v.begin())
#define ub(v, val) (upper_bound(v.begin(), v.end(), val) - v.begin())
#define PI 3.1415926535
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
ll powmod(ll base,ll exp,ll MOD){ll res=1;while(exp>0){if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return (res%MOD);}
#define sz(v) (int)v.size()
#define endl '\n'
const int mod = 1e9+7;
ll mul_inv(ll a,ll b = mod) {ll t1=a,t2=b,t3,v1=1,v2=0,v3;while(t2!=1){ll x=t1/t2;t3=t1-x*t2;v3=v1-x*v2;t1=t2,t2=t3;v1=v2,v2=v3;}return(v2+b)%b;}
const int N = 1e6+5;
int arr[N];

int32_t main(){
   
   speed_cubing

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

   int w = 0;

   for(auto x:s)
      if(x=='W')
        w++;

   int t = 0;

   for(int i=0;i<n-w;i++){
      if(s[i]=='W')
        t++;
   }

   cout<<t;     

   return 0;
}

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

typedef long long ll;

int main()
{

    ll n,a,b,cal,mn=100000,i,c;
    string st;
    cin >> st;
    for(i=0; i<st.size()-2; i++)
    {
        a=st[i]-48;
        b=st[i+1]-48;
        c=st[i+2]-48;
        cal=(a*100)+(b*10)+c;
        mn=min(mn,abs(753-cal));
    }
    cout << mn << "\n";


    return 0;
}



Measured memory_bytes: 256
def main():
    h, w = list(map(int, input().split()))
    A = [['.'] * (w + 2)] + [['.', ] + list(input()) + ['.', ] for _ in range(h)] + [['.'] * (w + 2)]
    i, j = 1, 1
    while True:
        A[i][j] = '.'
        if i == h and j == w:
            break
        if A[i + 1][j] == A[i][j + 1]:
            print('Impossible')
            exit()
        if A[i + 1][j] == '#':
            i += 1
        else:
            j += 1
    for a in A:
        if any([i == '#' for i in a]):
            print('Impossible')
            break
    else:
        print('Possible')

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256