akhauriyash/Code-Regression huggingface dataset:
const BKRT = "\n";
const SPAC = " ";
const NOSP = "";

function Main(input){
	input = [].concat(...input.split(BKRT).map(a=>a.split(SPAC)));
  const strShift = ()=>input.shift();
  const intShift = ()=>~~input.shift();
  
  var A = intShift();
  var B = intShift();
  var C = intShift();
  
  var X = intShift();
  
  var sum = 0;
  
  for(var a = 0; a <= A ; a++)
  for(var b = 0; b <= B ; b++)
  for(var c = 0; c <= C ; c++){
  	if(500 * a + 100 * b + 50 * c == X)sum++;
  }
  
  return ~~sum;
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
30
40
50
6000
`);

Measured memory_bytes: 7372
#include <stdio.h>
#include <stdlib.h>
typedef struct Tree{
  int key;
  int parent;
  int left;
  int right;
}Tree;

int main(){
  int H,i,j,store;
  Tree *T;
  scanf("%d",&H);
  T=(Tree*)malloc(sizeof(Tree)*H);
  for(i=0;i<H;i++){
    T[i].key=2000000001;
    T[i].parent=-1;
    T[i].left=-1;
    T[i].right=-1;
  }
  
  for(i=0;i<H;i++){
    scanf("%d",&T[i].key);
    T[i].parent=(i+1)/2-1;
    if(2*i+1<H){
      T[i].left=2*i+1;
      if(2*i+2<H)
	T[i].right=2*i+2;
    }
  }
  
  for(i=T[H-1].parent;i!=-1;i--){
    j=i;
    while(T[j].left!=-1){
      if(T[T[j].left].key>T[T[j].right].key){
	if(T[T[j].left].key>T[j].key){
	  store=T[j].key;
	  T[j].key=T[T[j].left].key;
	  T[T[j].left].key=store;
	  j=T[j].left;
	}
	else
	  break;
      }
      else
	if(T[T[j].right].key>T[j].key){
	  store=T[j].key;
	  T[j].key=T[T[j].right].key;
	  T[T[j].right].key=store;
	  j=T[j].right;
	}
	else
	  break;
    }
  }

  
  for(i=0;i<H;i++){
    printf(" %d",T[i].key);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 8416
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    string s;
    cin >> s;
    cout << s[0] <<s.size()-2<<s[s.size()-1]<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
A = [read_int()[0] for _ in range(N)]

def solve() -> str:

    M = max(A)

    semi_M = 0
    num_of_M = 0
    for i in range(N):
        if A[i] == M:
            num_of_M += 1
        else:
            semi_M = max(semi_M, A[i])

    for i in range(N):
        if A[i] == M and num_of_M == 1:
            print(semi_M)
        else:
            print(M)
    return

if __name__ == "__main__":
    solve()

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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  string s; cin >> s;
  char h = s[0];
  char l = s[s.size()-1];
  string x = to_string(s.size()-2);

  string ans ="";
  ans+=h;
  ans+=x;
  ans+=l;

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3652
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

//const long long int MOD = 1000000007;
const long long int MOD = 1000003;
//const int MOD = 998244353;
//const long long int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

long long int gcd(long long int a, long long int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

long long int extended_gcd(long long int a, long long int b, long long int c, long long int d, long long int m) {
	long long int ret = 0;
	if (c == 1)return d;
	ret = extended_gcd(c, d, a%c, (b + (MOD *MOD / m)*m - ((a / c) % m)*(d%m)) % m, m);
	return ret;
}

long long int extended_gcd(long long int a, long long int b) {
	int g = gcd(a, b);
	a /= g;
	b /= g;
	long long int box = a % b;
	long long int bag = b - (a % b);
	long long int bbox = 1;
	long long int bbag = b - 1;
	return extended_gcd(box, bbox, bag, bbag, b)*g;
}

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

	int T;
	cin >> T;
	vector<long long int>by(MOD, 1);
	vector<long long int>rev(MOD, 1);
	for (int i = 2; i < MOD; i++) {
		by[i] = by[i - 1] * i;
		by[i] %= MOD;
		rev[i] = power(by[i], MOD - 2, MOD);
	}
	while (T--) {
		cin >> N >> M >> K;
		if (!M) {
			cout << power(N, K, MOD) << endl;
			continue;
		}
		if (K >= MOD) {
			cout << 0 << endl;
			continue;
		}
		if (!N) {
			cout << 0 << endl;
			continue;
		}
		long long int box = extended_gcd(M, MOD);
		box *= N;
		box %= MOD;
		long long int ed = box + K - 1;
		if (ed >= MOD) {
			cout << 0 << endl;
			continue;
		}
		long long int ans = by[ed];
		ans *= power(by[box - 1], MOD - 2, MOD);
		ans %= MOD;
		ans *= power(M, K, MOD);
		ans %= MOD;
		cout << ans << endl;
	}
}

Measured memory_bytes: 18176
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def li():  return list(mi())

def main():
    a,b,c,d = mi()

    p1 = max(a,b)*max(c,d)
    p2 = max(a,b)*min(c,d)
    p3 = min(a,b)*min(c,d)
    p4 = min(a,b)*max(c,d)

    print(max(p1,p2,p3,p4))
    # pass


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Measured memory_bytes: 9396
import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,m=map(int,input().split())

h=list(map(int,input().split()))

p=[1]*n

for i in range(m):
	a,b=map(int,input().split())
	if h[a-1]>h[b-1]:
		p[b-1]-=1
	elif h[a-1]<h[b-1]:
		p[a-1]-=1
	else:
		p[b-1]-=1
		p[a-1]-=1
		
print(p.count(1))

Measured memory_bytes: 84676
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
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; }
const int INF = 1e18;


signed main(){
    int n, m; cin >> n >> m;
    vector<int> G[n];
    vector<bool> used(n,false);
    deque<int> ans;
    int left_t,right_t;
    REP(i,m){
        int a, b; cin >> a >> b; a--; b--;
        if(i == 0){
            ans.push_front(a);
            ans.push_back(b);
            left_t = a;
            right_t = b;
            used[a] = used[b] = true;
        }
        G[a].eb(b);
        G[b].eb(a);
    }
    labl1:;
    for(auto v:G[left_t]){
        if(!used[v]){
            ans.push_front(v);
            used[v] = true;
            left_t = v;
            goto labl1;
        }
    }
    labl2:;
    for(auto v:G[right_t]){
        if(!used[v]){
            ans.push_back(v);
            used[v] = true;
            right_t = v;
            goto labl2;
        }
    }
    int k = SZ(ans);
    cout << k << '\n';
    REP(i,k){
        cout << ans.front()+1 << " ";
        ans.pop_front();
    }
}

Measured memory_bytes: 7168
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		double n = 0;
		if(b == 100) {
			n = Math.pow(100, a) * b + Math.pow(100, a);
		}else {
			n = Math.pow(100, a)*b;
		}
		System.out.println((int)n);
	}
}


Measured memory_bytes: 25172
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main(){
    int N;  cin>>N;
    vector<int> A1(N),A2(N);
    for(int i=0;i<N;++i){
        cin>>A1[i];
    }
    for(int i=0;i<N;++i){
        cin>>A2[i];
    }
    int ans=0;
    for(int i=0;i<N;++i){
        int sum=0;
        if(i==0){
            sum+=A1[0];
            for(int j=0;j<N;++j){
                sum+=A2[j];
            }
        }
        else if(i==N-1){
            for(int j=0;j<N;++j){
                sum+=A1[j];
            }
            sum+=A2[N-1];
        }
        else{
            for(int j=0;j<i+1;++j){
                sum+=A1[j];
            }
            for(int j=i;j<N;++j){
                sum+=A2[j];
            }
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define run(a) for(int k=head[a];k;k=e[k].ne)
#define v e[k].t
#define clr(a) memset(a,0,sizeof(a));
#define il inline
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back 
#define w1 first
#define w2 second
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
typedef double db;
typedef long long ll;typedef long double ld;typedef unsigned long long ull;
typedef pair<ll,ll> pa;
const int N=3e2+5,M=5e3+5,INF=1e9,mod=1e9+7;
const ll linf=1e18;const double eps=1e-8,pi=acos(-1);
il int gmin(int &a,int b){if(a>b)a=b;}il ll gmin(ll &a,ll b){if(a>b)a=b;}il int gmax(int &a,int b){if(a<b)a=b;}il ll gmax(ll &a,ll b){if(a<b)a=b;}
il void read(ll&x){ll f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il ll read(ll&x,ll&y){read(x);read(y);}
il void read(int&x){int f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il int read(int&x,int&y){read(x);read(y);}
il void read(int&a,int&b,int&c){read(a);read(b);read(c);}il void read(ll&a,ll&b,ll&c){read(a);read(b);read(c);}
il int read(){int x;read(x);return x;}
il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}il ll qpow(ll a,ll b){ll ret=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
il ll qmul(ll a,ll b,ll p){ll ret=0;for(;b;b>>=1,a=(a<<1)%p)if(b&1)adm(ret,a,p);return ret;}il ll qmul(ll a,ll b){ll ret=0;for(;b;b>>=1,a=(a<<1)%mod)if(b&1)adm(ret,a,mod);return ret;}
il void judge(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);}
int a[N][N],n,m,c[N],bad[N],pt[N];
int main(){
	read(n,m);rep(i,1,n)rep(j,1,m)read(a[i][j]);
	int ans=n;
	rep(i,1,n)pt[i]=1;
	re(t,1,m){
		clr(c);
		rep(i,1,n){
			while(bad[a[i][pt[i]]])pt[i]++;
			c[a[i][pt[i]]]++;
		}int mx=0,id=0;
		rep(i,1,m)if(c[i]>mx){mx=c[i];id=i;}
		gmin(ans,mx);
		bad[id]=1;
	}cout<<ans<<endl;
}

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

using namespace std;

#define allof(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define exists(s, e) (s.find(e)!=s.end())
#define INF 0x3f3f3f3f
#define endl '\n'
#define mp make_pair
#define watch(x) cout << (#x) << " is " << (x) << endl;

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

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

void solve() {
    string s; cin >> s;
    int minDiff = INT_MAX;
    for(int i=0; i<sz(s)-2; i++) {
        string sub = s.substr(i, 3);
        int val = stoi(sub);
        minDiff = min(minDiff, abs(val-753));
    }
    cout << minDiff << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int MAX = 2600000;
int mod = 998244353;
int n, m;
int fact[MAX];
int inv[MAX];
int factInv[MAX];

void initFact() {
	int i;
	
	fact[0] = fact[1] = 1;
	factInv[0] = factInv[1] = 1;
	inv[1] = 1;
	for (i = 2; i <= 3 * m + n; i++) {
		fact[i] = (i * fact[i - 1]) % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		factInv[i] = factInv[i - 1] * inv[i] % mod;
	}
}

int comb(int n, int k) {
	if (k > n) return 0;
	return fact[n] * factInv[n - k] % mod * factInv[k] % mod;
}

signed main() {
	cin >> n >> m;
	initFact();
	
	int x;
	int ng = 0;
	for (x = 2 * m + 1; x <= 3 * m; x++) {
		int res = n * comb(3 * m - x + n - 2, n - 2) % mod;
		ng += res;
		ng %= mod;
	}
	
	//奇数がx個
	for (x = m + 1; x <= n; x++) {
		if (x > 3 * m) break;
		if ((3 * m - x) % 2 != 0) continue;
		int res = comb((3 * m - x) / 2 + n - 1, n - 1) * comb(n, x) % mod;
		ng += res;
		ng %= mod;
	}
	
	int all = comb(3 * m + n - 1, n - 1);
	int ans = (all - ng + mod) % mod;
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 60416
N,X = map(int,input().split())
res = 0
mod = 10** 9 + 7
S = list(map(int,input().split()))
S.sort()
dp = [[0 for i in range(10**5+1)] for j in range(201)]
#dp[X][I] = Sの前X個だけの集合(無視あり)に対してIstartで得られる集合の個数
dp[0][X] = X
for i in range(10**5+1):
    dp[1][i] = i%S[0]
for i in range(2,N+1):
    for j in range(10**5+1):
        dp[i][j] = (dp[i-1][j%S[i-1]] + (i-1)* dp[i-1][j] ) %mod

ans = dp[N][X]
print(ans)

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

int main(){
  int n,m;
  cin >> n >> m;
  int l1 = 0, r1 = 1000000;
  rep(i,m){
    int l, r;
    cin >> l >> r;
    l1 = max(l1, l);
    r1 = min(r1, r);
  }
  if(r1-l1 < 0) cout << 0 << endl;
  else cout << r1-l1+1 << endl;
}


Measured memory_bytes: 3616
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::string s;
    std::string result;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'B') {
            if (result.size() > 0) {
                result.erase(result.end() - 1);
            }
        } else {
            result += s[i];
        }
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 760
require 'prime'
require 'set'
require 'tsort'
include Math
ALP = ('a'..'z').to_a
INF = 0xffffffffffffffff
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def pr?(num);              Prime.prime?(num)                          end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end

x=gif
mx=1
repl 2, x do |xx|
  tx = xx * xx
  next if tx > x
  while  tx*xx <= x
    tx  *= xx
  end
  mx = max mx,tx
end

puts mx


Measured memory_bytes: 2428
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long x;
    cin>>x;
    long long low=1,high=x,ans=-1;
    while(low<=high)
    {
        long long mid=(low+high)/2;
        long long g=mid*6+(mid-1)*5;
        long long h=g+5;
        if(g>=x)
        {
            ans=2*mid-1;
            high=mid-1;
        }
        else if(h>=x)
        {
            ans=2*mid;
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define HUGE_NUM 9999999999999999

int N;
ll W[4001],dp[4000][4000];
int loc[4000][4000];

int main(){

	scanf("%d",&N);
	for(int i = 0; i < N; i++){
		for(int k = i; k < N; k++)dp[i][k] = HUGE_NUM;
	}

	W[0] = 0;
	for(int i = 1; i <= N; i++){
		scanf("%lld",&W[i]);
		W[i] += W[i-1];
	}

	for(int i = 0; i < N; i++){
		dp[i][i] = 0;
		loc[i][i] = i;
	}

	int right;
	ll tmp;
	for(int length = 2; length <= N; length++){
		for(int left = 0; left+length-1 <= N-1; left++){
			right = left+length-1;
			for(int mid = loc[left][right-1]; mid <= loc[left+1][right]; mid++){
				tmp = dp[left][mid]+dp[mid+1][right]+W[right+1]-W[left];
				if(tmp < dp[left][right]){
					dp[left][right] = tmp;
					loc[left][right] = mid;
				}
			}
		}
	}

	printf("%lld\n",dp[0][N-1]);
}

Measured memory_bytes: 125716
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int main(){
  int n,m,a,b;
  int ans = 0;
  cin >> n >> m;
  
  vector<P> q;
  
  for(int i=0;i<m;i++){
    cin >> a >> b;
    q.push_back(make_pair(b,a));
  }
  sort(q.begin(),q.end());
    
  int tmp = -1,x = 0;
  while(x<m){
    if(q.at(x).second > tmp){
      tmp = q.at(x).first - 1;
      ans++;
    }
    x++;
  }
  
  cout << ans << endl;
}


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

int main(){
  int n,m,x;
  int a[101];
  cin >> n >> m >> x;
  int i,cost1,cost2;
  cost1=0;
  cost2=0;
  for(i=0;i<m;i++){
    int a[i];
    cin >> a[i];
    if (a[i]<x){
     cost1++;
    }
    else if (a[i]>x){
      cost2++;
    }
  }
  if (cost1>cost2){
    cout << cost2 << endl;
  }
  else {
    cout << cost1 << endl;
  }
}
    
      
      
      
      
      
    

Measured memory_bytes: 256
import math

n, M= map(int,input().split())
#AB=[]
#N = int(input())
#C = input()
parents = [-1] * n

def find( x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

def size( x):
    return -parents[find(x)]

def same( x, y):
    return find(x) == find(y)

def members( x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def roots():
    return [i for i, x in enumerate(parents) if x < 0]

def group_count():
    return len(roots())

def all_group_members():
    return {r: members(r) for r in roots()}

def __str__():
    return '\n'.join('{}: {}'.format(r, members(r)) for r in roots())
 
C = []
for i in range(M):
    A, B = map(int,input().split())
    union(A-1,B-1)
    '''
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
    '''
print(group_count()-1)


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

int main() {
	char a;
	cin >> a;

	if(a >= 65 && a <= 90)
		cout << "A" << endl;
	else
		cout << "a" << endl;

	return 0;
}

Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld=long double;
 
int main(){
    int n,k;
    cin>>n;
    vector<pair<int ,int>> v(n);
    
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v[i]={x,i+1};
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        cout<<v[i].second<<" ";
    }
    
    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define rep(i, j) FOR(i, 0, j, 1)
#define rrep(i, j) RFOR(i, j, 0, 1)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define endl "\n"
#define MOD 1000000007
#define DEB(x) cout<<"##"<<x<<"##"<<endl;

void solve()
{
    int nr,ng,nb;
    cin>>nr>>ng>>nb;
    int r[nr],g[ng],b[nb];
    rep(i,nr)
    cin>>r[i];
    rep(i,ng)
    cin>>g[i];
    rep(i,nb)
    cin>>b[i];
    sort(r,r+nr);
    sort(g,g+ng);
    sort(b,b+nb);
}
void b()
{
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            return;
        }
    }
    cout<<"NG";
   
}
int main() 
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
    b();
    return 0;
    int t;
    cin>>t;
    while(t--)
    b();
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
#define rad2deg(a) ((a)/M_PI * 180.0)
#define deg2rad(a) ((a)/180.0 * M_PI)
const std::string yes = "Yes";
const std::string no  = "No";

int main(){
    int x;
    std::cin >> x;
    if(x<=599){std::cout << 8 << "\n";}
    else if(x<=799){std::cout << 7 << "\n";}
    else if(x<=999){std::cout << 6 << "\n";}
    else if(x<=1199){std::cout << 5 << "\n";}
    else if(x<=1399){std::cout << 4 << "\n";}
    else if(x<=1599){std::cout << 3 << "\n";}
    else if(x<=1799){std::cout << 2 << "\n";}
    else{std::cout << 1 << "\n";}
    return 0;
}

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

vector<int> par[100010];
vector<int> ch[100010];
int depth[100010];
int n, m;

int dfs(int v){
    if (par[v].size() == 0) {
        depth[v] = 0;
        return 0;
    }
    if (depth[v]) return depth[v];
    for (int p : par[v]) {
        depth[v] = max(dfs(p)+1, depth[v]);
    }
    return depth[v];
}

int main(void){
    cin >> n >> m;
    rep(i,n-1+m){
        int a,b;
        cin >> a >> b;
        a--,b--;
        ch[a].push_back(b);
        par[b].push_back(a);
    }
    rep(i,n) dfs(i);
    rep(i,n){
        int true_par = -1;
        int max_depth = 0; 
        for(int p : par[i]){
            if (max_depth <= depth[p]) {
                max_depth =  depth[p];
                true_par = p;
            }
        }
        cout << true_par+1 << endl;
    }

    return 0;
}


Measured memory_bytes: 14080
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll              long long
#define pb              push_back
#define ppb             pop_back
#define endl            '\n'
#define mii             map<ll,ll>
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define vs              vector<string>
#define all(a)          (a).begin(),(a).end()
#define F               first
#define S               second
#define sz(x)           (ll)x.size()
#define hell            1000000007
#define inf             (ll)1e18 + 5
#define PI              (double)3.14159265358979323844
#define DECIMAL(n)      cout << fixed << setprecision(n);
#define rep(i,a,b)      for (ll i=a;i<b;i++)
#define repr(i,a,b)     for (ll i=a-1;i>=b;i--)
#define bitcount(a)     (ll)__builtin_popcount(a)
#define lbnd            lower_bound
#define ubnd            upper_bound
#define mp              make_pair
#define ios             ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ordered_set     tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define trace(...)      __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

using namespace std;
using namespace __gnu_pbds;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//primes for hashing 937,991,1013,1409,1741

void solve() {
    ll n;
    cin>>n;
    ll arr[n];
    rep(i,0,n){
    	cin>>arr[i];
    }
    ll temp1[n],temp2[n];
    rep(i,0,n){
    	temp1[i]=arr[i]+i+1;
    	temp2[i]=i+1-arr[i];
    }
    mii m;
    rep(i,0,n){
    	m[temp2[i]]++;
    }
    ll ans=0;
    rep(i,0,n){
    	ans+=m[temp1[i]];
    }
    cout<<ans<<endl;
    // rep(i,0,n){
    // 	cout<<temp1[i]<<" ";
    // }
    // cout<<endl;
    // rep(i,0,n){
    // 	cout<<temp2[i]<<" ";
    // }
    // cout<<endl;
}

signed main() {
    ios
    ll test=1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

Measured memory_bytes: 31020
n, m= list(map(int,input().split()))
arr = []
for i in range(n):
    arr.append(list(input()))
dp = []
dp.append([0]*(m+1))
for i in range(n):
    dp.append([0]+[1]*(m))
dp[1][1] = 1
for i in range(n):
    for g in range(m):
        dp[1][1] = 1
        if arr[i][g] != "#":
            dp[i+1][g+1] = (dp[i][g+1]+dp[i+1][g])%1000000007
        else:
            dp[i+1][g+1] = 0
print(dp[n][m])

Measured memory_bytes: 115012
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

int main() {
	int n, ans = 0;
	bool flag = true;
	cin >> n;
	vi v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	while (flag) {
		for (int i = 0; i < n;i++) {
			if (v[i] % 2 == 0) {
				v[i] /= 2;
			}else {
				flag = false;
				break;
			}
		}
		ans++;
	}
	cout << ans-1 << endl;
}


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

using namespace std;

#define int long long
#define forr(i,n) for(int i = 0;i < (int)n; i++)
#define forn(i,n) for(int i = (int)(n-1); ~i ;i--)
#define deb(x) cout<<#x<<" " <<x<<"\n";
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define mpa make_pair
#define endl "\n"
#define ar array



void solve(){
	int a, b;
	cin >> a >> b;
	if(a >=1 && a<=9 && b>=1 && b<=9){
		cout << a*b << "\n";
	}else{
		cout << -1 << "\n";
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();		
	}
	return 0;
}


Measured memory_bytes: 3644
n, k = map(int, input().split())
mod = 10**9+7

ans = 0

s = n*(n+1)//2

for i in range(k, n+2):
    min_ = (i-1)*i//2
    max_ = s - (n-i)*(n-i+1)//2
    ans += (max_ - min_ +1)%mod

print(ans%mod)


Measured memory_bytes: 63532
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
arrA = list(map(int,input().split()))

arrA.sort()
A = arrA[N:]
# print(A)
ans = sum(A[::2])

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N; cin >> N;
	vector<int>a(N); rep(i, 0, N) { cin >> a[i]; }

	using B = bitset<8>;

	int x = 0;
	for (auto hoge : a) {
		x ^= hoge;
	}

	rep(i, 0, N) {
		a[i] &= ~x;
	}
	int ans = 0;
	int rank = 0;
	rrep(i, 0, 60) {
		int pivot = -1;
		rep(k, rank, N) {
			if ((a[k] >> i) & 1)pivot = k;
		}
		if (pivot == -1)continue;
		swap(a[rank], a[pivot]);
		rep(k, 0, N) {
			if (k == rank)continue;
			if ((a[k] >> i) & 1) {
				a[k] ^= a[rank];
			}
		}

		rank++;
	}
	int g = 0;
	rep(k, 0, N) {
		g ^= a[k];
	}

	ans = x + g*2;

	cout << ans  << endl;

	return 0;
}


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

int main() {
  int N;
  cin >> N;
  string c;
  int x = 0; 
  
  for(int i = 0; i < N; i++) {
    cin >> c;
    if(c == "Y") {
      x = 1;
    }
  } 
  
  if(x == 0) {
    cout << "Three" << endl;
  }
  else if(x == 1) {
    cout << "Four" << endl;
  }
}


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

vector<pair<ll, ll> > v;
bitset<55> vis; 
int n;

int check(ll p, ll q) {
	vis.reset();
	vis[0] = 1;
	int from = 0, seg = 1;
	//cout << p << ", " << q <<  endl;
	while(vis.count() < n) {
		bool found = 0;
		//cout << "from " << from << endl;
		for(int i = from+1; i < n; ++i) {
			if(not vis[i] and v[from].first+p == v[i].first and v[from].second+q == v[i].second) {
				from = i, vis[i] = 1, found = 1;
				break;
			}
		}

		if(not found) {
			for(int i = 0; i < n; ++i)
				if(not vis[i]) {
					from = i, vis[i] = 1;
					break;
				}
			//cout << "NOTFOUND " << from << endl;
			++seg;
		}
	}
	//cout << "SEG " << seg << endl;
	return seg;
}

int main() {
	cin >> n;
	ll x, y;
	for(int i = 0; i < n; ++i) {
		cin >> x >> y;
		v.push_back({x, y});
	}

	sort(v.begin(), v.end());
	int ans = max(n-1, 1);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j) {
			if(i == j) continue;
			ll p = v[j].first - v[i].first;
			ll q = v[j].second - v[i].second;

			ans = min(ans, check(p, q));		
		}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m,ans=0;cin>>n>>m;
  lvector A(m,0);rep(i,m) cin>>A[i];
  ll s=accumulate(ALL(A),0);
  print(max(-1ll,n-s));
  return 0;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
#define ll long long
#define uint unsigned long long
#define ls x << 1
#define rs x << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
ll dfs(ll a,ll b)
{
	if(a > b) swap(a, b);
	if(b % a == 0) return (a * ((b / a) * 2 - 1));
	ll res = dfs(a, b % a) + (a + a) * (b / a);
	return res;
}

ll n,x;
int main(void)
{
	scanf("%lld%lld", &n, &x);
	if(n == x * 2) printf("%lld\n", x * 3);
	else
	{
		ll ans = 0;
		if(x * 2 < n)
		{
			ans = x + (n - x) + x + x;
			ans += dfs(x, n - 2 * x);
		}
		else
		{
			ans = x + n - x;
			ans += dfs(x, n - x);
		}
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int i;
  long sum=0;
  long n,m;
  cin>>n>>m;
  long a[m];
  for(i=0;i<m;i++){
  cin>>a[i];
  sum+=a[i];
  }
  if(sum<=n) cout<<n-sum;
  else cout<<-1;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << "\n"
#define COUTF(x) cout << setprecision(15) << (x) << "\n"
#define ENDL cout << "\n"
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll) x.size()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define ANS cout << ans << "\n"
#define RETURN(x)    \
  cout << x << "\n"; \
  return 0
clock_t CLOCK;
#define START_TIMER CLOCK = clock()
#define SHOW_TIMER cerr << "time: " << (ld)(clock() - CLOCK) / 1000000 << "\n"
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define LINE cerr << "[debug] line: " << __LINE__ << "\n";
#define debug(x) cerr << "[debug] " << #x << ": " << x << "\n";
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << "\n";
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using mll = map<ll, ll>;
using qll = queue<ll>;
using P = pair<ll, ll>;

constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

signed main() {
  init();
  ll N, L;
  cin >> N >> L;
  vector<string> S(N);
  rep(i, N) cin >> S[i];
  SORT(S);

  rep(i, N) {
    cout << S[i];
  }
  ENDL;
  return 0;
}

Measured memory_bytes: 3684
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
  ll s;
  cin >> s;
  ll x, y;
  ll k = 1e9;
  y = s/k;
  if(s%k) y++;
  x = k*y - s;
  cout << 0 << " " << 0 << " " << k << " " << 1 << " " << x << " " << y;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <climits>
using namespace std;
const int N = 2e5+507;
int k,n,i,a[N],minn=INT_MAX;
int main()
{
    cin>>k>>n;
    for (i=1;i<=n;++i)
         cin>>a[i];
    for (i=1;i<=n;++i)
    {
        if (i==1)
            minn=min(minn,min(a[n]-a[1],a[n]-a[2]+a[1]+k-a[n]));
        else minn=min(minn,(a[n]-a[i]+a[i-1]+a[1]+k-a[n],a[i]+a[n]-a[i+1]+k-a[n]));
    }
    cout<<minn;
}



Measured memory_bytes: 1024
#084_D
from bisect import bisect_left, bisect_right
prime = []
like_2017 = []

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
            if (i+1)//2 in prime:
                like_2017.append(i)
                
sieve(100000)
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect_right(like_2017, r)-bisect_left(like_2017, l))

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

int main(void){
    // Here your code !

    string str;
    cin >> str;

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

    char last = str[0];
    for (int i = 1; i < str.length(); i++) {
        if (last == str[i]) {cout << "no" << endl; return 0;}
        last = str[i];
    }

    cout << "yes" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;
//



     signed main(){
  int d;
  clock_t st=clock();
  cin>>d;
    clock_t ed=clock();

  int c[26];
  for(int i=0;i<26;i++)cin>>c[i];
  int t[d],s[d][26],x[26]={};
    vector<int>v[26];
    for(int i=0;i<26;i++)v[i].push_back(-1);

  for(int i=0;i<d;i++)for(int j=0;j<26;j++)cin>>s[i][j];
   // cerr<<'i';
  for(int i=0;i<d;i++){
      for(int j=0;j<26;j++)x[j]+=c[j];
      int k=0;
      for(int j=1;j<26;j++)if(x[k]+s[i][k]<x[j]+s[i][j])k=j;
      t[i]=k;
      x[k]=0;
      v[k].push_back(i);
  }
  for(int i=0;i<26;i++)v[i].push_back(d);
//for(int i=0;i<d;i++)cout<<t[i]+1<<endl;
  // cerr<<double(clock()-st)/CLOCKS_PER_SEC<<endl;
while(double(clock()-st)/CLOCKS_PER_SEC<1.90){
    int p=rand()%d;
    auto q=find(v[t[p]].begin(),v[t[p]].end(),p);
    q++;
   int m=(p+(*q))/2;
  // int m=p+rand()%((*q)-p);
//cerr<<m<<' '<<p<<endl;
   if(m==p)continue;
   auto r1=find(v[t[m]].begin(),v[t[m]].end(),m);
   auto r0=r1-1,r2=r1+1;
   if((m-p)*((*q)-m)*c[t[p]]+s[m][t[p]]>(m-(*r0))*((*r2)-m)*c[t[m]]+s[m][t[m]]){
 
    v[t[p]].insert(q,m);
    v[t[m]].erase(r1);
    t[m]=t[p];
   }




}
     for(int i=0;i<d;i++)cout<<t[i]+1<<endl;


     }


 


 






    





      

        


Measured memory_bytes: 3756
# import sys
# input = sys.stdin.readline

H, W = map(int, input().split())
q = []
a = [None] * H
for y in range(H):
    l = list(input())
    a[y] = l
    for x in range(W):
        if l[x] == '#':
            q.append((y,x))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1][qq[1]] == '.':
                a[qq[0] - 1][qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (H-1):
            if a[qq[0]+1][qq[1]] == '.':
                a[qq[0] + 1][qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0]][qq[1]-1] == '.':
                a[qq[0]][qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (W-1):
            if a[qq[0]][qq[1]+1] == '.':
                a[qq[0]][ qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)


Measured memory_bytes: 130688
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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++)
int main() {
  ll N;
  string S;
  cin >> N >> S;
  int co = 0;
  if(N % 2 == 0) {
    rep(i, N/2) {
      if(S.at(i) == S.at(i + N/2)) {
        co++;
      }
    }
    if(co == N / 2) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
  else {
    cout << "No" << endl;
  }
}

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

typedef long long ll;

int N;
vector<ll> A;

vector<vector<ll> > cc;
ll dp(int idx, int r) {
    if(idx == N) return 0;
    ll &ret = cc[idx][r];
    if(ret != -1) return ret;

    if(A[idx]) ret = max(ret, (ll)r + (A[idx] - r) / 2 + dp(idx + 1, (A[idx] - r) % 2));
    ret = max(ret, A[idx] / 2 + dp(idx + 1, A[idx] % 2));

    return ret;
}

int main() {
    scanf("%d", &N);
    A.resize(N);
    for(int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }

    cc = vector<vector<ll> >(N, vector<ll>(2, -1));
    printf("%lld", dp(0, 0));
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sim template < class c
#define ris return *this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", ", d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; it++)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int N = 3010;
double p[N];
int n;
vector<vector<double>> dp(N, vector<double> (N, -1));

double solve(int c, int h) {
	if (c == n) {
		if (h >= (n + 1) / 2) {
			return 1;
		}
		return 0;
	}
	if (dp[c][h] != -1) {
		return dp[c][h];
	}
	return dp[c][h] = p[c] * solve(c + 1, h + 1) + (1.0 - p[c]) * solve(c + 1, h);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	double ans = solve(0, 0);
	cout << fixed << setprecision(12) << ans;
	
	return 0;
}


Measured memory_bytes: 71552
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
	//"strconv"
)

var stdin = bufio.NewScanner(os.Stdin)

func sI() string {
	stdin.Scan()
	return stdin.Text()
}

func main() {
    sI()
	s := strings.Split(sI(), " ")[0]
    fmt.Println(strings.Count(s, "ABC"))
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define forn(b) for(int i = 0; i < b; i++)
#define rforn(b) for(int i = b - 1 ;b >= 0; i--)
#define It(m) for(auto it = m.begin(); it != m.end(); it++)
#define N 500500
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
const ll mod = (ll)1e9 + 7;
    
int main(){
    speed;
    int n; cin >> n;
    string s; cin >> s;
    if(n > s.size()) {
        n = s.size();
    }   
    for(int i = 0; i < n; i++) {
        cout << s[i];
    }
    if(n < s.size()) {
        cout << "...";
    }
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
using namespace std;
class UFtree{
  int N;
  int *parent;
  int *depth;
  public:
    UFtree(int x);
    void root(int x,int a[2]);
    int unite(int x,int y,int d);
};

UFtree::UFtree(int x)
{
 N=x;
 parent = new int[N];
 depth = new int[N];
 int i;
 for(i=0;i<=N;i++){
   parent[i]=-1;
   depth[i]=0;
 }
}

void UFtree::root(int x,int a[2]){
  if(parent[x-1]==-1){
    a[0]=x;
    a[1]=0;
  }else{
   int b[2];
   root(parent[x-1],b);
   parent[x-1]=b[0];
   depth[x-1]+=b[1];
   a[1]=depth[x-1];
   a[0]=b[0];
  }
}

int UFtree::unite(int x,int y,int d){
  int a[2],b[2];
  root(x,a);
  root(y,b);
  if (a[0]!=b[0]){
   parent[a[0]-1]=b[0]; 
   depth[a[0]-1]=b[1]-a[1]+d;
  }else{
    if (a[1]-b[1]!=d){
      return 0;
    }
  }
  return 1;
}

int main(){
  int N,M;
  cin >> N >> M;
  UFtree tr(N);
  int i;
  int L,R,D;
  	for(i=0;i<M;i++){
      cin >> L >> R >> D;
      if(tr.unite(L,R,D)==0){
        cout<<"No";
        return 0;
      }  
    }
  cout << "Yes";
  return 0;
}



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

int main() {
    int n;
    cin >> n;
    ll sum = 0;
    for (int i =1;i <= n;i++) {
        if (i%3!=0&&i%5!=0) {
            sum +=i;
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>
int main(void){
    int n,p,ans=0,max=0;
    scanf("%d",&n);
    for (int i=0; i<n; i++){
        scanf("%d",&p);
        ans+=p;
        max=max>p?max:p;
    }
    ans=ans-max/2;
    printf("%d\n",ans);
	return 0 ;
}

Measured memory_bytes: 128