akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
#define fprint(NUM,X) cout << fixed << setprecision(NUM) << (X) << endl
#define fprints(NUM,X,Y) cout << fixed << setprecision(NUM) << (X) << " " << (Y) << endl
static const int INF = 1e+9+7;
ll n,m,l;
string s,t;
int d[200010],dp[1010][1010];
double w[1000],v[1000];
double box[200010];
#define MAX 100000
#define INFTY (1 << 30)

class Edge{
public:
  int t,w;
  Edge(){}
  Edge(int t,int w): t(t),w(w){}
};

vector<Edge> G[MAX];

bool vis[MAX];
int cnt;

void dfs(int s){
  for(int i = 0;i < n;i++)d[i] = INFTY;
  queue<int> que;
  que.push(s);
  d[s] = 0;
  int u;
  while(!que.empty()){
    u = que.front();que.pop();
    for(int i = 0;i < G[u].size();i++){
      Edge e = G[u][i];
      if(d[e.t] == INFTY){
        d[e.t] = d[u] + e.w;
        que.push(e.t);
      }
    }
  }
}

void solve(){
  dfs(0);
  int maxv = 0;
  int tgt = 0;
  for(int i = 0;i < n;i++){
    if(d[i] == INFTY)continue;
    if(maxv < d[i]){
      maxv = d[i];
      tgt = i;
    }
  }

  dfs(tgt);
  maxv = 0;
  for(int i = 0;i < n;i++){
    if(d[i] == INFTY)continue;
    maxv = max(maxv,d[i]);
  }
  cout << maxv << endl;
}

int main(){
  int s,t,w;
  cin >> n;
  for(int i = 0;i < n-1;i++){
    cin >> s >> t >> w;
    G[s].push_back(Edge(t,w));
    G[t].push_back(Edge(s,w));
  }
  solve();
  return 0;
}


Measured memory_bytes: 10004
K = int(input())
count = 1
rem = 7 % K

if K % 2 == 0:
    print(-1)
elif rem % K == 0:
    print(1)
else:
    while (rem % K) != 0 and count <= K:
        count += 1
        rem += 7 * pow(10, count-1, mod=K) % K
    if count <= K:
        print(count)
    else:
        print(-1)


Measured memory_bytes: 9176
n,k = map(int,input().split())
sushi = [[int(i) for i in input().split()] for _ in range(n)]
sushi.sort(key=lambda x: x[1],reverse=True)
eaten = [False]*n
d1 = [0]
d2 = [0]
for i in range(n):
    t,d = sushi[i]
    t -= 1
    if eaten[t]: d1.append(d1[-1]+d)
    else:
        eaten[t] = True
        d2.append(d2[-1]+d)
# print(d1)
# print(d2)
ans = 0
for i in range(1,k+1):
    if k-i >= len(d1): continue
    if i >= len(d2): continue
    ans = max(ans, d1[k-i] + d2[i] + i*i)
print(ans)

Measured memory_bytes: 32348
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

fn main(){

    input!{
        n: usize,
    }

    let mut flag: bool = false;
    for i in 1..10{
        if n % i == 0 && n / i < 10{
            flag = true;
            break;
        } 
    }

    if flag==true {
        println!("Yes");
    } else {
        println!("No");
    }

}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define lli long long int
#define llu unsigned long long int
#define fr(va, beg, end) for (lli va = beg; va < end; va++)
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (lli)(x.size())
const lli MOD = 1e9 + 7;
// cout << fixed << setprecision(0) << pi <<endl;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// for multiset
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

void solve() {
    lli n, a, k;
    cin >> n >> k;
    lli val = n / k;
    n -= val * k;
    lli ans = min(n, abs(n - k));
    cout << ans << endl;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // lli t; cin >> t; while(t--)
    solve();
    rt;
}

Measured memory_bytes: 256
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    return n,a

# 拡張ユークリッドアルゴリズム
# (d, x, y): d=ax+by を満たすd, x, yを求める
# aとbが互いに素な整数であればgcd(a,b)=d=1, ax=1 (mod b)
# xは法bの元でaの乗法逆元a^-1になる
def exEuclid(a, b):
    if (b==0):
        return (a, 1, 0)
    else:
        (dd, xx, yy) = exEuclid(b, a % b)
        return (dd, yy, xx - (a//b)*yy)

def main(n,a):
    MOD=10**9+7
    sum1=0
    sum2=0
    for i in range(n):
        sum1=(sum1+a[i])%MOD
        sum2=(sum2+(a[i]*a[i]))%MOD

    aa=(sum1*sum1-sum2+MOD)%MOD

    d,x,y=exEuclid(2,MOD)
    if x<0:
        x+=MOD
    #print(x)

    return (aa*x)%MOD

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)


Measured memory_bytes: 32160
s = input()
a = []
for i in range(len(s)+1):a.append(0)
for i in range(len(s)):
  if(s[i]=='<'):a[i+1]=a[i]+1
for i in range(len(s)-1,-1,-1):
  if(s[i]=='>'):a[i]=max(a[i],a[i+1]+1)
    
print(sum(a))

Measured memory_bytes: 77260
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

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

int main(){
    int h, w; cin>>h>>w;
    vector<string> c(h);
    for(int i=0; i<h; i++) cin>>c[i];

    vector<int> plus;
    vector<int> minus;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(c[i][j] == 'B'){
                plus.emplace_back(j + i);
                minus.emplace_back(j - i);
            }
        }
    }

    sort(plus.begin(), plus.end());
    sort(minus.begin(), minus.end());

    int ma1 = plus[plus.size() - 1] - plus[0];
    int ma2 = minus[minus.size() - 1] - minus[0];

    cout << max(ma1, ma2) << endl;
}


Measured memory_bytes: 10104
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long LL;
LL i,j,k,n,m;
LL mod=1000000007;
string s;

bool isValid(const int n, const map<int, int>& mp) {
  bool valid =true;
  if (n%2 == 0) {
    if(mp.size() == n/2 ) {
      k=1;
      for (auto const& ele: mp) {
        if (ele.second != 2 || ele.first != k ) valid = false;
        k += 2;
      }
    } else {
      valid = false;
    }
  } else {
    if(mp.size() == n/2 + 1 ) {
      k=0;
      for (auto const& ele: mp) {
      	if (k == 0) {
      		if (ele.second != 1 || ele.first != k ) valid = false;
      	} else {
      		if (ele.second != 2 || ele.first != k ) valid = false;
      	}
        k += 2;
      }
    } else {
      valid = false;
    }
  }
  return valid;
}

int main() {
  cin >> n;
  map<int, int> mp;
  for (i=0;i<n;++i) {
    int t; cin >> t;
    if(mp.find(t) != mp.end()) {
      mp[t] +=1;
    } else {
      mp[t] =1;
    }
  }
  int cnt = 0;
  if (isValid(n,mp)) {
    int tmp =1;
    for (j=1;j<=n/2;++j) {
      tmp = tmp*2%mod;
    }
    cnt = tmp;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3200
// AOJ 2000
#include<iostream>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

const int XMAX = 30, YMAX = 30, MMAX = 40;

bool field[XMAX][YMAX];
char dir[MMAX];
int dist[MMAX];
int N, M;

void init() {
  REP(x, XMAX) REP(y,YMAX) { field[x][y] = false; }
}

bool solve() {
  int items = 0;
  int x = 10, y = 10;
  REP(i, M) {
    REP(d, dist[i]) {
      x += (dir[i] == 'E' ? 1 : dir[i] == 'W' ? -1 : 0);
      y += (dir[i] == 'N' ? 1 : dir[i] == 'S' ? -1 : 0);

      if (field[x][y]) {
        field[x][y] = false;
        items++;
      }
    }
  }
  return items == N;
}

int main() {
  while (cin >> N and N) {
    init();
    REP(i, N) {
      int x, y;
      cin >> x >> y;
      field[x][y] = true;
    }

    cin >> M;
    REP(i, M) {
      cin >> dir[i] >> dist[i];
    }

    cout << (solve() ? "Yes" : "No") << endl;
  }
}

Measured memory_bytes: 1148
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdio.h>
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define test ll t; cin>>t; while(t--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define FOR(p,n) for(ll i=p;i<(ll)n;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b) {a %= mod;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % mod;  a = a * a % mod;  b >>= 1; }  return res%mod; }
ll modmul(ll x, ll y){return (x*y)%mod;}
ll modadd(ll x, ll y){return (x+y)%mod;}
ll modsub(ll x, ll y){return (x-y+mod)%mod;}
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[r],mod-2)))%mod; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
#define max 1000005
bool prime[max];
/*ull sieve()
{
	memset(prime,true,sizeof(prime));
	for(ull p=2;p*p<max;p++)
	{
		if(prime[p]==true){
			for(ull i=2*p;i<max;i+=p)
			{
				prime[i]=false;
			}
		}
	}
	prime[0]=0;
	prime[1]=0;
}*/
using namespace std;
signed main()
{
	fastio;
	int a,b,c;
	cin>>a>>b>>c;
	cout<<c<<" "<<a<<" "<<b;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;
using ll = long long;

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

    if (a == b && b == c) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }


    return 0;
}


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

int main(){
	
	bool flag = true;
	while (flag == true){
		int h, w = 0;
		cin >> h >> w;
		if (h != 0 && w != 0){
			for (int i = 0; i < h; i++){
				for (int j = 0; j < w; j++){
					if ((i+j) % 2 == 0){
						cout << "#";
					}
					else{
						cout << ".";
					}
				}
				cout << endl;
			}
			cout << endl;
		}
		else{
			flag = false;
		}
	}

}

Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef pair<int,int> P;

int main(){
    int N;
    int p[20001],a[20001],b[20001];
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>p[i];
    }
    for(int i=1;i<=N;i++){
        a[i]=i*N;
        b[N-i+1]=i*N;
    }
    for(int i=1;i<=N;i++){
        a[p[i]] -= (N-i);
    }
    for(int i=1;i<=N;i++){
        cout << a[i];
        if(i!=N){
            cout<<' ';
        }
    }
    cout<<endl;
    for(int i=1;i<=N;i++){
        cout << b[i];
        if(i!=N){
            cout<<' ';
        }
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 896
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}

int main(void){
	int a, b, c, x, y;
	scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);
	int ans;
	if(c*2>=a+b){
		ans = x*a + y*b;
	}else{
		if(a>c*2) a=c*2;
		if(b>c*2) b=c*2;
		int z = x>y?y:x;
		ans = (x-z)*a + (y-z)*b + z*c*2;
	}
	printf("%d\n", ans);
}


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

struct StCond                  // 材料質量・限界量
{
  int m_nWaterA;
  int m_nWaterB;
  int m_nSugerC;
  int m_nSugerD;
  double m_nConcE;
  int m_nLimitF;
};

struct StAmt                   // 使用量
{
  StAmt() : m_nAmtA(0), m_nAmtB(0), m_nAmtC(0), m_nAmtD(0) { }

  int m_nAmtA, m_nAmtB, m_nAmtC, m_nAmtD;
};

struct StRslt                  // 出力結果
{
  StRslt() : m_nAllMass(0), m_nSugerMass(0) { }

  int m_nAllMass, m_nSugerMass;
};

void fnInput(StCond& roCond)
{
  cin >> roCond.m_nWaterA >> roCond.m_nWaterB >> roCond.m_nSugerC >> roCond.m_nSugerD;
  cin >> roCond.m_nConcE  >> roCond.m_nLimitF;
}

void fnAmtClear(string sProc, const StCond& cnroCond, StAmt& roAmt)
{ 
  if      (sProc == "A")
    { roAmt.m_nAmtA = 0; roAmt.m_nAmtB = 0; roAmt.m_nAmtC = 0; roAmt.m_nAmtD = 0; }
  else if (sProc == "B")
    { roAmt.m_nAmtB = 0; roAmt.m_nAmtC = 0; roAmt.m_nAmtD = 0; }
  else if (sProc == "C")
    { roAmt.m_nAmtC = 0; roAmt.m_nAmtD = 0; }
  else if (sProc == "D")
    { roAmt.m_nAmtD = 0; }
}

int fnAmtSumup(string sProc, const StCond& cnroCond, const StAmt& cnroAmt)
{ 
  if (sProc == "ALL")
    return  (cnroCond.m_nWaterA * cnroAmt.m_nAmtA + cnroCond.m_nWaterB * cnroAmt.m_nAmtB) * 100
          + (cnroCond.m_nSugerC * cnroAmt.m_nAmtC + cnroCond.m_nSugerD * cnroAmt.m_nAmtD);
  else                       // sProc == "SUG"         
    return  (cnroCond.m_nSugerC * cnroAmt.m_nAmtC + cnroCond.m_nSugerD * cnroAmt.m_nAmtD);
}

double fnConcCalc(const StCond& cnroCond, const StAmt& cnroAmt)
{
  double nLimtConc = cnroCond.m_nConcE / (100.0 + cnroCond.m_nConcE);
  double nNowConc =  (double)fnAmtSumup("SUG", cnroCond, cnroAmt)
                   / (double)fnAmtSumup("ALL", cnroCond, cnroAmt);

  if (nLimtConc < nNowConc)  return 0.0;
  else                       return nNowConc;
}

void fnConcCheck(const StCond& cnroCond, StRslt& roRslt)
{
  StAmt oAmt;
  double nMaxConc = -1.0;

  fnAmtClear("A", cnroCond, oAmt);
  while (true)
  {
    fnAmtClear("B", cnroCond, oAmt);
    if (fnAmtSumup("ALL", cnroCond, oAmt) > cnroCond.m_nLimitF)  break;

    if (!oAmt.m_nAmtA)  oAmt.m_nAmtB = 1;
    while (true)
    {
      fnAmtClear("C", cnroCond, oAmt);
      if (fnAmtSumup("ALL", cnroCond, oAmt) > cnroCond.m_nLimitF)  break;

      while (true)
      {
        fnAmtClear("D", cnroCond, oAmt);
        if (fnAmtSumup("ALL", cnroCond, oAmt) > cnroCond.m_nLimitF)  break;

        while (true)
        {
          if (fnAmtSumup("ALL", cnroCond, oAmt) > cnroCond.m_nLimitF)  break;

          double nNowConc = fnConcCalc(cnroCond, oAmt);
          if (nMaxConc < nNowConc)
          {
            nMaxConc = nNowConc;
            roRslt.m_nAllMass = fnAmtSumup("ALL", cnroCond, oAmt);
            roRslt.m_nSugerMass = fnAmtSumup("SUG", cnroCond, oAmt);
          }
          oAmt.m_nAmtD++;
        }
        oAmt.m_nAmtC++;
      }
      oAmt.m_nAmtB++;
    }
    oAmt.m_nAmtA++;
  }
}

int main()
{
  StCond oCond;
  StRslt oRslt;

  fnInput(oCond);
  fnConcCheck(oCond, oRslt);
  cout << oRslt.m_nAllMass << " " << oRslt.m_nSugerMass << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

struct fraction{
  int p, q;
};

int unit_fraction_partition(struct fraction f1, int a, int n, int multiple, int denominator);
struct fraction difference(struct fraction f1, struct fraction f2);
struct fraction reduction(struct fraction f);
struct fraction times(struct fraction f, int n);
int numerator(struct fraction f);
int gcd(int m, int n);

int main(void){
  struct fraction f;
  int a, n;
  do{
    scanf("%d%d%d%d", &(f.p), &(f.q), &a, &n);
    if(f.p!=0 || f.q!=0 || a!=0 || n!=0)
      printf("%d\n", unit_fraction_partition(f, a, n, 1, 1));
  }while(f.p!=0 || f.q!=0 || a!=0 || n!=0);
  
  return 0;
}

int unit_fraction_partition(struct fraction f1, int a, int n, int multiple, int denominator){
  int total=0;
  struct fraction f2;
  f2.p = 1;
  for(f2.q=denominator; f2.q*multiple<=a && numerator(difference(f1, times(f2, n)))<=0; f2.q++)
    if(numerator(difference(f1, f2)) == 0) total++;
    else if(numerator(difference(f1, f2)) > 0)
      total += unit_fraction_partition(difference(f1, f2), a, n-1, f2.q*multiple, f2.q);
  return total;
}

struct fraction difference(struct fraction f1, struct fraction f2){
  struct fraction f3;
  f3.p = f1.p * f2.q - f2.p * f1.q;
  f3.q = f1.q * f2.q;
  if(f3.p > 0) f3 = reduction(f3);
  return f3;
}
  
struct fraction reduction(struct fraction f){
  int tmp = gcd(f.p, f.q);
  f.p /= tmp;
  f.q /= tmp;
  return f;
}
 
struct fraction times(struct fraction f, int n){
  f.p *= n;
  return reduction(f);
}
   
int numerator(struct fraction f){
  return f.p;
}

int gcd(int m, int n){
  int tmp;
  if(m < n){
    tmp = m;
    m = n;
    n = tmp;
  }
  while(n != 0){
    tmp = n;
    n = m % n;
    m = tmp;
  }
  return m;
}

Measured memory_bytes: 408
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main implements Runnable {
	public static void main(String[] args) throws FileNotFoundException {
		new Main().run2();
	}
 
	long[] f;
	long INF = Integer.MAX_VALUE / 10;
	// f[i][0]={w[i],#黒}∧col[i]=白
	// f[i][1]={#白,w[i]}∧col[i]=黒
 
	void dfs(int cur, int par, ArrayList<Integer>[] g, int[] x) {
		f[cur] = 0;
		long base = 0;
		ArrayList<Long> add = new ArrayList<>();
		for (int dst : g[cur]) {
			if (dst == par) {
				continue;
			}
			dfs(dst, cur, g, x);
			if (Math.max(f[dst], x[dst]) == INF) {
				f[cur] = INF;
				return;
			}
			base += Math.min(x[dst], f[dst]);
			add.add(Math.max(x[dst], f[dst]) - Math.min(x[dst], f[dst]));
		}
		if (base > x[cur]) {
			f[cur] = INF;
			return;
		}
		boolean[] h = new boolean[(int) (x[cur] - base + 1)];
		h[0] = true;
		int sum = 0;
		int max = 0;
		for (long v : add) {
			sum += v;
			for (int i = h.length - 1; i >= 0; --i) {
				if (i + v >= h.length)
					continue;
				h[(int) (i + v)] |= h[i];
			}
		}
		for (int i = 0; i < h.length; ++i) {
			if (h[i])
				max = Math.max(max, i);
		}
		if (base > x[cur]) {
			f[cur] = INF;
			return;
		}
		f[cur] = base + (sum - max);
	}
 
	// f[i][0]={w[i],#黒}∧col[i]=白
	// f[i][1]={#白,w[i]}∧col[i]=黒
 
	String solve(int n, int[] p, int[] x) {
		ArrayList<Integer>[] g = new ArrayList[n];
		for (int i = 0; i < n; ++i)
			g[i] = new ArrayList<>();
		for (int i = 1; i < n; ++i) {
			g[i].add(p[i]);
			g[p[i]].add(i);
		}
		f = new long[n];
		Arrays.fill(f, INF);
		dfs(0, -1, g, x);
		if (f[0] < INF) {
			return "POSSIBLE";
		} else {
			return "IMPOSSIBLE";
		}
	}
 
	public void run() {
		new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
	}
 
	void run2() {
 
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] p = new int[n];
		int[] x = new int[n];
		for (int i = 1; i < n; ++i) {
			p[i] = sc.nextInt();
			--p[i];
		}
		for (int i = 0; i < n; ++i) {
			x[i] = sc.nextInt();
		}
		System.out.println(solve(n, p, x));
	}
}

Measured memory_bytes: 27688
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000001
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 100

ll n,W;//荷物の個数、重さの総和
ll w[ARRAY_MAX],v[ARRAY_MAX];//重さ、価値
ll dp[ARRAY_MAX + 1][ARRAY_MAX*ARRAY_MAX + 1];


//dp[i][j]:= 

void solve(){

    for(ll i = 0; i <= ARRAY_MAX*ARRAY_MAX;i++){
		dp[0][i] = INF;
	}
    dp[0][0] = 0;

    for(ll i = 1;i <= n;i++){
        for(ll j = 0;j <= ARRAY_MAX*ARRAY_MAX;j++){
            if(j < v[i-1]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]] + w[i-1]);
            }
        }
    }
    ll ans = 0;
    for(ll i = 0;i <= ARRAY_MAX*ARRAY_MAX;i++){
        if(dp[n][i]<=W){
            ans = i;
            //cout << ans << endl;
        }
    }
    cout << ans << endl;


}

int main(){    

    cin >> n >> W;
    //cout << n << W;
    for(ll i = 0;i < n;i++){
        cin >> v[i] >> w[i];
    }
    solve();

    return 0;
}


Measured memory_bytes: 11028
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if ((1 <= i && i <= 9) || (100 <= i && i <= 999) || (10000 <= i && i <= 99999)) {
                count++;
            }
        }

        System.out.println(count);
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


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


ll sign[3];
ll x[1002], y[1002], z[1002];
int N, M;

bool visited[1002][1002];
ll memo[1002][1002];

ll dfs(int n, int m) {
	if(n == N || m == M) {
		return 0;
	}
	if (visited[n][m]) return memo[n][m];
	ll ret = 0;
	if(N - n == M - m) {
		for(int i=n;i<N;i++) {
			ret += sign[0] * x[i];
			ret += sign[1] * y[i];
			ret += sign[2] * z[i];
		}
	} else {
		assert(M - m < N - n);
		ret = dfs(n + 1, m + 1);
		ret += sign[0] * x[n];
		ret += sign[1] * y[n];
		ret += sign[2] * z[n];
		ret = max(ret, dfs(n + 1, m));
	}
	visited[n][m] = true;
	memo[n][m] = ret;
	return ret;
}

int main() {
	cin >> N >> M;

	for(int i=0;i<N;i++) {
		cin >> x[i] >> y[i] >> z[i];
	}

	ll ans = 0;
	for(int bit=0;bit<(1<<3);bit++) {
		for(int j=0;j<3;j++) {
			if((bit>>j)&1) {
				sign[j] = 1;
			}else {
				sign[j] = -1;
			}
		}
		memset(visited, 0, sizeof(visited));
		ans = max(ans, dfs(0, 0));
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;


int main(){
    ll N; cin >> N;
    ll Max=0;
    vector<ll> A(N); for(int i = 0; i < N; i++) {cin >> A[i]; Max = max(Max, A[i]);}
    vector<int> Count(N), Ans(N);
    for(int i = 0; i < N; i++) Ans[i]++;
    for(int i = 0; i < N; i++){
        ll x = A[i];
        if(x == 0){
            Ans[x] *= (3-Count[x]);
            Count[x]++;
        }
        else{
            Ans[x] *= (Count[x-1] - Count[x]);
            Count[x]++;
        }
    } 
    ll ans = 1;
    for(int i = 0; i <= Max; i++) { 
        ans *= Ans[i]; ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,W = LI()
    vw = [LI() for _ in range(n)]

    def rk(vw):
        r = collections.defaultdict(int)
        r[0] = 0
        for v,w in vw:
            rl = list(r.items())
            for rw,rv in rl:
                if rw + w > W:
                    continue
                if r[rw+w] < rv + v:
                    r[rw+w] = rv + v

        t = []
        m = -1
        for w,v in sorted(r.items()):
            if m < v:
                m = v
                t.append((w,v))

        return t

    r1 = rk(vw[:n//2])
    r2 = rk(vw[n//2:])

    i2 = len(r2) - 1
    r = 0
    for w,v in r1:
        while w + r2[i2][0] > W:
            i2 -= 1

        vv = v + r2[i2][1]
        if r < vv:
            r = vv

    return r

print(main())






Measured memory_bytes: 273556
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int y = sc.nextInt();
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n - i; j++) {
				int k = n - i - j;
				if (10000 * i + 5000 * j + 1000 * k == y) {
					System.out.println(i + " " + j + " " + k);
					return;
				}
			}
		}
		System.out.println("-1 -1 -1");
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <bitset>
#include <sstream>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <climits>
#include <ctype.h>
using namespace std;

#define PI acos(-1.0)
#define EPS 1e-8
#define MOD 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second

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

template <class L, class R> ostream &operator <<(ostream &os, pair<L, R> P){
    return os << "(" << P.fi << "," << P.se << ")";
}
template <class T> ostream &operator <<(ostream &os, vector<T> V){
    os << "["; for (auto vv: V) os << vv << ","; return os << "]";
}

struct Matrix {
    vvi data;
    int r, c;
    Matrix(int row, int col, bool identity = false) : r(row), c(col) {
        data.assign(row, vector<int>(col, 0));
        if (identity) {
            for (int i = 0; i < r; ++i) {
                data[i][i] = 1;
            }
        }
    }
    Matrix operator * (Matrix& other) {
        int m = r, n = c, p = other.c;
        Matrix res(m, p);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < p; ++j) {
                for (int k = 0; k < n; ++k) {
                    res.data[i][j] += data[i][k] * other.data[k][j];
                }
            }
        }
        return res;
    }
};

// 扩展欧几里得算法 res[1] * a + res[2] * b = res[0] = gcd(a, b)
vector<int> extendGcd(int a, int b) {
    if (b == 0) {
        return {a, 1, 0};
    } else {
        vector<int> tmp = extendGcd(b, a % b);
        return {tmp[0], tmp[2], tmp[1] - (a / b) * tmp[2]};
    }
}

// 矩阵快速幂
Matrix matrix_power(Matrix base, ll exp) {
    int n = base.r;
    Matrix res(n, n, true);
    while (exp) {
        if (exp & 1) {
            res = res * base;
        }
        base = base * base;
        exp >>= 1;
    }
    return res;
}

// 带模快速幂
template <typename T>
T power_mod(T base, int exp, int mod = MOD) {
    T res = 1;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 快速幂
template <typename T>
T power(T base, int exp) {
    T res = 1;
    while (exp) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

// 求逆元
ll inv(ll a) {
    return power_mod(a, MOD - 2);
}

/******************************** template ********************************/
#define N 110
int n;
int a[2][N];
int dp[2][N];

int main() {
    cin >> n;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }

    dp[0][0] = a[0][0];
    for (int i = 1; i < n; ++i) {
        dp[0][i] = dp[0][i - 1] + a[0][i];
    }
    dp[1][0] = dp[0][0] + a[1][0];
    for (int i = 1; i < n; ++i) {
        dp[1][i] = max(dp[1][i - 1], dp[0][i]) + a[1][i];
    }
    cout << dp[1][n - 1];

    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input())
S = list(input())

W = [0] * N
E = [0] * N

W_pre = E_pre = 0
for i in range(N):
    if S[i] == "W":
        W[i] = W_pre + 1
        E[i] = E_pre
    else:
        W[i] = W_pre
        E[i] = E_pre + 1
    W_pre = W[i]
    E_pre = E[i] 

ans = N
for i in range(N):
    if i>0:
        res1 = W[i-1]
    else:
        res1 = 0
    res2 = E[N-1]-E[i]
    #print(i,res1,res2)
    ans = min(ans,res1+res2)

print(ans)


Measured memory_bytes: 25440
import java.util.Scanner;

class Main{
    public static char grade_1(int m,int f){
	if(m==-1 || f==-1) return 'F';
	if(m+f>=80) return 'A';
	else if(m+f>=65) return 'B';
	else if(m+f>=50) return 'C';	
	else if(m+f>=30) return 'D';
	else return 'F';
    }

    public static char grade_2(int r){
	if(r>=50) return 'C';
	else return 'D';
    }
    
    public static void main(String[] args){
	final Scanner sc=new Scanner(System.in);
	while(true){
	    int m = sc.nextInt();
	    int f = sc.nextInt();
	    int r = sc.nextInt();
	    if(m==-1 && f==-1 && r==-1) break;
	    char g=grade_1(m,f);
	    if(g=='D') g=grade_2(r);
	    System.out.println(g);
	}
    }
}

Measured memory_bytes: 17424
#include<iostream>
//#include<algorithm>
using namespace std;
int main()
{
    long long n, a, b, max_l, min_l, res;
    scanf("%lld%lld%lld", &n, &a, &b);
    if(n == 1 && a != b)
        printf("0\n");
    else if(a > b)
        printf("0\n");
    else
    {
        max_l = (n - 1) * b + a;
        min_l = (n - 1) * a + b;
        res = max_l - min_l + 1;
        printf("%lld\n", res);
    }
    return 0;
}


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

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PI;

int main() {
	double r;
	cin >> r;
	double pi = 3.1415926535897932;
	cout << setprecision(6) << fixed << r * r* pi << " " << 2 * r * pi << endl;
	return 0;
}


Measured memory_bytes: 3252
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  int n,a,b,c,d;
  scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
  int i;
  for(i=0;i<=n-1;i++){
    int64 min=a+(int64)c*i-(int64)d*(n-1-i);
    int64 max=a+(int64)d*i-(int64)c*(n-1-i);
    if(b>=min && b<=max){
      printf("YES\n");
      return;
    }
  }
  printf("NO\n");
}

int main(void){
  run();
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll K = 1000000000;

int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    cout << 0 << ' ' << 0 << ' ';
    int x,y;
    x = (N+K)/K;
  	if(N % K == 0) x--;
    y = x*K - N;
    cout << 1 << ' ' << 1000000000 << ' ' << x << ' ' << y << endl;
}

Measured memory_bytes: 256
import sys

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    S = ii(str)
    S = [1 if s == "W" else -1 for s in S]
    pivot = np.argmin(np.cumsum(S))
    E = S[:pivot].count(1)
    W = S[pivot+1:].count(-1)
    return E + W


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 19792
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int l = (int)s.size();
    if(l%2==1){
        cout << "No" << endl;
        return 0;
    }else{
        REP(i,l){
            if(i%2==0){
                if(s[i]!='h'){
                    cout << "No" << endl;
                    return 0;
                }
            }else{
                if(s[i]!='i'){
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<algorithm>

using namespace std;
typedef long long ll;

int N;
map<long long ,int> in;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int c;
		cin >> c;
		in[c]++;
	}

	ll a = 0, b = 0;

	for (auto i = in.begin(); i != in.end(); i++) {
		if (i->second > 1) {
			b = a;
			a = i->first;
			if (i->second > 3)b = a;
		}
	}
	//if (b == 0)b = a;
	cout << a * b << endl;
	return 0;
}

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

using namespace std;

#define REP(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << "\t"; } cout << "\n";

template <typename T>
using V = vector<T>;

typedef long double ld;

int64_t N;

int64_t A[300][300];


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

	cin >> N;

	REP(i, N) {
		REP(j, N) {
			cin >> A[i][j];
		}
	}
	REP(i, N) {
		REP(j, N) {
			REP(k, N) if (A[i][k] + A[k][j] < A[i][j]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}

	int64_t tot = 0;

	REP(i, N) {
		for (int j = i+1; j < N; ++j) {
			bool g = 0;
			REP(k, N) if (k != i && k != j && A[i][k] + A[k][j] == A[i][j]) {
				g = 1;
				break;
			}
			if (!g) {
				tot += A[i][j];
			}
		}
	}

	cout << tot << endl;
	
}


Measured memory_bytes: 1024
import sys
def ds4(here, lb, ub, field, label):
	if not field[here[1]][here[0]][label]:
		field[here[1]][here[0]][label] = True
	
		if lb[0] < here[0]:
			ds4((here[0]-1, here[1]), lb, ub, field, label)

		if lb[1] < here[1]:
			ds4((here[0], here[1]-1), lb, ub, field, label)
			
		if ub[0] > here[0]:
			ds4((here[0]+1, here[1]), lb, ub, field, label)
			
		if ub[1] > here[1]:
			ds4((here[0], here[1]+1), lb, ub, field, label)

sys.setrecursionlimit(10000)	
while 1:
	w,h = map(int,raw_input().split())
	if (w,h) == (0,0):
		break
	W = []
	B = []
	island = [[[False, False] for i in range(w)] for j in range(h)]
	for j in range(h):
		s = raw_input()
		for i in range(w):
			if s[i] == "B":
				island[j][i][0] = True
				B.append((i,j))
			elif s[i] == "W":
				island[j][i][1] = True
				W.append((i,j))
	for wh in W:
		ds4(wh,(0,0),(w-1,h-1),island,0)
	for bl in B:
		ds4(bl,(0,0),(w-1,h-1),island,1)
	wnum = bnum = 0
	for j in range(h):
		for i in range(w):
			if island[j][i][0]^island[j][i][1]:	
				if island[j][i][0] and not island[j][i][1]:
					wnum += 1
				elif island[j][i][1] and not island[j][i][0]:
					bnum += 1
	print bnum, wnum

Measured memory_bytes: 6716
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m;
int a[102][102];
int b[102][102];
int sum;
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[j][i]);
			b[j][i]=a[j][i];
		}
	}
	for(int i=0;i<n;i++){
		int maxsc=0;
		for(int j=0;j<=m;j++){
			int sc=0;
			for(int k=0;k<j;k++){
				sc+=a[k][i];
				a[k+1][i]^=1;
			}
			for(int k=m-1;k>=j;k--){
				sc+=a[k][i];
				a[k-1][i]^=1;
			}
			for(int k=0;k<m;k++)a[k][i]=b[k][i];
			maxsc=max(maxsc,sc);
		}
		sum+=maxsc;
		for(int j=0;j<m;j++){
			a[j][i+1]^=1;
			b[j][i+1]^=1;
		}
	}
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 3256
N, M = map(int, input().split())
k = []
s = []
for i in range(M):
    inp = list(map(int,input().split()))
    k.append(inp[0]) # 0 - M-1
    s.append(inp[1:]) # s[i] index: 0 - k-1

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

bits = [format(i,'b').zfill(N) for i in range(2**N)]

count = 0
for bit in bits:
    d = 1
    for i in range(M):
        sum = 0
        for sl in s[i]:
            sum = sum + int(bit[sl-1])
        if sum % 2 != p[i]:
            d = 0
            break
    count += d

print(count)


Measured memory_bytes: 40560
def binaryUpper(n, a):
    ok = -1
    ng = len(a)
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        # print("n:", n, "idx:", mid, "val:", a[mid], ok, ng, file=sys.stderr)
        if a[mid] <= n:
            ok = mid
        else:
            ng = mid
    return ng


def binaryLower(n, a):
    ok = len(a)
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        # print("n:", n, "idx:", mid, "val:", a[mid], ok, ng, file=sys.stderr)
        if a[mid] >= n:
            ok = mid
        else:
            ng = mid
    return ok


def resolve():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    for _ in range(q):
        k = int(input())
        print(binaryLower(k, a), binaryUpper(k, a))


resolve()



Measured memory_bytes: 16856
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cntA = Counter(A)

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    if cntA[a] == 1:
        ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

print(ans)


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

int main()
{
    long N;
    cin>>N;
    long int k;
    k=(N*100)/108;
    if((k*108/100)==N)
    cout<<k;
    else if((k-1)*108/100==N)
        cout<<k-1;
    else if((k+1)*108/100==N)
        cout<<k+1;
    else
        cout<<":(";
    return 0;
}



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

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

    int n;
    cin>>n;

    int a=1;
    int b=1;

    for(b=1;b<=n;b+=a)
    {
        if(b/a%2==0)
        {
            a*=2;
        }
    }

    b-=a;

    cout<<b<<"\n";

    return 0;
}


Measured memory_bytes: 3616
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 2000
#define MO 1000000007
using namespace std;
int dp[MAXN*2+5][MAXN+5],sum[MAXN*2+5][MAXN+5];
int main()
{
	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);
	int ed=(N+M-1)/(K-1);
	N--;
	dp[0][0]=1;
	for(int j=0;j<=M;j++)
		sum[0][j]=1;
	for(int i=1;i<=ed;i++)
		for(int j=0;j<=M;j++)
		{
			int mx=min(K-1,j);
			if(j-mx-1>=0)
				dp[i][j]=(1LL*sum[i-1][j]-1LL*sum[i-1][j-mx-1])%MO;
			else
				dp[i][j]=sum[i-1][j];
			if(j-1<0)
				sum[i][j]=dp[i][j];
			else
				sum[i][j]=(1LL*sum[i][j-1]+1LL*dp[i][j])%MO;
		}
	int ans=0;
	for(int i=1;i<=ed;i++)
		for(int j=1;j<=M;j++)
		{
			int mx=min(K-1,j);
			int ansn;
			if(j-mx-1>=0)
				ansn=((1LL*sum[i-1][j-1]-1LL*sum[i-1][j-mx-1])%MO+MO)%MO;
			else
				ansn=sum[i-1][j-1];
			if(M%(K-1)==j%(K-1)&&(((K-1)*i-j)%(K-1)+K-1)%(K-1)==N%(K-1)&&(K-1)*i-j<=N)
				ans=(1LL*ans+1LL*ansn)%MO;
		}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 62848
#include<iostream>
#include<string>

int main() {

	int N, L;
	std::string S;
	int flag;

	std::string str[124];

	std::string retstr;

	std::cin >> N;
	std::cin >> L;
	std::cin >> str[0];

	for (int i = 1; i < N; i++) {
		std::cin >> S;
		flag = 0;

		for (int y = 0; y < i; y++) {

			//文字列との比較

			//その文字より小さいならば
			if (S.substr(0, L) < str[y].substr(0, L)) {

				//ずらす
				for (int x = i - 1; x >= y; x--) {
					str[(x + 1)] = str[x];
				}
				//挿入処理
				str[y] = S;
				flag = 1;
				break;
			}

		}


		if (!flag)str[i] = S;

		

	}

	for (int i = 0; i < N; i++) {
		retstr += str[i];
	}
	
	std::cout << retstr;
	
	

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

void bubble(int N,char s[],int a[]){
    int i,j,tmp;
    char x;
    
    for(i=0;i<N-1;i++){
        for(j=0;j<N-i-1;j++){
           if(a[j]>a[j+1]){
               tmp=a[j];
               a[j]=a[j+1];
               a[j+1]=tmp;
               
               x=s[j];
               s[j]=s[j+1];
               s[j+1]=x;
           } 
        }
    }
}

void selection(int N,char s[],int a[]){
    int i,j,min,tmp;
    char x;
    
    for(i=0;i<N-1;i++){
        min=i;
        for(j=i;j<N;j++){
            if(a[j]<a[min]){
                min=j;
            }
        }
        tmp=a[i];
        a[i]=a[min];
        a[min]=tmp;
        
        x=s[i];
        s[i]=s[min];
        s[min]=x;
    }
}

int main(void){
    char s[36],t[36];
    int a[36]={};
    int b[36]={};
    int i,N;
    
    scanf("%d",&N);
    getchar();
    for(i=0;i<N;i++){
        scanf("%c%d",&s[i],&a[i]);
        getchar();
        b[i]=a[i];
    }
    strcpy(t,s);
    
    bubble(N,s,a);
    for(i=0;i<N;i++){
        printf("%c%d",s[i],a[i]);
        if(i!=N-1)printf(" ");
    }
    puts("\nStable");
    
    selection(N,t,b);
    for(i=0;i<N;i++){
        printf("%c%d",t[i],b[i]);
        if(i!=N-1)printf(" ");
    }
    puts("");
    
    if(strcmp(s,t)==0){
        puts("Stable");
    }
    else puts("Not stable");
    
    return 0;
}

Measured memory_bytes: 632
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include <numeric>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;



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


ll m = 1000000007;

ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}
int a[5];
int main() {
	int N;
	cin >> N;
	ll cnt = 0;
	REP(i, N) {
		ll x;
		cin >> x;
		a[x % 4]++;
	}
	if (a[2] == 0) {
		if (a[1]+a[3] <= a[0] + 1) {
			cout << "Yes" << endl;
		}
		else cout << "No" << endl;
	}
	else {
		if (a[1]+a[3] <= a[0])cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}


Measured memory_bytes: 256
n, k = map(int, input().split())
H = [0] + list(map(int, input().split()))

m = n - k
DP = [[float("inf")] * (m + 1) for _ in range(n + 1)]

DP[0][0] = 0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if i < j:
            continue
        DP[i][j] = min(DP[k][j - 1] + max(0, H[i] - H[k]) for k in range(i))

print(min(DP[i][m] for i in range(n + 1)))


Measured memory_bytes: 48348
N = gets.chomp.to_i
a = gets.chomp.split('')
b = gets.chomp.split('')
c = gets.chomp.split('')
ans = 0

for i in 0..(N - 1)
  if a[i] == b[i]
    if b[i] == c[i]
      ans += 0
    else
      ans += 1
    end
  else
    if a[i] == c[i] || b[i] == c[i]
      ans += 1
    else
      ans += 2
    end
  end
end

puts ans

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

int main() {
  int N;
  cin >> N;
  
  vector<int> tako(N);
  for (int i = 0; i < N; i++){
    cin >> tako.at(i);
  }
  
  int ans = 0;
  
  for (int j = 0; j < N-1; j++){
    for (int k = 0; k < N-j-1; k++){
      ans = ans + tako.at(j)*tako.at(j+k+1);
    }
  }
  cout << ans << endl;
}

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

typedef struct Ant{
  int position;
  bool left;
}Ant;

int main(){
  int n,l;
  char c;
  while(cin>>n>>l,n){
    Ant a[n];
    for(int i=0;i<n;i++){
      cin>>c>>a[i].position;
      if(c == 'L')
	a[i].left = true;
      else
	a[i].left = false;
    }
    bool flag=false;
    int ans=0;
    int num;

    while(1){
      if(flag == true)
	break;
      //cout<<"KJLJ"<<endl;
      flag = true;
      ans++;

      //for(int i=0;i<n;i++){
	//cout<<"a["<<i<<"].left" << a[i].left<<endl;
      //}

      for(int i=0;i<n;i++){
	if(a[i].left==false && (a[i].position!=l && a[i].position!=0)){
	  a[i].position++;
	  flag = false;
	  num = i;
	  //cout<<"i "<<i<<" ant pos "<<a[i].position<<" flag "<<a[i].left<<endl;
	}
      }
      
      for(int i=0;i<n;i++){
	if(a[i].left == true && a[i].position != l && a[i].position!=0){
	  a[i].position--;
	  flag = false;
	  num = i;
	  //cout<<"i "<<i<<" ant pos "<<a[i].position<<" flag "<<a[i].left<<endl;
	}
	//for i end
      }
      for(int j=0;j<n && flag == false;j++){
	for(int k=j+1;k<n;k++){
	  if(a[j].position == a[k].position){
	    //cout<<"j "<<j<<" k "<<k<<endl;
	    a[j].left = !a[j].left;
	    a[k].left = !a[k].left;
	  }
	}
      }
      //while(1) end
    }
    cout<<ans-1<<" "<<num+1<<endl;
  }  
  return 0;
}

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

int main(){
    int A, B;
    cin >> A >> B;
    if (A == B){
        cout << A * 2 << endl;
    }else{
        A = max(A, B);
        cout << A * 2 - 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256