akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  
  if(s.at(0) == s.at(1) && s.at(1) == s.at(2)){
    cout << "Yes" << endl;
  }
  else if(s.at(1) == s.at(2) && s.at(2) == s.at(3)){
    cout << "Yes"  << endl;
  }
  else{
    cout << "No" << endl;
  }
  
}

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

int main() {
  string S;
  cin >> S;
  
  string words[4] = {"dream", "dreamer", "erase", "eraser"};
  string temp;
  bool flag = false;
  bool can = true;

  reverse(S.begin(), S.end());
  for(int i = 0; i < 4; i++){
    reverse(words[i].begin(), words[i].end());
  }

  for(int i = 0; i < S.size();){
    flag = false;
    for(int j = 0; j < 4; j++){
      temp = S.substr(i, words[j].size());
      if(words[j] == temp){
        i += words[j].size();
        flag = true;
        break;
      }
    }
    if(!flag){
      can = false;
      break;
    }
  }

  if(can){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

}


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

const int maxn = 1e5+10;
int n;
int a[maxn],b[maxn],c[maxn];

int32_t main()
{
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i]  >> b[i] >> c[i];
    }
    int dp[maxn][3];
    dp[1][0] = a[1];
    dp[1][1] = b[1];
    dp[1][2] = c[1];
    for(int i = 2;i<=n;i++){
        dp[i][0] = max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
        dp[i][1] = max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
        dp[i][2] = max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
    }
    int ans = max(dp[n][0],max(dp[n][1],dp[n][2]));
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define PB push_back
#define f first
#define s second
#define what_is(x) cerr << #x << " is " << x << endl;

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

map<string, int> m;


void print_s(string str)
{
    cout << str << " x ";
    cout << m[str] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        string s;
        cin >> s;
        m[s]++;
    }
    print_s("AC");
    print_s("WA");
    print_s("TLE");
    print_s("RE");
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

 
struct Unionfind{
    vector<int> parents;
    int n;
    Unionfind(int n):n(n),parents(n,-1){ }

    int find(int x){
        if(parents[x] < 0) return x;
        else return parents[x] = find(parents[x]);
    }

    void unite(int x,int y){
        // x parent y child
        x = find(x);
        y = find(y);

        if(x==y) return;
        //if(parents[x] > parents[y]) swap(x,y);
        parents[x] += parents[y];
        parents[y] = x;
    }  

   int size(int x){
       return -parents[find(x)];
   }

   bool same(int x,int y){
       return find(x)==find(y);
   }

   vector<int> members(int x){
       int root = find(x);
       vector<int> member;
       for(int i=0;i<n;i++){
           if(find(i)==root ){
               member.push_back(i);
           }
       }
      return member;
  }

  int group_cnt(){
      int c = 0;
      rep(i,n){
          if(parents[i] < 0) ++c;
      }
      return c;
  }
};

int main(){
    int n,k,l;
    scanf("%d%d%d",&n,&k,&l);
    //cin >> n >> k >> l;
    Unionfind uf1(n),uf2(n);
    rep(i,k){
        int p,q;
        scanf("%d%d",&p,&q);
        //cin >> p >> q;
        --p;--q;
        uf1.unite(p,q);
    }
    rep(i,l){
        int p,q;
        scanf("%d%d",&p,&q);
        //cin >> p >> q;
        --p;--q;
        uf2.unite(p,q);
    }
    map<P,int> mp;
    rep(i,n){
        mp[P(uf1.find(i),uf2.find(i))] ++;
    }
    rep(i,n){
        printf("%d ", mp[P(uf1.find(i),uf2.find(i))]);
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 16000
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
vector<int> G[100001];
bool visited[100001];
int ans=0;
//グラフの連結判定
int cnt=0;
void dfs(int now){//訪れたところに印を付けながら進んでいくイメージ
    visited[now] = true;
    for(int i=0;i<G[now].size();i++){
        //iが訪れておらず、nowとiがつながっていれば探索する
        int child = G[now][i];
        if(!visited[child]){
            dfs(child);
        }
    }
    
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> x(m),y(m),z(m);
    rep(i,m){
        cin>>x[i]>>y[i]>>z[i];
        x[i]--,y[i]--;
        //connect[x[i]][y[i]]=
        G[x[i]].push_back(y[i]);
        G[y[i]].push_back(x[i]);
    }
    rep(i,n){
        visited[i]=false;
    }
    rep(i,n){
        if(!visited[i]){
            dfs(i);
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 10112
#include <stdio.h>

int main(void)
{
	int a, b , c, i;
	int counter = 0;

	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);

	for( i = a; i <= b; i++){
		if ( ( c % i) == 0) {
			counter++;
		}
	}
	printf("%d\n", counter);
	return 0;
}


Measured memory_bytes: 2724
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int max_size = 1048576;
int N, M, col[1000009], seg[2097168]; vector<int> g[1000009];
void add(int pos, int x) {
	pos += max_size; seg[pos] += x;
	while (pos > 1) {
		pos >>= 1;
		seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);
	}
}
int max_query(int a, int b, int k = 1, int l = 0, int r = max_size) {
	if (r <= a || b <= l) return 0;
	if (a <= l && r <= b) return seg[k];
	int lc = max_query(a, b, k * 2, l, (l + r) >> 1);
	int rc = max_query(a, b, k * 2 + 1, (l + r) >> 1, r);
	return max(lc, rc);
}
int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> col[i];
		g[--col[i]].push_back(i);
		add(col[i], 1);
	}
	for (int i = 0; i < M; i++) {
		int ret = 0;
		for (int j = -1; j <= 0; j++) {
			vector<int> v;
			for (int k : g[i]) {
				v.push_back((k - j) / 2);
			}
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
			for (int k : v) {
				int l = max(k * 2 + j, 0), r = min(k * 2 + j + 2, N);
				for (int p = l; p < r; p++) add(col[p], -1);
			}
			ret = max(ret, (int)g[i].size() + max_query(0, N));
			for (int k : v) {
				int l = max(k * 2 + j, 0), r = min(k * 2 + j + 2, N);
				for (int p = l; p < r; p++) add(col[p], 1);
			}
		}
		cout << N - ret << '\n';
	}
	return 0;
}

Measured memory_bytes: 69608
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long length = sc.nextInt();
        int n = sc.nextInt();
        char[] arr = sc.next().toCharArray();
        long count = 0;
        for (int i = 1; i < length; i++) {
            if (arr[i - 1] == 'o' && arr[i] == 'o') {
                count++;
            }
        }
        for (int i = 0; i < n; i++) {
            length += count * 3;
            count *= 2;
        }
        System.out.println(length);
    }
}


Measured memory_bytes: 26396
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000
#define long long long // for codeforces

int main(){
  long k,a,b;
  cin>>k>>a>>b;

  if(a >= k){
    cout << 1 << endl;
    return 0;
  }
  if(a <= b){
    cout << -1 << endl;
    return 0;
  }

  long reps = (k-a + (a-b)-1)/(a-b);

  cout << reps*2+1 << endl;

  return 0;
}


Measured memory_bytes: 256
import numpy as np

a1 = list(int(i) for i in input().split())  
x = list(int(i) for i in input().split())  
x = np.sort(x)
n = a1[0]

delta = []
if len(x) <= n:
    print(0)
else:
    for i in range(0,len(x) - 1):
        delta.append(x[i + 1] - x[i])

    if n == 1:
        print(np.sum(delta))
    else:
        delta = np.sort(delta)
        f = delta.size - (n - 2)
        print(np.sum(delta[0:-(n-1):]))

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

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

	int ans;

	if (n % (2 * d + 1) == 0) {
		ans = n / (2 * d + 1);
	}
	else {
		ans = n / (2 * d + 1) + 1;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
a, b, c = list(map(int, input().split()))
k = int(input())
 
ans = False
 
for i in range(k):
    if c <= b:
        c *= 2
    elif b <= a:
        b *= 2
    else:
        ans = True
        break
if c > b and b > a:
    ans = True

if ans:
  	print("Yes")
else:
  	print("No")

Measured memory_bytes: 9188
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  stack<int> S1;
  stack<pair<int,int> > S2;
  char ch;
  int sum=0;
  for(int i=0;cin>>ch;i++){
    if(ch=='\\')S1.push(i);
    else if(ch=='/'&&S1.size()>0){
      int j=S1.top();S1.pop();
      sum+=i-j;
      int a=i-j;
      while(S2.size()>0&&S2.top().first>j){
        a+=S2.top().second;S2.pop();
      }
      S2.push(make_pair(j,a));
    }
  }
  vector<int> ans;
  int t=0;
  while(S2.size()>0){ans.push_back(S2.top().second);S2.pop();}
  reverse(ans.begin(),ans.end());
  cout<<sum<<endl;
  cout<<ans.size();
  for(int i=0;i<ans.size();i++){
    cout<<" ";
    t+=ans[i];
    cout<<ans[i];
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    int a, b;
    cin >> a >> b;
    if ((a+1)/0.08 <= b/0.1 || (b+1)/0.1 <= a/0.08) {
        cout << -1 << endl;
    } else {
        cout << ceil(max(a/0.08, b/0.1)) << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int A,B,C,D;
    int main()
    {
    	
       scanf("%d %d %d %d",&A,&B,&C,&D);
  
cout<<max(0,min(B,D)-max(A,C));
	//cout<<(min(B,D)-max(A,C));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e6 + 10;

int cnk(int n, int k) {
	while (k) {
		int dn = n & 1;
		int dk = k & 1;
		n >>= 1;
		k >>= 1;
		if (!dn && dk) {
			return 0;
		}
	}
	return 1;
}

int n;
int a[N];

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	bool one = false;
	for (int i = 0; i < n; ++i) {
		char c;
		cin >> c;
		a[i] = c - '1';
		one |= a[i] == 1;
	}
	if (!one) {
		for (int i = 0; i < n; ++i) {
			a[i] /= 2;
		}
	}
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int cur = a[i] & 1;
		res ^= cur * cnk(n - 1, i);
	}
	if (!one) {
		res *= 2;
	}
	cout << res << "\n";
	return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n,a,b;
    cin >> n >> a >> b;
    if(a>b){
        cout << 0 << endl;
        return 0;
    }
    if(a==b){
        cout << 1 << endl;
        return 0;
    }
    if(n==1){
        cout << 0 << endl;
        return 0;
    }
    ll ans=1+(n-2)*(b-a);
    cout << ans << endl;
}

Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		sc.close();
		
		int n = S.length();
		int ans = 0;
		int i = n % 2 == 0 ? 2 : 1;
		for(;i < n;i+=2) {
			int len = (n - i) / 2;
			if(S.substring(0, len).equals(S.substring(len, n-i))) {
				ans = n - i;
				break;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 24020
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[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 (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n, k; cin >> n >> k;
	vector<int> a(n); rep(i, n)cin >> a[i];
	sort(all(a));
	if (a[n - 1] < k)cout << "IMPOSSIBLE" << endl;
	else
	{
		int d = a[0];
		rep(i, n)d = gcd(d, a[i]);
		rep(i, n)
		{
			if (a[i] < k)continue;
			else
			{
				if ((k - a[i]) % d == 0)
				{
					cout << "POSSIBLE" << endl;
					return 0;
				}
			}
		}
		cout << "IMPOSSIBLE" << endl;
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

#define M 1000'000'007ll
int n;
vector<ll> v, s;

int main() {
    cin >> n;
    v.resize(n);
    s.resize(n);
    rep(i, n) cin >> v[i];
    s.back() = v.back();
    rrep(i, n - 1) { s[i] = (s[i + 1] + v[i]) % M; }
    ll ans = 0;
    rep(i, n - 1) { ans = (ans + s[i + 1] * v[i]) % M; }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6400
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define E 1e-6
#define INF 0x3f3f3f3f
void open(){freopen("data.txt","r",stdin);}
void out(){freopen("out.txt","w",stdout);}
const int maxn = 101010;
const int MOD = 1e9 + 7;

int main()
{
    int n;
    cin>>n;
    long long ans=0;
    while(n--)
    {
        int left,right;
        cin>>left>>right;
        ans+=right-left+1;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vector<ll> plus, minus;
    ll zeroCnt = 0;
    for(ll i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if(a == 0) {
            zeroCnt++;
        } else if(a < 0) {
            minus.push_back(-a);
        } else {
            plus.push_back(a);
        }
    }
    sort(ALL(plus));
    sort(ALL(minus));

    // x以下の値がk個以上あるかどうか
    auto check = [&](ll x) {
        ll res = 0;
        if(x >= 0) {
            res += (zeroCnt * (zeroCnt - 1) / 2) + zeroCnt * (n - zeroCnt);
            res += (ll)minus.size() * (ll)plus.size();
            for(ll i = 0; i < (ll)minus.size(); i++) {
                ll v = x / minus[i];
                ll id = upper_bound(ALL(minus), v) - minus.begin();
                ll cnt = id - i;
                if(v >= minus[i]) {
                    cnt--;
                }
                res += max(cnt, 0LL);
            }
            for(ll i = 0; i < (ll)plus.size(); i++) {
                ll v = x / plus[i];
                ll id = upper_bound(ALL(plus), v) - plus.begin();
                ll cnt = id - i;
                if(v >= plus[i]) {
                    cnt--;
                }
                res += max(cnt, 0LL);
            }
        } else {
            x *= -1;
            for(ll i = 0; i < (ll)plus.size(); i++) {
                ll v = (x + plus[i] - 1) / plus[i];
                ll cnt = minus.end() - lower_bound(ALL(minus), v);
                res += max(cnt, 0LL);
            }
        }
        return (res >= k);
    };

    ll ng = -LLINF, ok = LLINF;
    while(llabs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S,class T>ostream&operator<<(ostream&os,map<S,T>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>ostream&operator<<(ostream&os,set<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>auto&operator<<(ostream&os,vector<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,c;
    cin>>a>>b>>c;
    set<ll> st;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    Yn(st.size()==2);
    return 0;
}

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

int main(){
    int h ,w;
    cin>>h>>w;
    while(!(h==0 && w==0)){
        for(int i=0; i < h; i++){
            for(int j=0; j<w; j++){
                if(i==0 || i==h-1) {cout<<"#";}
                else{
                    if(j==0 || j==w-1){cout<<"#";}
                    else{cout<<".";}
                }
            }
            cout<<endl;
        }
        cout<<endl;
        cin>>h>>w;
    }
}


Measured memory_bytes: 3088
#%%
kai = [1]
tt = 1
mod = 10**9+7
for i in range(1, 10**5+1):
    tt *= i
    tt %= mod
    kai.append(tt)
#print(kai)


def combination(n, x, kai, mod=10**9+7):
    # nCx, a=n!, b=x!, c=(n-x)!
    # 組み合わせ
    # ex) combination(5, 2) = 10
    tmp = kai[n]
    tmp = (tmp * pow(kai[x], mod-2, mod)) % mod
    tmp = (tmp * pow(kai[n-x], mod-2, mod)) % mod
    return tmp

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

b = combination(n, k, kai)

l = [b] * (n-1)

for i in range(n-1):
    tmp = 0
    x = i+1
    y = (n-1)-i
    if x >= k:
        tmp += combination(x, k, kai)
    if y >= k:
        tmp += combination(y, k, kai)
    l[i] -= tmp

ll = [0] * (n-1)
for i in range(n-1):
    ll[i] = a[i+1] - a[i]
    ll[i] %= mod


ans = 0
for i in range(n-1):
    tmp = l[i] * ll[i]
    tmp %= mod
    ans += tmp
    ans %= mod

if ans < 0:
    ans += mod

print(ans)


Measured memory_bytes: 66764
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

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

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N;
  cin >> N;
  vl X(N);
  REP(i, N) cin >> X[i];
  ll ans = llINF;
  FOR(i, 1, 101) {
    ll score = 0;
    REP(j, N) { score += POW(X[j] - i, 2); }
    ans = min(ans, score);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  ll x , n;
  cin >> x >> n;
  vector<bool>p(101,false);
  for(int i=0; i<n; i++){
    ll a;
    cin >> a;
    p[a]=true;
  }
  
  
  for(int i=0; i<=100; i++){
    
    if(p[x-i]==false){
      cout << x-i << endl;
      return 0;
      
    }
    
    if(p[x+i]==false){
      cout << x+i << endl;
      return 0;
      
      
    }
    
    
    
  }
  
  
  
  
}
  
  
  


Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    public struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        int[] P = Enumerable.Range(0, N).Select(v => NextInt()).ToArray();
        int[] Q = Enumerable.Repeat(-1, N + 1).ToArray();
        for (int i = 0; i < N; i++)
            Q[P[i]] = Q[P[i] - 1] + 1;
        //最長部分連続列の数
        Console.WriteLine(N - Q.Max() - 1);
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 20672
#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    ll n, x;    cin >> n >> x;
    ll *a = new ll[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll *b = new ll[n];
    for (int i = 0; i < n; i++) 
        b[i] = a[i];

    if (b[0] > x)
        b[0] = x;
    
    for (int i = 0; i < n-1; i++) {
        if (b[i] + b[i+1] > x)
            b[i+1] -= min((b[i]+b[i+1])-x, b[i+1]);
        if (b[i] + b[i+1] > x && b[i] > 0) 
            b[i] -= min(b[i]+b[i+1]-x, b[i]);
    }

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

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

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

int dp[20][55][20];

int cnt_sum(int n, int s, int x){
  if(n < 0 || s < 0){
    return 0;
  }
  if(dp[n][s][x] != -1){
    return dp[n][s][x];
  }
  if(n == 0 && s == 0){
    return (1);
  }
  if(x>9){
    return (0);
  }
   
  return dp[n][s][x] = (cnt_sum(n-1, s-x, x+1) + cnt_sum(n, s, x+1));
}
int main(){
  int n, s;
  memset(dp,-1,sizeof(dp));
  while(1){
    scanf("%d %d", &n, &s);
    if(n == 0 && s == 0){
      break;
    }
    if(n >= 11 || s >= 46) printf("0\n");
    else printf("%d\n", cnt_sum(n, s, 0));
  }
  return 0;
}

Measured memory_bytes: 1132
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
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;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - 48;}
char myitoc(int N) {return '0' + N;}

signed main()
{
  int H, W;
  cin >> H >> W;

  int ans = INF;
  for (int i = 1; i < H; i++)
  {
    int S0 = i * W;
    int S1 = (H - i) * (W / 2);
    int S2 = H * W - S0 - S1;
    chmin(ans, max({S0, S1, S2}) - min({S0, S1, S2}));
    int S3 = ((H - i) / 2) * W;
    int S4 = H * W - S0 - S3;
    chmin(ans, max({S0, S3, S4}) - min({S0, S3, S4}));
  }
  swap(H, W);
  for (int i = 1; i < H; i++)
  {
    int S0 = i * W;
    int S1 = (H - i) * (W / 2);
    int S2 = H * W - S0 - S1;
    chmin(ans, max({S0, S1, S2}) - min({S0, S1, S2}));
    int S3 = ((H - i) / 2) * W;
    int S4 = H * W - S0 - S3;
    chmin(ans, max({S0, S3, S4}) - min({S0, S3, S4}));
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  int n,m,l,r,ll,rr,i,res;
  cin >> n >> m;
  ll=1;
  rr=n;
  for(i=0;i<m;i++){
    cin >> l >> r;
    ll=max(ll,l);
    rr=min(rr,r);
  }
  res=max(rr-ll+1,0);
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int inf = 1e9+7;
int main() {
    string s; int q; cin >> s >> q;
    int n = s.length();
    auto dp = vectors(26+1, n, inf);
    repeat_reverse (i,n) {
        setmin(dp[s[i]-'a'][i], i+1);
        repeat (c,26) {
            if (dp[c][i] < n) {
                setmin(dp[c+1][i], dp[c][dp[c][i]]);
            }
        }
        repeat (c,26) {
            if (dp[26][i] < n) {
                setmin(dp[c][i], dp[c][dp[26][i]]);
            }
            if (dp[c][i] < n) {
                setmin(dp[c+1][i], dp[c][dp[c][i]]);
            }
        }
    }
    int log_n = log2(n);
    auto skip = vectors(log_n+1, n, inf);
    skip[0] = dp[26];
    repeat (k,log_n) {
        repeat (i,n) {
            if (skip[k][i] < n) {
                skip[k+1][i] = skip[k][skip[k][i]];
            }
        }
    }
    while (q --) {
        int l, r; cin >> l >> r; -- l;
        int i = l;
        repeat_reverse (k, log_n+1) {
            while (i < n and skip[k][i] <= r) {
                i = skip[k][i];
            }
        }
        cout << (i == r ? "Yes" : "No") << endl;
    }
    return 0;
}


Measured memory_bytes: 94932
#include <bits/stdc++.h>
#define MAXN 105
using namespace std;

int n,m,X,Y,mx=1<<31,mn=~(1<<31);
int x[MAXN],y[MAXN];

inline void read(int &x)
{
	x=0;char ch=getchar();bool f=false;
	while (ch<'0'||ch>'9'){if (ch=='-') f=true;ch=getchar();}
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	if (f) x=-x;return ;
}

int main()
{
	read(n);read(m);read(X);read(Y);
	for (int i=1;i<=n;i++) read(x[i]);
	for (int i=1;i<=m;i++) read(y[i]);
	for (int Z=X+1;Z<=Y;Z++)
	{
		bool f=true;
		for (int i=1;i<=n&&f;i++) if (x[i]>=Z) f=false;
		if (!f) continue;
		for (int i=1;i<=m&&f;i++) if (y[i]<Z) f=false;
		if (f)
		{
			puts("No War");
			return 0;
		}
	}
	puts("War");
	return 0;
}

Measured memory_bytes: 256
S = input()
T = input()

min_m = len(T)
dif = range(len(S)-min_m+1)

for j in dif:
  St = S[j:len(T)+j]
  miss = 0
  for i in range(len(T)):
    if St[i] != T[i]:
      miss += 1
  if miss < min_m:
    min_m = miss

print(min_m)


Measured memory_bytes: 8912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll n,m,ch[12],ans;
bool sw[12];
vector<vector<ll>>s(11);
void cal(){
	bool l=true;
	for(ll i=0;i<m;i++){
		ll sum=0;
		for(ll j=0;j<s[i].size();j++){
			ll now=s[i][j];
			if(sw[now]){
				sum++;
			}
		}
		//cout << sum<<endl;
		if(sum%2!=ch[i]){
			l=false;
			break;
		}
	}
	if(l){
		ans++;
	}
}
void dep(ll now){
	if(now==n){
		cal();
		return;
	}
	sw[now]=false;dep(now+1);
	sw[now]=true;dep(now+1);
}
int main() {
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		ll x;
		cin>>x;
		for(ll j=0;j<x;j++){
			ll a;
			cin>>a;
			a--;
			s[i].push_back(a);
		}
	}
	for(ll i=0;i<m;i++){
		cin>>ch[i];
	}
	//cout << ch[0];
	dep(0);
	cout <<ans;
	// your code goes here
	return 0;
}

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

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

  ll a, b, c;
  map<ll, ll> counts;
  for (ll i = 0; i < n; i++) {
    cin >> a;
    counts[a]++;
  }
  for (ll i = 0; i < m; i++) {
    cin >> b >> c;
    counts[c] += b;
  }

  vector<ll> nums;
  for (auto count : counts) {
    nums.push_back(count.first);
  }
  sort(nums.begin(), nums.end());

  ll cnt = 0;
  ll ans = 0;
  while (cnt < n) {
    ll num = nums.back();
    nums.pop_back();
    ans += num * min(counts[num], n - cnt);
    cnt += min(counts[num], n - cnt);
  }

  cout << ans << endl;
}


Measured memory_bytes: 14964
import java.util.Scanner;

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

        char ch = chList[0];

        if (Character.isLowerCase(ch)){
            System.out.println("a");
        }else{
            System.out.println("A");
        }
    }
}


Measured memory_bytes: 35516
/* B */

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int n;
	cin >> n;
	int result = 0;
	std::vector<int> v(n);
	std::vector<int> c(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	for(int i = 0; i < n; i++){
		cin >> c[i];
	}

	for(int i = 0; i < n; i++){
		int k = v[i]-c[i];
		if(k >= 0){
			result += k;
		}
	}

	cout << result << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#define ll long long
#define ar array
using namespace std;
const int N = 1e5;
int arr[N];
int dp[N];

int main(){
    ios_base::sync_with_stdio(0);
    int n, k;
    cin>>n>>k;;
    for(int i=0; i<n; i++)
        cin>>arr[i];

    dp[0] = 0;
    for(int i=1; i<n; i++){
        int cur = dp[i-1] + abs(arr[i]-arr[i-1]);
        for(int j=1; j<=k; j++){
            if(i>=j)
                cur = min(cur, dp[i-j]+abs(arr[i]-arr[i-j]));
            else
                break;
        }
        dp[i] = cur;
    }
    cout<<dp[n-1]<<endl;

}

Measured memory_bytes: 3940
#include <stdio.h>

int main (){
	int n,i,sw,j;
	int count;
	int jisho[8];
	int p[8];
	int q[8];
	int pc=0;
	int qc=0;
	scanf("%d",&n);
	count = 1;
	for(i=0;i<n;i++){
		jisho[i] = i+1;
	}
	for(i=0;i<n;i++){
		count = 1;
		scanf("%d",&p[i]);
		for(j=n-1-i;j>0;j--){
			count = count*j;
		}
		j=0;sw=0;
		while(sw>=0){
			if(p[i]==jisho[j]){
				pc += count*sw;
				jisho[j]= -1;
				sw = -1;
			} else if(jisho[j]>0){
					sw ++;
			}
			j++;
		}
	}
	for(i=0;i<n;i++){
		jisho[i] = i+1;
	}
	for(i=0;i<n;i++){
		count = 1;
		scanf("%d",&q[i]);
		for(j=n-1-i;j>0;j--){
			count = count*j;
		}
		j=0;sw=0;
		while(sw>=0){
			if(q[i]==jisho[j]){
				qc += count*sw;
				jisho[j]= -1;
				sw = -1;
			} else if(jisho[j]>0){
					sw ++;
			}
			j++;
		}
	}

	if(pc>qc){
		printf("%d\n",pc-qc);
	}else{
		printf("%d\n",qc-pc);
	}


	return 0;
}

Measured memory_bytes: 2144
import heapq

N=int(input())
S=list(map(int,input().split()))
S=[-S[i] for i in range(len(S))]
heapq.heapify(S)
que=[]
next=[]
rest=[]
x=heapq.heappop(S)
heapq.heappush(que,x)
while S:
    while que:
        x=heapq.heappop(que)
        while S:
            y=heapq.heappop(S)
            if y>x:
                heapq.heappush(next,x)
                heapq.heappush(next,y)
                break
            else:
                heapq.heappush(rest,y)
        else:
            print("No")
            exit()
    que=next
    next=[]
    while rest:
        x=heapq.heappop(rest)
        heapq.heappush(S,x)


print("Yes")


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

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
    
   	System.out.println(check(n));
    
    
    
  }
  
  private static String check(int n){
    for(int i = 1; i <= 50000; i++ ){
      int money = i*108/100;
      if(money == n)
        return "" + i;
    }
    return ":(";
  }
}

Measured memory_bytes: 38700
#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 1e5 + 5;

int n, ar[N], ans;

main ()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]);

    for (int i = 1; i < n; i++)
        if (ar[i] == i)
            swap( ar[i], ar[i + 1] ), ans++;

    for (int i = 2; i <= n; i++)
        if (ar[i] == i)
            swap( ar[i], ar[i - 1] ), ans++;

    cout << ans << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include<numeric>
using namespace std;
using P = pair<int, int>;
#define rep(i,n) for(int i=1; i<=(n);i++)
typedef long long ll;

int gcd(int p, int q){
     if(p % q == 0) return q;
     return gcd(q, p % q);
}

int main(){
    int k; cin >> k;
    ll ans=0;
    rep(i,k){
        rep(j,k){
            rep(h,k){
                ans += gcd(i ,gcd(j,h));
            }
        }
    }
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3156
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
p = [-1] + [*map(int, readline().split())]

MOD = 10**9+7
child = [[] for i in range(n+1)]
tot = [None for i in range(n+1)]
one = [None for i in range(n+1)]
dep = [0]*(n+1)
p2 = [1]*(n+1)
for i in range(n):
    p2[i+1] = p2[i]*2%MOD

for v in range(n,-1,-1):
    if dep[v]==0:
        tot[v] = []
        one[v] = []
    else:
        child[v].sort(key=lambda i: dep[i])
        one[v] = one[child[v][-1]]
        tot[v] = tot[child[v][-1]]
        #one_sum = [0]*(dep[v])
        #zero_sum = [0]*(dep[v])
        child[v].pop()
        if child[v]:
            zero = [p2[tot[v][j]]-one[v][j] for j in range(-len(one[child[v][-1]]),0)]
        for c in child[v]:
            for j in range(-len(one[c]),0):
                z = p2[tot[c][j]]-one[c][j]
                one[v][j] = (one[v][j]*z+zero[j]*one[c][j])%MOD
                zero[j] = zero[j]*z%MOD
                tot[v][j] += tot[c][j]

    tot[v].append(1)
    one[v].append(1)

    child[p[v]].append(v)
    dep[p[v]] = max(dep[p[v]],dep[v]+1)        

    #print(v,tot[v],one[v])
        
#print("tot",tot[0])
#print("one",one[0])

ans = 0
for i,j in zip(tot[0],one[0]):
    ans += pow(2,n+1-i,MOD)*j%MOD

print(ans%MOD)
#print(sum(tot[0]))

Measured memory_bytes: 154528
def main():
    ans = 0
    n, k = map(int, input().split())
    s = input()
    arr = []
    if s[0] == '0':
        arr.append(0)
    cnt = 1
    i = 1
    while i != n:
        if s[i] != s[i - 1]:
            arr.append(cnt)
            cnt = 1
        else:
            cnt += 1
        i += 1
    arr.append(cnt)
    if s[-1] == '0':
        arr.append(0)
    ans = 0
    curr = arr[0]
    j = 1
    if len(arr) - 1 <= 2 * k:
        print(n)
        return 0
    for i in range(1, len(arr), 2):
        curr += arr[i] + arr[i + 1]
        if i - j == 2 * k:
            curr -= arr[j] + arr[j - 1]
            j += 2
        ans = max(ans, curr)
    print(ans)
    return 0
main()

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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RFOR(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); --i)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(a) ((int)(a).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define SQ(x) ((x) * (x))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    int n;
    while (cin >> n, n) {
        vb broken(n);
        vi signal(n);
        REP(i, n) {
            string s;
            cin >> s;
            if (s == "x") {
                broken[i] = true;
            } else {
                signal[i] = stoi(s);
            }
        }
        pll range = {10e9, -10e9};
        REP(i, n-1) {
            if (!broken[i] && !broken[i+1]) {
                if (i % 2 == 0) {
                    if (signal[i] >= signal[i+1]) {
                        goto NONE;
                    }
                } else {
                    if (signal[i] <= signal[i+1]) {
                        goto NONE;
                    }
                }
            }
            if (broken[i]) {
                if (broken[i+1]) goto NONE;
                if (i % 2 == 0) {
                    if (range.first >= signal[i+1]) {
                        range.first = signal[i+1]-1;
                    }
                } else {
                    if (range.second <= signal[i+1]) {
                        range.second = signal[i+1]+1;
                    }
                }
            }
            if (broken[i+1]) {
                if (broken[i]) goto NONE;
                if (i % 2 == 0) {
                    if (range.second <= signal[i]) {
                        range.second = signal[i]+1;
                    }
                } else {
                    if (range.first >= signal[i]) {
                        range.first = signal[i]-1;
                    }
                }
            }
        }
        if (range.first == range.second) {
            cout << range.first << endl;
        } else {
            if (range.first > range.second) {
                cout << "ambiguous" << endl;
            } else {
                goto NONE;
            }
        }
        goto END;
NONE:
        cout << "none" << endl;
END: {}
    }
}

Measured memory_bytes: 2984
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
#define for1(i,a,n)  for(int i=0;i<n;i++)
#define rep(i, c) for(int i = 0; i < (int)c; i++)
#define set(x) cout<<fixed<<setprecision(x);
using namespace std;
//**********************************************DO IT NO****************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
int l(int n)
{
    int x=0;
    while(n)
    {
        x++;
        n/=10;
    }
    return x;
}
signed main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    {  
      int n;
      cin>>n;
      int a,b,c,d;
      vector< pair <int,int> > vect(n); 
      vector< pair <int,int> > vect1(n); 
       vector<bool> z(n, false);
      for(int i=0;i<n;i++)
      {
      cin>>a>>b;
      vect[i]={b,a};
      }
      for(int i=0;i<n;i++)
      {
      cin>>c>>d;
      vect1[i]={c,d};
      }
          sort(vect.begin(), vect.end()); 
            sort(vect1.begin(), vect1.end()); 
      int ans=0;
      for(int i=0;i<n;i++)
      {   
          int x1=vect1[i].first,x2=vect1[i].second;
          for(int j=n-1;j>=0;j--)
          {  
              int x3=vect[j].second,x4=vect[j].first;
              if(z[j])
              continue;
              if(x3>=x1)
              continue;
              if(x4<x2)
              {
                  ans++;
                  z[j]=true;
                  break;
              }
          }
      }
      
            
      cout<<ans;
    }
}
// 🍪 🍪 🍪


Measured memory_bytes: 3660