akhauriyash/Code-Regression huggingface dataset:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *H = map(int, read().split())
    
    H.sort(reverse=True)
    print(sum(H[K:]))
    
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 111056
#include <stdio.h>
#include <string.h>
int main(void)
{
  int i,j,k,n,m;
  char t1[201],t2[201];
 
  while(1){
    scanf("%s\n%d", t1, &n);
    if(!strcmp(t1, "-")) break;
    
    for(i=0;i<n;i++){
      scanf("%d", &m);
      for(j=m;t1[j]!='\0';j++)
        t2[j-m] = t1[j];
      for(k=0;k<m;k++)
        t2[j-m+k] = t1[k];
      for(j=0;t1[j]!='\0';j++)
        t1[j] = t2[j];
    }
 
    printf("%s\n", t1);
  }
  return 0;
}


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

int main()
{
	int n;
	cin >> n;
	int dig;
	int sum = 0;

	int num = n;
	while(num){
		dig = num % 10;
		sum = sum+dig;
		num = num / 10;
	}

	if(n%sum == 0){
		cout << "Yes" << endl; 
	}
	else{
		cout << "No" << endl;
	}
}



Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
bool a[100005];
void is_prime() {
	a[1] = true;
	for (int i = 2; i <= sqrt(100000); i++)
		if (!a[i])
			for (int j = i * i; j <= 100005; j += i)
				a[j] = true;
}
int main() {
	int n;
	cin >> n;
	is_prime();
	for (int i = n; i < 100005; i++)
		if (!a[i])
			return cout << i,0;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main() {
	int n,k;
	scanf("%d%d",&n,&k);
	vector<ll>a(n);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	sort(a.begin(),a.end());
	ll ans=1,sign=1;
	int l=0,r=n-1;
	if(k%2){
        ans=a[r--];
        --k;
        if(ans<0) sign=-1;
	}
	while(k){
        ll x=a[l]*a[l+1],y=a[r]*a[r-1];
        if(x*sign>y*sign){
            ans=x%mod*ans%mod;
            l+=2;
        }else{
            ans=y%mod*ans%mod;
            r-=2;
        }
        k-=2;
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}


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

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

const int N = 2e5+10;
ll v[N];
bool vis[N];

int main(){
	ll n, k; cin >> n >> k;
	fr(i,n) scanf("%lld", v+i), v[i]--;
	
	int id = 0;
	vector<int> p;
	
	while(!vis[id]){
		vis[id] = 1;
		p.push_back(id);
		id = v[id];
	}
	
	int inic = id;
	id = 0;
	
	vector<int> ciclo;
	int eh_ciclo = 0;
	for(auto &it : p){
		if(it==inic){
			eh_ciclo = 1;
		}
		if(eh_ciclo) ciclo.push_back(it);
	}
	
	while(k and id!=inic){
		k--;
		id = v[id];
	}
	
	int ans = id;
	
	if(k){
		ans = ciclo[k%sz(ciclo)];
	}
	
	printf("%d\n", ans+1);
}

Measured memory_bytes: 7284
n = int(input())
rmin = int(input())
r=int(input())
dmax = r-rmin
if rmin>r: rmin=r
for _ in range(n-2):
    r = int(input())
    if dmax<r-rmin: dmax=r-rmin
    if rmin>r: rmin=r

print(dmax)


Measured memory_bytes: 5608
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(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 pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vi a(n),b(n);
    rep(i,n) cin >> a[i] >> b[i];
    set<int> s;
    ll ans = 0;
    auto f = [&](set<int> ns) {
        ll ret = 0;
        rep(i,n) {
            bool ok = true;
            rep(j,30) if(a[i]>>j&1 and ns.count(j)) ok = false;
            if(ok) ret += b[i];
        }
        return ret;
    };
    rrep(i,30) {
        if(k>>i&1) {
            auto ns = s;
            ns.insert(i);
            chmax(ans,f(ns));
        } else {
            s.insert(i);
        }
    }
    chmax(ans,f(s));
    cout << ans << endl;
}


Measured memory_bytes: 3956
import java.util.*;

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

		while(sc.hasNext()){
			int n = sc.nextInt();
			for(int k=0;k<n;k++){
				double[] x = new double[4];
				double[] y = new double[4];
				for(int i=0;i<4;i++){
					x[i] = sc.nextDouble();
					y[i] = sc.nextDouble();
				}
				double a=0;
				double b=0;
				
				a = (y[1]-y[0])/(x[1]-x[0]);
				b = (y[3]-y[2])/(x[3]-x[2]);
				
				if(x[0]==x[1] && x[2]==x[3]){
					System.out.println("YES");
				}else if(y[0]==y[1] && y[2]==y[3]){
					System.out.println("YES");
				}else if(a==b){
					System.out.println("YES");
				}else{
					System.out.println("NO");
				}
			}
		}
	}	
}

Measured memory_bytes: 18788
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
typedef long long unsigned int ll;
typedef pair<int, int> P;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<int>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

#define rep(i,n) for(auto i=0; i<(n); i++)
#define isValidPoint(x, y, mx, my) x >= 0 && x  < mx && y >= 0 && y < my

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

const int MOD = 1000000007;

long exp_mod(long long a, long long b, long m) {
	long long res = 1;
	while (b > 0) {
		if (b&1)
			res = (res * a)%m;
		a = (a * a)%m;
		b >>= 1;
	}
	return (long)res;
}

long fact_mod(long n, long m) {
	long long res = 1;
	for (long i=n; i>0; --i)
		res = (res * i)%m;
	return (long)res;
}

long comb_mod(long n, long r) {
	long long res = 1;
	for (long i=0; i<r; ++i)
		res = (res * (n - i) )%MOD;
	return ( res * exp_mod(fact_mod(r, MOD), MOD-2, MOD) ) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

struct Pony
{
    int x,y;

    Pony(int x_, int y_)
    {
        x = x_;
        y = y_;
    }

    bool operator<(const Pony &another) const
    {
        return x < another.x;
    };
};

long modinv(long a, long m) {
    long b = m, u = 1, v = 0;
    while (b) {
        long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


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

  int n;

  cin >> n;

  vector<int> v(n);

  fillInt(v, n);

  sortv(v);

  int l = v[0];
  int u = v[n-1];

  vector<Pony> p;

  for(int i = 1; i < n-1; i++) {
    if (v[i] > 0) {
      p.push_back(Pony(l, v[i]));
      l = l - v[i];
    } else {
      p.push_back(Pony(u, v[i]));
      u = u - v[i];
    }
  }

  p.push_back(Pony(u, l));

  cout << u-l << endl;

  rep(i, p.size()) {
    cout << p[i].x << " " << p[i].y << endl;
  }
}



Measured memory_bytes: 3188
import fractions
a, b, c, d = map(int, input().split())
p = b//c - (a-1)//c 
q = b//d - (a-1)//d 
#a,bの最小公倍数
def lcm(a, b):
  return a * b // fractions.gcd (a, b)
e = lcm(c, d)
r = b//e - (a-1)//e 
f = b - a + 1
p = f - p
q = f - q
r = f - r

print((p+q-r))

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

#define ll long long
#define Y printf("YES\n")
#define N printf("NO\n")
#define pb push_back
#define tp make_tuple
#define srt(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define pr(a) printf("%lld\n",a)
#define r0 return 0
#define pi acos(-1)

using namespace std;

int main(){

     ll n,m,i,j,k,l,r,x,y,z,t;

     cin>>n;

     x=0;

     for(i=1;i<=n;i++){

          x+=n/i;

          if(n%i==0)x--;
     }

     cout<<x<<endl;
}



Measured memory_bytes: 3564
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N, M = map(int, input().split())

    AB = [0] * N
    for i in range(N):
        AB[i] = list(map(int, input().split()))

    AB = sorted(AB)

    have = 0
    price = 0
    for x, y in AB:
        if M - have < y:
            price += x * (M - have)
            break

        else:
            price += x * y
            have += y


    print(price)

main()

Measured memory_bytes: 28972
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

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

	          int N,K;
	          cin >> N >> K;

	          if(N%2==1){
	        	  if((N+1)/2>=K) cout <<"YES" << endl;
	        	  else cout << "NO" << endl;
	          }else{
	        	  if(N/2>=K) cout <<"YES" << endl;
	        	  else cout << "NO" << endl;
	          }

	          return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(pos,mp) for(ll pos=mp.begin();pos!=mp.end();pos -++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

//union find
struct UnionFind {
    vector<ll> parent;
    vector<ll> usize;
 
    UnionFind(int n) : parent(n), usize(n, 1LL){
        rep(i, n)parent[i]=i;
    }
    
    int root(int x){
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }
    
    bool issame(int x, int y){
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
 
        if(x == y)return false;
 
        if(parent[x] > parent[y]) swap(x, y);

        usize[x] += usize[y];
        parent[y] = x;
 
        return true;
    }
    
    int size(int x) {
        return usize[root(x)];
    }
};

int main(){
    ll n, m;
    cin >> n >> m;

    UnionFind uf(n);
    rep(i, m){
        ll x, y, z;
        cin >> x >> y >> z;
        x--, y--;

        if(!uf.issame(x, y))uf.merge(x, y);
    }

    ll ans = 0;
    rep(i, n){
        if(i == uf.root(i))ans++;
    }

    cout << ans << endl;

}

Measured memory_bytes: 4812
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int n;cin>>n;
  vll a(n); rep(i,n) cin >> a[i];
  sort(a.rbegin(), a.rend());
  ll ans = a[0];
  int ptr = 1;
  int cnt = 0;
  rep(i, n-2) {
    ans += a[ptr];
    cnt ^= 1; 
    if (cnt == 0) ptr++;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 4756
#don't use for, while, list
n = int(input())
ans = 0

def ryuka(a,b,count):
    global ans
    c = a + b
    if count == n:
        ans = c
    else:
        count = count + 1
        ryuka(b,c,count)
        
if n == 0 :
    print(2)
elif n == 1:
    print(1)
else:
    ryuka(2,1,2)        
    print(ans)


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

int MAX = 1e9;

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, k, s;
    cin >> n >> k >> s;
    vector<int> ans;

    if (s != MAX) {
        REP(i, k) ans.push_back(s);
        REP(i, n - k) ans.push_back(MAX);
    } else {
        REP(i, k) ans.push_back(MAX);
        REP(i, n - k) ans.push_back(MAX - 1);
    }

    REP(i, n) {
        cout << ans[i];
        if (i != n - 1) cout << ' ';
    }
    cout << '\n';
    return 0;
}

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

using namespace std;

#define INF (1<<29)

int H, W;
char f[200][200];
 
int bfs(queue<int>& px, queue<int>& py, int gx, int gy)
{
    vector<vector<int>> d(H, vector<int>(W, INF));
    auto qx = px, qy = py;
    while (!px.empty()) {
        int x = px.front(), y = py.front();
        px.pop(); py.pop();
        d[y][x] = 0;
    }
    const int dx[] = {-1, +1, +0, +0}, dy[] = {+0, +0, -1, +1};
    while (!qx.empty()) {
        int x = qx.front(), y = qy.front();
        qx.pop(); qy.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (0 <= nx && nx < W && 0 <= ny && ny < H &&
                f[ny][nx]=='.') {                
                if (d[y][x] + 1 < d[ny][nx]) {
                    d[ny][nx] = d[y][x] + 1;
                    qx.push(nx); qy.push(ny);
                }
            }
        }
    }
    return d[gy][gx];
}
 
int main()
{
    int gx, gy;
    cin >> H >> W;
    queue<int> ax, ay, bx, by;
    for (int i = 0; i < H; i++) {
        for (int j = 0 ; j < W; j++) {
            cin >> f[i][j];
            if (f[i][j] == '@') {
                f[i][j] = '.';
                ax.push(j); ay.push(i);
            } else if (f[i][j] == '$') {
                f[i][j] = '.';
                bx.push(j); by.push(i);
            } else if (f[i][j] == '%') {
                f[i][j] = '.';
                gx = j; gy = i;
            }
        }
    }
    cout << (bfs(ax, ay, gx, gy) < bfs(bx, by, gx, gy) ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 3760
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ans = 0
tmp = -1
for a_i in a:
    if a_i == tmp + 1:
        ans = ans + b[a_i-1] +c[tmp-1]
    else:
        ans += b[a_i-1]
    tmp = a_i
print(ans)

Measured memory_bytes: 3064
# frozen_string_literal: true

n = gets.to_i
c, s, f = Array.new(n - 1) { gets.split.map(&:to_i) }.transpose

(n - 1).times do |i|
  t = 0

  i.upto(n - 2) do |j|
    t = s[j] < t ? s[j] + ((t.to_f - s[j]) / f[j]).ceil * f[j] + c[j] : s[j] + c[j]
  end

  puts t.to_i
end

puts 0

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

using namespace std;

int main()
{
    int N;
    string a, Sum;
    cin >> N;

    for (int i = 1; i <= 9; i++)
    {
        a = to_string(i);
        Sum = a + a + a;
        int Sum2 = stoi(Sum);

        if (Sum2 >= N)
        {
            cout << Sum2;
            break;
        }
    }
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut x = read_vec::<usize>();
    x.sort();
    let mut i = 0;
    let mut pairs = HashMap::new();
    let mut paired_idx = HashSet::new();
    while i + 1 < n {
        if x[i] == x[i + 1] {
            *pairs.entry(x[i] % m).or_insert(0) += 1;
            paired_idx.insert(i);
            paired_idx.insert(i + 1);
            i += 2;
            continue;
        }
        i += 1;
    }
    debug!(paired_idx);

    let mut mod_dict = vec![0; m];
    for i in 0..n {
        if paired_idx.contains(&i) {
            continue;
        }
        mod_dict[x[i] % m] += 1;
    }

    let mut ans = paired_idx.len() / 2;
    debug!(ans, mod_dict);
    for i in 0..m {
        if i == m - i || i == 0 {
            ans += mod_dict[i] / 2;
            mod_dict[i] -= (mod_dict[i] / 2) * 2;
            continue;
        }
        let pairable = min(mod_dict[i], mod_dict[m - i]);
        ans += pairable;
        mod_dict[i] -= pairable;
        mod_dict[m - i] -= pairable;
    }
    debug!(ans, mod_dict);

    for &same_key in pairs.keys() {
        if same_key == 0 || same_key == m - same_key {
            continue;
        }
        let pairable = min(pairs[&same_key] * 2, mod_dict[m - (same_key % m)]);
        ans += pairable / 2;
        let paired = 2 * (pairable / 2);
        mod_dict[m - (same_key % m)] -= paired;
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
 
int main () {
  double L, Ldiv, ans;
  cin >> L;
  Ldiv = L / 3;
  ans = Ldiv * Ldiv * Ldiv;
  printf("%lf\n", ans);
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (int i=(int)j;i<=(int)k;++i)
#define Forr(i,j,k) for (int i=(int)j;i>=(int)k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T &a,T b) { return a<b?a=b,1:0; }
template<typename T>bool chkmin(T &a,T b) { return a>b?a=b,1:0; }

const int maxn=1e6+1e2;
const int N=1e6;
const int modd=1e9+7;
int n,Ans;
int	fac[maxn],inv[maxn];

inline void file() {
	freopen("AGC023C.in","r",stdin);
	freopen("AGC023C.out","w",stdout);
}

inline int quick(int a,int b) {
	int s=1;
	while (b) {
		if (b%2==1) s=1ll*s*a%modd;
		a=1ll*a*a%modd; b/=2;
	}
	return s;
}

inline int C(int n,int m) {
	if (n<m) return 0;
	return 1ll*fac[n]*inv[m]%modd*inv[n-m]%modd;
}

inline void init() {
	fac[0]=inv[0]=1;
	For (i,1,N) fac[i]=1ll*fac[i-1]*i%modd;
	inv[N]=quick(fac[N],modd-2);
	Forr (i,N-1,1) inv[i]=1ll*inv[i+1]*(i+1)%modd;
}

inline void solve() {
	scanf("%d",&n);
	for (int i=(n+1)/2,lst=0;i<n;++i) {
		int ans=1ll*C(i-1,n-i-1)*fac[i]%modd*fac[n-i-1]%modd;
		(Ans+=1ll*(ans-lst+modd)*i%modd)%=modd; lst=ans;
	}
	printf("%d\n",(Ans+modd)%modd);
}

int main() {
//	file();
	init();
	solve();
	return 0;
}

Measured memory_bytes: 8064
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& a : A) {
        cin >> a;
    }
    int ans = 0;
    vector<int> colored;
    for (auto& a : A) {
        auto itr = lower_bound(colored.rbegin(), colored.rend(), a);
        if (itr == colored.rbegin()) {
            colored.push_back(a);
            ++ans;
        } else {
            auto prev_itr = itr.base();
            *prev_itr = a;
        }
    }
    cout << ans << endl;
    return 0;
}

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

struct node{
  struct node *R;
  struct node *L;
  struct node *P;
  int key;
};
typedef struct node Node;
Node *NIL;

Node *root;

void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z=(Node *)malloc(sizeof(Node));
  z->key=k;
  z->L=NIL;
  z->R=NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->L;
    }
    else{
      x=x->R;
    }
  }
  z->P=y;

  if(y==NIL){
    root=z;
  }
  else if(z->key < y->key){
      y->L=z;
    }
  else{
      y->R=z;
    }
}

void inorder(Node *u);
void preorder(Node *u);
Node* search(Node *u,int k);

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
      if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node* t = search(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    }
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if ( com[0] == 'p' ){
      inorder(root);

      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}
Node* search(Node *u, int k){
  while((u!=NIL)&&(k!=u->key)){
    if(k<u->key) u=u->L;
    else u=u->R;
  }
  return u;
}
void inorder(Node *u){
  if (u==NIL)return ;
  inorder(u->L);
  printf(" %d",u->key);
  inorder(u->R);
}
void preorder(Node *u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->L);
  preorder(u->R);
}


Measured memory_bytes: 20496
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

//------------------------------------------------------

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

    REP(i, 1, sqrt(n) + 1) {
        if (n % i == 0) {
            st.insert(i - 1);
            st.insert(n / i - 1);
        }
    }
    ll sum = 0;

    for (auto a : st) {
        if (a != 0 && n / a == n % a) sum += a;
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

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

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

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

	int m;
	cin >> m;

	vector<int> b(m);
	for (int i = 0; i < m; i++)
	{
		cin >> b[i];
	}

	println((includes(all(a), all(b)) ? 1 : 0));
}



Measured memory_bytes: 4328
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX(X, Y) (((X) > (Y))? (X) : (Y))
#define MIN(X, Y) (((X) < (Y))? (X) : (Y))
int compare_int(const void *a, const void *b){
  return *(long int*)b - *(long int*)a; // 大きい順
}
int compare_int_small(const void *a, const void *b){
  return *(long int*)a - *(long int*)b; // 小さい順
}
// 公約数
long int gcd(long int a, long int b){
  if(b == 0){
    return a;
  }else{
    return gcd(b, a % b);
  }
}
// 最小公倍数 = a * b / 最大公約数
// 公倍数
long int lcm(long int a, long int b){
  return a * b / gcd(a, b);
}



// min
int main(void){

  long int n;
  long int a[100001];
  long int tmp;

  long int ans = 0;;

  scanf("%ld", &n);
  
  for(long int i = 1; i <= n; i++){
    scanf("%ld", &tmp);
    a[tmp] = i;
  }

  //  qsort(a, n, sizeof(long int), compare_int_small);

  //  fprintf(stderr, "n / 2 = %f\n", 3.0/5.0);
  /*
  for(long int i = 1; i <= n; i++){
    for(long int j = 1; j <= n; j++){
      if(i == a[j]){
	printf("%ld\n", j);
	break;
      }
    }
  }
  */
  for(long int i = 1; i <= n; i++){
    printf("%ld\n", a[i]);
  }


  return 0;
}


Measured memory_bytes: 1536
#pragma region

#include "bits/stdc++.h"
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define _rep3(i, begin, end) for (register int i = (begin), i##_end = (end); i < i##_end; i++)
#define _irep3(i, begin, end) for (register int i = (end)-1, i##_begin = (begin); i >= i##_begin; i--)
#define _rep2(i, n) _rep3(i, 0, n)
#define _irep2(i, n) _irep3(i, 0, n)
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__, _rep3, _rep2, )(__VA_ARGS__)
#define irep(...) _overload3(__VA_ARGS__, _irep3, _irep2, )(__VA_ARGS__)
#define out(x) cout << (x) << '\n';
#define debug(x) cerr << #x << " = " << (x) << " (line: " << __LINE__ << ") " << endl;

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &pair) {
  cin >> pair.first >> pair.second;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[ ";
  rep(i, vec.size()) i == 0 ? os << vec[i] : os << ", " << vec[i];
  os << " ]";
  return os;
}

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

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

void init() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10) << boolalpha;
}

#pragma endregion

#define MOD 1000000007
#define INF 2147483647

int main() {
  init();

  int H, W;
  cin >> H >> W;
  vvi a(H, vi(W));
  rep(i, H) {
    string l;
    cin >> l;
    rep(j, W) {
      a[i][j] = -(l[j] == '#');
    }
  }

  a[H - 1][W - 1] = 1;

  irep(i, H) irep(j, W) {
    if (a[i][j] == -1) continue;
    if (i < H - 1) a[i][j] += max(a[i + 1][j], 0);
    if (j < W - 1) a[i][j] += max(a[i][j + 1], 0);
    a[i][j] %= MOD;
  }

  out(a[0][0]);
}


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

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i = 0; i < N; i++) {
    cin >> p.at(i);
  }
  int max_p;
  for (int i = 0; i < N; i++) {
    max_p = max(max_p, p.at(i));
  }
  int sum;
  for (int i = 0; i < N; i++) {
    sum += p.at(i);
  }
  sum -= max_p / 2;
  cout << sum << endl;
  return 0;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
    }

    int ans = 0;

    //set<ll> se;
    map<ll, int> ma;
    for(int i = 0; i < N; i++){
        ll a = A[i];
        //auto last = se.end();
        //auto it = se.upper_bound(-a);
        auto last = ma.end();
        auto it = ma.upper_bound(-a);
        if(it != last){
            //se.erase(*it);
            ma[it->first]--;
            if(ma[it->first] == 0) ma.erase(it->first);
        }
        else{
            ans++;
        }
        //se.insert(-a);
        ma[-a]++;
    }

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


Measured memory_bytes: 7168
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))

x = 0
y = 0

for i in range(1,a[0]):
    x = x + b[i] - b[0]
    
xx = x
for i in range(1,a[0]-1):
    xx = xx - ((b[i] - b[i - 1]) * (a[0] - i))
    x = x + xx

for i in range(1,a[1]):
    y = y + c[i] - c[0]
    
yy = y
for i in range(1,a[1]-1):
    yy = yy - ((c[i] - c[i - 1]) * (a[1] - i))
    y = y + yy

ans = x * y
ans = ans % (10**9 + 7)

print(ans)

Measured memory_bytes: 18576
#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def f(n):
    if n % 2 == 0:
        return False    
    if n in P and (n+1)//2 in P:
        return True
    return False


P = set(primes(10**5))

Q = int(input())
LR = []
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    LR.append((l,r))

A = []
cur = 0
for i in range(10 ** 5):
    if f(i):
        cur += 1
    A.append(cur)


for l,r in LR:
    print(A[r] - A[l-1])



Measured memory_bytes: 19808
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

const int MAX=510000;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for (int i=2;i<MAX;i++){
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		finv[i]=finv[i - 1]*inv[i]%MOD;
	}
}
long long COM(int n, int k){
	if(n<k) return 0;
	if(n<0||k<0) return 0;
	return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int main(){
	COMinit();
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	ll ans=0;
	for(int i=b;i<w;i++){
		ans+=COM(h-a-1+i,i)*COM(a-1+w-i-1,a-1)%MOD;
		ans%=MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 15588
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

vector<ll> layer(51), p(51);
ll f(ll n, ll x){
  if (n == 0) return 1;
  if (x <= 1) return 0;
  if (x <= layer[n]/2) return f(n-1, x-1);
  if (x == layer[n]/2+1) return p[n-1] + 1;
  if (x < layer[n]) return p[n-1] + 1 + f(n-1, x-layer[n]/2-1);
  return p[n];
}

int main(){
  ll n, x;
  cin >> n >> x;
  layer[0] = 1;
  p[0] = 1;
  rep(i, n){
    layer[i+1] = 2 * layer[i] + 3;
    p[i+1] = 2 * p[i] + 1;
  }
  ll ans = f(n, x);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3452
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,m,l,r,x[nmax],nr,i,m1;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	m1=m;
	while(m--)
	{
		cin>>l>>r;
		x[l]++;
		x[r+1]--;
	}
	for(i=1;i<=n;i++)x[i]+=x[i-1],nr+=(x[i]==m1);
	cout<<nr<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
int main(void){
    int n;
    cin >> n;
    int A[n];
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    
    vector<int> G;
    
    int i=0;
    while(true){
        i++;
        if((pow(3,i)-1)/2<=n){
            G.push_back((pow(3,i)-1)/2);
        }else{
            break;
        }
    }
    cout << G.size() << endl;
    
    int cnt=0;
    for(int j=G.size()-1;j>=0;j--){
        if(j!=0){
            cout << G[j] << " ";
        }else{
            cout << G[j] << endl;
        }
        for(int k=G[j];k<n;k++){
            int v = A[k];
            int l = k - G[j];
            while(l>=0 and A[l] > v){
                A[l+G[j]] = A[l];
                l = l-G[j];
                cnt++;
            }
            A[l+G[j]] = v;
        }
    }
    cout << cnt << endl;
    
    for(int j=0;j<n;j++){
        cout << A[j] << endl;
    }
    
}



Measured memory_bytes: 7180
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define mod 1000000007
#define fi first
#define se second
using namespace std;
int n;
int v[100002];
int frqpar[100002], frqimpar[100002], first, second, first2, second2;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // shuffle(permutation.begin(), permutation.end(), rng);
    cin>>n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        if(i % 2 == 1)
            frqimpar[v[i]] ++;
        else
            frqpar[v[i]]++;
    }
    frqimpar[0] = -1;
    frqpar[0] = -1;
    for(int i = 1; i <= 100000; ++i)
    {
        if(frqimpar[i] > frqimpar[first])
            second = first, first = i;
        else
            if(frqimpar[i] > frqimpar[second])
                second = i;
    }
    for(int i = 1; i <= 100000; ++i)
    {
        if(frqpar[i] > frqpar[first2])
            second2 = first2, first2 = i;
        else
            if(frqpar[i] > frqpar[second2])
                second2 = i;
    }
    int sol = n;
    if(first != first2)
        sol = sol - frqimpar[first] - frqpar[first2];
    else
        sol = sol - max(frqimpar[first] + frqpar[second2], frqimpar[second] + frqpar[first2]);
    cout << sol;
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> adj(100005);
int p[100005];
bool vis[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }

    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();

        for (int v : adj[u]) {
            if (!vis[v]) {
                q.push(v);
                p[v] = u;
                vis[v] = 1;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    for (int i = 2; i <= n; i++) {
        cout << p[i] << '\n';
    }
}


Measured memory_bytes: 10352
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
#pragma warning(disable : 4996)

#define MAX_N 25

struct Node {
	int id;
	int parent;
	int left;
	int right;
	int depth;
	int hight;
	Node() : id(-1), parent(-1), depth(-1), left(-1), right(-1), hight(-1) {}
};

Node nodes[MAX_N];

Node *GetRoot(int n) {
	for (int i = 0; i < n; ++i) {
		if (nodes[i].parent == -1) {
			return &nodes[i];
		}
	}
	return NULL;
}
int CalcDHr(Node *n, int depth) {
	n->depth = depth;
	int md = n->depth;
	if (n->left != -1) {
		Node *l = &nodes[n->left];
		int cd = CalcDHr(l, depth+1);
		if (md < cd) md = cd;
	}
	if (n->right != -1) {
		Node *r = &nodes[n->right];
		int cd = CalcDHr(r, depth+1);
		if (md < cd) md = cd;
	}
	n->hight = md - n->depth;
	return md;
}
void CalcDH(int n) {
	Node *root = GetRoot(n);
	CalcDHr(root, 0);
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int id;
		int left;
		int right;
		scanf("%d %d %d", &id, &left, &right);
		nodes[id].id = id;
		nodes[id].left = left;
		if (left >= 0) {
			nodes[left].parent = id;
		}
		nodes[id].right = right;
		if (right >= 0) {
			nodes[right].parent = id;
		}
	}
	CalcDH(n);
	for (int i = 0; i < n; ++i) {
		Node n = nodes[i];
		int s = -1;
		int dig = 0;
		if (n.parent != -1) {
			Node p = nodes[n.parent];
			if ((p.left != -1) && (p.left != n.id)) s = p.left;
			if ((p.right != -1) && (p.right != n.id)) s = p.right;
		}
		if (n.left != -1) ++dig;
		if (n.right != -1) ++dig;
		const char *type = "internal node";
		if (n.parent == -1) type = "root";
		else if (dig == 0) type = "leaf";
		printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", n.id, n.parent, s, dig, n.depth, n.hight, type);
	}
	return 0;
}


Measured memory_bytes: 2720
#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,a[1000000];
inline int check(int k)
{	for(rint l=n-1,r=n+1;l>=1&&r<n+n;l--,r++)
	{//	debug(l),debug(r);
		if((a[l]>=k&&a[l+1]>=k)||(a[r]>=k&&a[r-1]>=k)) return 1;
		if((a[l]<k&&a[l+1]<k)||(a[r]<k&&a[r-1]<k)) return 0;
	}
	return (a[1]>=k);
}
int main()
{	cin>>n;
	for(rint i=1;i<n+n;i++) scanf("%d",&a[i]);
	int l=1,r=n+n-1,ans=-1;
	while(l<=r)
	{	int mid=(l+r)>>1;// mid=5;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	//	debug(ans);system("pause");
	}
	cout<<ans;
	return 0;
}


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

int main(){
  int n,k,x,ans=0;
  cin>>n>>k;
  for(int i=0;i<n;++i){
    cin>>x;
    ans+=min(x,k-x);
  }
  cout << 2*ans << endl;
  return 0;
}

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

int main(){
    int Rrate,num;
    int Frate;
    cin >> num;
    cin >> Frate;

    if(num>=10){
        Rrate = Frate;
    }
    else{
        Rrate = Frate+100*(10-num);
    }

    cout << Rrate << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args)  {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt(); 
        int []n=new int[N];
        for(int i=0; i<N; i++){
           n[i]=sc.nextInt();
        }
        int max=n[0];
        int min=n[0];
        for(int i=0; i<N; i++){
           if(max<n[i]){
               max=n[i];
           }
           if(min>n[i]){
               min=n[i];
           }
        }
        System.out.println(max-min);
    }    
}


Measured memory_bytes: 21844
n,m = map(int, raw_input().split(" "))
bridges = [[]]
check = [0]
needline = 0
for i in range(n):
    bridges.append([])
for t in range(m):
    x,y = map(int, raw_input().split(" "))
    bridges[x].append(y)
    bridges[y].append(x)
#    brid.append()

#print bridges

def recursivebridge(k,count,goal,checki):
    boo = False
#    print k
    for h in bridges[k]:
        if count >= 2 and h == goal:
            boo = True
        elif h not in checki:
            checky = checki[:]
            checky.append(h)
            boo = boo or recursivebridge(h,count+1,goal,checky)
    return(boo)

for i in range(n+1):
    if i in check:
        continue
    checkcopy = check[:]
    checkcopy.append(i)
    if recursivebridge(i,0,i,checkcopy) is False:
#        print "false"
        needline += 1


if needline > m:
    needline = m
print needline

Measured memory_bytes: 2820
N= int(input())
li=[0]*(N+1)
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            f=x*x + y*y + z*z + x*y + y*z + z*x
            if f<N+1:
                li[f]+=1

for i in range(1,N+1):
    print(li[i])

Measured memory_bytes: 9356
#include<stdio.h>
#include<stdlib.h>

struct node {
	int val;
	struct node* next;
};
struct node* a[100005];
void insert (int u,int v) {
        struct node* q;
        q=(struct node*)malloc(1*sizeof(struct node));
        q->val=v;
        q->next=NULL;
        if(a[u]==NULL)
                a[u]=q;
        else {
                struct node* p;
                p=a[u];
                q->next=p;
                a[u]=q;
        }
}

int max(int a, int b)
{
    if(a<b)
        return b;
    else
        return a;
}

int main()
{
    int m,n,u,v,visited[100005],arr[1000005],count[100005],count2[100005],j,maxi,i,l,r;
    struct node* p;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        visited[i]=0;
        count[i]=0;
        count2[i]=0;
    }
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&u,&v);
        count2[v]++;
        insert(u,v);
    }
    for(i=1;i<=n;i++)
    {
        l=0,r=-1;
        if(count2[i]==0 && visited[i]==0)
        {
            visited[i]=1;
            p=a[i];
            while(p!=NULL)
            {
                count2[p->val]--;
                if(count2[p->val]==0)
                {
                    arr[++r]=p->val;
                }
                count[p->val]=max(count[p->val],count[i]+1);
                p=p->next;
            }
            while(l<=r)
            {
                j=arr[l];
                visited[j]=1;
                p=a[j];
                while(p!=NULL)
                {
                    count2[p->val]--;
                    if(count2[p->val]==0)
                    {  
                        arr[++r]=p->val;
                    }
                    count[p->val]=max(count[p->val],count[j]+1);
                    p=p->next;
                }
                l++;
            }
        }
    }
    maxi=-1;
    for(i=1;i<=n;i++)
    {
        if(count[i]>maxi)
        {
            maxi=count[i];
        }
    }
    printf("%d\n",maxi);
}

Measured memory_bytes: 7128
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<utility>
using namespace std;

// Problem https://atcoder.jp/contests/abc091/tasks/abc091_b
// Reference(mapの利用) https://atcoder.jp/contests/abc091/submissions/2246375

int solver(int blueCardC,vector<string> blueCards,int redCardC,vector<string> redCards){
    int result=0;
    map<string,int> dict;// ここから参考文献を使いながら開始
    dict.clear();
    for(int j=0;j<blueCards.size();j++){
       // cout << blueCards.at(j) << " ";
        dict[blueCards.at(j)]= dict[blueCards.at(j)]+1;
    }
    for(int j=0;j<redCards.size();j++){
         dict[redCards.at(j)] = dict[redCards.at(j)] - 1;
    }
    for(auto jt=dict.begin();jt!=dict.end();++jt){
        // cout << jt->first << "=>" << jt->second << endl;
        // これだとエラー
        // cout << std::get<0>(jt) << "=>" << std::get<1>(jt) << endl;
        if(result < jt->second){
            result = jt->second;
        }
    }   
    return result;
}   
int main(void){
    int N,M;
    int answer = 0;
    cin >> N ;// 青いカード
    vector<string> S(N);
    for(int j=0;j<N;j++){
        string str;
        cin >> str;
        S.at(j) = str;
    }
    cin >> M ;// 赤いカード
    vector<string> T(M);
    for(int j=0;j<M;j++){
        string str;
        cin >> str;
        T.at(j) = str;
    }
    answer = solver(N,S,M,T);
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;

class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();    
        String s = in.next();
        int k = in.nextInt();
        
        char key = s.charAt(k-1);
        for (int i = 0; i < n; ++i){
            char x = s.charAt(i);
            if (x != key)  System.out.print('*');
                else System.out.print(x);
        }
        
    }
}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
#define ll long long
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define ina for(ll i=0;i<n;i++)cin>>a[i];
#define YES printf("YES\n")
#define all(v) v.begin(),v.end()
#define NO printf("NO\n")
#define fastio std::ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;


int main()
{
    fastio;

          ll a,b,c;
          cin>>a>>b>>c;
          cout<<c<<" "<<a<<" "<<b<<endl;


}



Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <functional>
#include <math.h> 
#define enld '\n'
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
// constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------


int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string S;
  cin >> S;
  cout << S[0] + to_string(S.size()-2) + S.back() << "\n";
  return 0;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll A,B,C;
  cin>>A>>B>>C;
  if(A<=C&&C<=B) {
cout<<"Yes"<<endl;
  }
  else {
cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3592