akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ALDS1_2_A
{
    public class Program

    {
        public static void Main(string[] args)
        {
            int n = ReadInt();
            int[] line = ReadIntAr();

            int swapTimes = BubbleSort(line);

            Console.WriteLine(string.Join(" ",line.Select(x => x.ToString()).ToArray()));
            Console.WriteLine(swapTimes);
        }

        //●バブルソート
        public static int BubbleSort(int[] array)
        {

            int swapTimes = 0;
            bool flg = true;
            while (flg)
            {
                flg = false;
                for (int i = array.Count() - 1 ; i > 0 ; i--)
                {
                    if (array[i] < array[i-1])
                    {
                        int tmp = array[i];
                        array[i] = array[i - 1];
                        array[i - 1] = tmp;
                        swapTimes++;
                        flg = true;
                    }
                }
            }
            return swapTimes;
        }

        static string ReadSt() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static long ReadLong() { return long.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static string[] ReadStAr(char sep = ' ') { return Console.ReadLine().Split(sep); }
        static int[] ReadIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
        static long[] ReadLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
        static double[] ReadDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }

    }

}



Measured memory_bytes: 18268
def main():
  n = int(input())
  mod = 10**9+7
  a = []
  for i in range(n):
    a.extend(list(map(int,input().split())))
  dp = [0]*(1<<n)
  dp[0] = 1
  for S in range((1<<n)-1):
    k = bin(S).count("1")*n
    t = dp[S]
    for i in range(n):
      if a[k+i]:
        dp[S|1<<i] = (dp[S|1<<i]+t)%mod
  print(dp[(1<<n)-1])
main()

Measured memory_bytes: 58716
#include <string.h>
#include <stdio.h>
#include <ctype.h>

int main(void)
{
	char W[11];
	char T[1001];
	
	int c = 0;
	int i;
	
	scanf("%s",W);
	for(i = 0;i < strlen(W);i++)W[i] = toupper(W[i]);
	
	while(1){
		scanf("%s",T);
		if(strcmp("end_of_text",T) == 0)continue;
		for(i = 0;i < strlen(T);i++)T[i] = toupper(T[i]);
		if(strcmp(T,"END_OF_TEXT") == 0)break;
		else if(strcmp(T,W) == 0)c++;
	}
	
	printf("%d\n",c);
		
	
	return 0;
}

Measured memory_bytes: 548
#include<bits/stdc++.h>                          
using namespace std;    
int a[105],n,x,y;
int main(){	
	cin>>n;
	for(int i=1;i<=100;i++)
	{
		if(i%4==0||i%7==0) a[i]=1;
		else 
		{
			x=i/7;
			for(int j=1;j<=x;j++)
			{
				y=i-j*7;
				if(y%4==0) {a[i]=1;break;}
			}
		}
	} 
	if(a[n]==1) cout<<"Yes";
	else cout<<"No";
	return 0;
}

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

#define thegamebegins   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fileio          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define int             long long
#define float           long double
#define test            int T; cin>>T; while(T--)
#define in(a,n)         for(int i=0; i<n; ++i)  cin>>a[i]
#define r0              return 0
#define E               "\n"
#define S               " "
#define elif            else if 
#define M               1000000007
#define fi(i,x,y)       for(int i=x; i<y; ++i)
#define fa(i,s)         for(auto i:s)
#define fp(i,s)         for(auto i=(s).begin(); i!=(s).end(); ++i)
#define sz(s)           (int)(s).size()
#define vi              vector <int>
#define vpii            vector <pair <int,int> >
#define mii             map <int,int>
#define pii             pair <int,int>
#define seti            set <int>
#define setd            set <int,greater <int> >
#define all(s)          (s).begin(),(s).end()
#define sortd(a,n)      sort(a, a+n, greater<int>())
#define pb              push_back
#define fr              first
#define sc              second
#define lb              lower_bound
#define ub              upper_bound
#define er              equal_range
 
const int INF = 0x3f3f3f3f;

signed main()
{
    thegamebegins

    int n;  cin>>n;
    int ans=0LL;
    fi(i,1,n+1) fi(j,1,n+1) fi(k,1,n+1)     ans+=__gcd(i,__gcd(j,k));
    cout<<ans;
    r0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

void extgcd(int a, int b, int &x, int &y){
	if(b == 0){
		x = 1;
		y = 0;
		return ;
	}
	extgcd(b,a%b,y,x);
	y -= a/b * x;
}

int mod_inverse(int a, int m){
	int x, y;
	extgcd(a, m, x, y);
	return (m + x % m ) % m;
}

int gcd(int a, int b) {return a%b?gcd(b, a%b):b;};

pair<int,int> liner_congrunce(const vector<int>& A, const vector<int>& B, const vector<int>& M){
	
	int x = 0, m = 1;
	
	for(int i = 0; i < A.size(); i++){ //cout<<"i = "<<i<<" A = "<<A[i]<<" B = "<<B[i]<<" M = "<<M[i]<<endl;
		int a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a);
		if(b % d != 0) return make_pair(0, -1);
		int t =  b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d);
		x = x + m * t;
		m *= M[i] / d;
	}
	
	return make_pair((x%m + m) % m, m);
}


signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	vector<int> P, Q, T, C, con1, con2, con0;
	
	cin>>N;
	
	P.assign(N,0);
	Q.assign(N,0);
	T.assign(N,0);
	C.assign(N,0);
	con1.assign(N,-1);
	con2.assign(N,-1);
	con0.assign(N,1);
	
	for(int i = 0; i < N; i++){
		cin>>P[i];
		P[i]--;
		C[P[i]] = i;
		T[i] = P[i];
	}
	
	for(int i = 0; i < N; i++){
		cin>>Q[i];
		Q[i]--;
	}
	
	for(int i = 0; i < N*2; i++){
		// cout<<"---------- <><> "<<i<<endl;
		// for(int j = 0; j < N; j++){
			// cout<<T[j]<<" ";
		// }
		// cout<<endl;
		
		for(int j = 0; j < N; j++){
			if(T[j] == j){
				if(con1[j] == -1){
					con1[j] = i;
				} else if(con2[j] == -1){
					con2[j] = i - con1[j];
				}
			}
			T[j] = Q[T[j]];
		}
	}
	
	pair<int,int> ans;
	
	ans = liner_congrunce(con0, con1, con2);
	
	if(ans.second == -1) cout<<-1<<endl;
	else cout<<ans.first<<endl;

	
	return 0;
}


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

int sd(int x) {
	int y=0;
	while (x) {
		y += x % 10;
		x /= 10;
	}
	return y;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	int n, z = 123123123;
	cin >> n;
	for (int i=1; i<n; i++) {
		z = min(z, sd(i) + sd(n-i));
	}
	cout << z;
}

Measured memory_bytes: 892
//  RAKSHIT KADAM
 #include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
 #warning !!!check the size of arrayss!!!

 #define ll long long
 #define int long long
 #define MOD  1000000007
 #define newMOD  998244353
 #define MAX 200006
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define endl "\n"
 #define x first
 #define y second
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define INF 1000000000000000005
 #define vi vector<ll>
 #define PI 3.14159265

using namespace std;
//int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;                                                  return (y%2 == 0)? p : (x * p) % m;}

//ll modInverse(int a, int m){int g = gcd(a, m); { return power(a, m-2, m);}}
//ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll a[MAX];
void solve()
{
    
    ll n;cin>>n;
    ll ans=0;
    ll s=n/500;
    ans+=s*1000;
    n-=s*500;
    ans+=5*(n/5);
    cout<<ans<<endl;
}
signed main()
{
    Need_for_speed(activated);
//       satisfy
//       {
//           solve();
//       }
//
  solve();
//
    
    return 0;}




Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


    const long long MOD = 1000000007;
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        if (A[i] > i) {
            cout << 0 << '\n';
            return 0;
        }
    }

    vector<vector<int>> pos(n + 1);
    pos[0] = {-1, -2, -3};

    for (int i = 0; i < n; ++i) {
        pos[A[i] + 1].push_back(i);
    }
    for (int i = 0; i <= n; ++i) {
        if (pos[i].size() > 3) {
            cout << 0 << '\n';
            return 0;
        }
        if (i - 1 >= 0 && pos[i].size() > pos[i - 1].size()) {
            cout << 0 << '\n';
            return 0;
        }
    }

    long long res = 1;

    for (int i = 1; i <= n; ++i) {
        if (pos[i].size() == 0) {
            break;
        }

        auto ord = pos[i];
        while (ord.size() < pos[i - 1].size()) {
            ord.push_back(n);
        }

        sort(ord.begin(), ord.end());
        long long cnt = 0;
        do {
            bool ok = true;
            for (int j = 0; j < ord.size(); ++j) {
                if (ord[j] <= pos[i - 1][j]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ++cnt;
            }
        } while (next_permutation(ord.begin(), ord.end()));

        (res *= cnt) %= MOD;
    }


    cout << res << '\n';


    return 0;
}

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

int main(){
    string str;
    
    while(getline(cin,str)){
        int JOI = 0 , IOI = 0;
        for(int i = 0 ; i < str.length() ; i++){
            string key = str.substr(i,3),repl;
            if(key == "JOI") JOI++;
            else if(key == "IOI") IOI++;
        }
        cout << JOI << endl;
        cout << IOI << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1204
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

const li mod = 1e9 + 7;

int main() {
    set<int> s;
    for (int i = 0; i < 4; ++i) {
        int x;
        cin >> x;
        s.insert(x);
    }
    bool ok = true;
    ok &= s.find(1) != s.end();
    ok &= s.find(9) != s.end();
    ok &= s.find(7) != s.end();
    ok &= s.find(4) != s.end();
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}


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

def solve():
    import bisect

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))
    Cs = list(map(int, input().split()))
    As.sort(), Bs.sort(), Cs.sort()
    lenA, lenB, lenC = len(As), len(Bs), len(Cs)

    Bs_cases = [0 for _ in range(lenB)]  # Bs[bi]を選んだときの、Csの選び方の場合の数
    for bi in range(lenB-1, -1, -1):
        cidx = bisect.bisect_right(Cs, Bs[bi])
        if cidx == lenC:
            Bs_cases[bi] = 0
        else:
            Bs_cases[bi] = lenC-cidx

    Bs_cases_ruiseki = [0 for _ in range(lenB)]  # Bs[bi]を選んだときの、Csの選び方の場合の数の累積和
    Bs_cases_ruiseki[lenB-1] = Bs_cases[lenB-1]
    for bi in range(lenB-2, -1, -1):
        Bs_cases_ruiseki[bi] = Bs_cases_ruiseki[bi+1] + Bs_cases[bi]

    ans = 0
    for a in As:
        bidx = bisect.bisect_right(Bs, a)
        if bidx == lenB:
            continue
        ans += Bs_cases_ruiseki[bidx]

    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 24000
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, a;
//   int ans = 0;
  cin >> n;
  vector<int> ans(n,0);
  for(int i=1; i<n; i++){
      cin >> a;
      ans.at(a-1)++;
  }
  
  for(int i=0; i < n; i++){
    cout << ans.at(i) << endl;  
  }
//   cout << ans << endl;
}

Measured memory_bytes: 4048
#include <cstdio>

using namespace std;

int main() {
  int n,k;
  double max=0.0,P[200000],sum[200000];
  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++){
    scanf("%lf",&P[i]);
    P[i]=(P[i]+1.0)/2.0;
    if(i==0)sum[i]=P[i];
    else sum[i]=sum[i-1]+P[i];
  }
  if(n==k){
    printf("%lf\n",sum[n-1]);
    return 0;
  }
  for(int i=0;i<n-k;i++){
    if(sum[i+k]-sum[i]>=max)max=sum[i+k]-sum[i];
  }
  printf("%lf\n",max);
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a == b && b == c) {
    cout << 1 << endl;
  }else if(a != b && b != c && c != a) {
    cout << 3 << endl;
  }else {
    cout << 2 << endl;
  }
}

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

ll mod_pow(ll n, ll p, ll mod){
    // return (n^p) % mod
    if(p==0) return 1;
    ll res = mod_pow(n*n%mod, p/2, mod);
    if(p%2==1) res = res * n % mod;
    return res;
}

int main(){
    string L;  cin >> L;
    ll N = L.length();
    ll mod = 1e9+7;

    // d を求める。
    // d[i] = 2^(L_0～L_i までの 1 の数) 
    vector<ll> d(N,0);
    d[0] = 2;
    for(int i=1; i<N; i++){
        if(L[i]=='0') d[i] = d[i-1];
        else d[i] = 2*d[i-1]%mod;
    }

    ll ans = 0;

    // (1) の場合
    ans += d[N-1];

    // (2) の場合
    for(int k=0; k<N; k++){
        if(L[k]=='0') continue;  // L[k] = 1 についてのみ和を取る

        ll tmp = 1;
        if(k>0){
            // k=0 のときは (2-2) の 1 つ目の条件を無視する
            tmp = tmp*d[k-1]%mod;
        }
        // (2-2) の 3 つ目の条件
        tmp = tmp*mod_pow(3, N-k-1, mod)%mod;

        ans = (ans +tmp)%mod;
    }    
    cout << ans << endl;
}

Measured memory_bytes: 1280
#include <iostream>
using namespace std;
int main(void){
    int i=0,n,x,c;
    while(i<5){
        cin >> x;
        if(x==0) break;
        c=0;
        n=1000-x;
        if(n>=500){
            c++;
            n-=500;
        }
        while(n>=100){
            c++;
            n-=100;
        }
        if(n>=50){
            c++;
            n-=50;
        }                
        while(n>=10){
            c++;
            n-=10;
        }
        if(n>=5){
            c++;
            n-=5;
        }
        while(n>0){
            c++;
            n-=1;
        }
        i++;
        cout<<c<<endl;
    }
    
}



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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int64_t> a;
  vector<int64_t> b;
  int64_t ans=0;
  for(int i=0;i<n+1;i++){
    int tmp=0;
    cin >> tmp;
    a.push_back(tmp);
  }
  for(int i=0;i<n;i++){
    int tmp=0;
    cin >> tmp;
    b.push_back(tmp);
  }
  for(int i=0;i<n;i++){
    if( a.at(i)-b.at(i)>=0 ){
      ans=ans+b.at(i);
      //cout << "a" ;
    }
    else{
      ans = ans + a.at(i);
      if( a.at(i+1)-( b.at(i)-a.at(i) ) >= 0){
        a.at(i+1) = a.at(i+1)-( b.at(i)-a.at(i) );
        ans=ans+b.at(i)-a.at(i);
        //cout << "b";
      }
      else{
        ans=ans+a.at(i+1);
        a.at(i+1)=0;
        // cout << "c";
      }
    }
    // for(auto g: a){
    //   cout << g;
    // }
    // cout << endl;
    // for(auto f: b){
    //   cout << f;
    // }
    // cout << endl;
  }

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


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;
//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

void solve() {
    ll n,m;
    cin >> n >> m;
    ll ans = 0;
    if (m < n) swap(m,n);
    if (m == 1 && n == 1) {
        ans += 1;
    } else if (n == 1) {
        ans += m - 2;
    } else {
        ans += (n - 2) * (m - 2);
    }
    cout << ans << endl;
}

int main(int argc, char *argv[]){
    // /* Regular */
    // int case_num = 1;
    // if (argc > 1 && stoi(argv[1])) cin >> case_num;
    // REP(case_no, case_num) {
    //   cerr << endl << "case " << case_no + 1 << endl;
    //   solve();
    // }
    /* AOJ */
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi			first
#define se			second
#define fz(i,a,b)	for(int i=a;i<=b;i++)
#define fd(i,a,b)	for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)		a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)	memset(a,0,sizeof(a))
#define fill1(a)	memset(a,-1,sizeof(a))
#define fillbig(a)	memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)		(1ll<<(a))
#define maskx(a,x)	((a)<<(x))
#define _bit(a,x)	(((a)>>(x))&1)
#define _sz(a)		((int)(a).size())
#define filei(a)	freopen(a,"r",stdin);
#define fileo(a)	freopen(a,"w",stdout);
#define fileio(a) 	freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)		putchar(x)
#define eoln        put('\n')
#define space		put(' ')
#define y1			y_chenxiaoyan_1
#define y0			y_chenxiaoyan_0
typedef pair<int,int> pii;
inline int read(){
	int x=0,neg=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	neg=-1;
		c=getchar();
	}
	while(isdigit(c))	x=x*10+c-'0',c=getchar();
	return x*neg;
}
inline void print(int x){
	if(x<0){
		putchar('-');
		print(abs(x));
		return;
	}
	if(x<=9)	putchar(x+'0');
	else{
		print(x/10);
		putchar(x%10+'0');
	}
}
inline int qpow(int x,int e,int _MOD){
	int ans=1;
	while(e){
		if(e&1)	ans=ans*x%_MOD;
		x=x*x%_MOD;
		e>>=1;
	}
	return ans;
}
int n=read(),m=read(),q=read();
int a[55],b[55],c[55],d[55];
int x[15],ans=0;
inline void dfs(int cur){
	if(cur==n+1){
		int sum=0;
		fz(i,1,q){
			if(x[b[i]]-x[a[i]]==c[i])	sum+=d[i];
		}
		ans=max(ans,sum);
		return;
	}
	fz(i,x[cur-1],m){
		x[cur]=i;
		dfs(cur+1);
	}
}
signed main(){
	x[0]=1;
	fz(i,1,q)	cin>>a[i]>>b[i]>>c[i]>>d[i];
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3520
//abc138_d.cpp
//Sun Aug 18 20:46:22 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

vector<int> G[200000];
int plusnum[200000];
int ans[200000];
int visited[200000];

void dfs(int node, int total){
	visited[node]=1;
	total += plusnum[node];
	ans[node] = total;
//	cout << node << " " << ans[node] << endl;
	for (int i=0;i<G[node].size();i++){
		if (visited[G[node][i]]==0){
			dfs(G[node][i],total);
		}
	}
}

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

	for (int i=0;i<n-1;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	fill(plusnum,plusnum+200000,0);
	for (int i=0;i<q;i++){
		int p,x;
		cin >> p >> x;
		p--;
		plusnum[p] += x;
	}

	fill(ans,ans+200000,0);
	fill(visited,visited+200000,0);
	dfs(0,0);

	for (int i=0;i<n;i++){
		cout << ans[i] << " ";
	}
	printf("\n");
}

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

#define N 3001

using namespace std;

int n;
bool p;
long long a[N];
long long dp[N][N];
long long vis[N][N] = {0};

long long solve(int i, int j)
{
	if (j < i)
		return 0;
	if (vis[i][j])
		return dp[i][j];
	vis[i][j] = 1;
	//cout << ((j - i + 1) & 1);
	if (((j - i + 1) & 1) == p)
		return dp[i][j] = max(a[i] + solve(i + 1, j), a[j] + solve(i, j - 1));
	return dp[i][j] = min(solve(i + 1, j) - a[i], solve(i, j - 1) - a[j]);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	p = n & 1;
	cout << solve(0, n - 1) << endl;
	return 0;
}


Measured memory_bytes: 139904
H,W = map(int, input().split())
L = []
while H != 0 or W != 0:
 L.append([H, W])
 H,W = map(int, input().split())

def draw(H,W):
 print("#" * W)
 for i in range(H-2):
  print("#" + "." * (W - 2) + "#")
 print("#" * W)
 print("")

for (H, W) in L:
 draw(H,W)

Measured memory_bytes: 7600
#![allow(non_snake_case)]

use std::io;
use std::str::FromStr;

macro_rules! parse_tuple {
    ($($t: ty),+) => ({
        let mut a_str = String::new();
        io::stdin().read_line(&mut a_str).expect("read error");
        let mut a_iter = a_str.split_whitespace();
        (
            $(
                a_iter.next().unwrap().parse::<$t>().expect("parse error"),
            )+
        )
    })
}

fn parse_vec<T: FromStr>() -> Vec<T> {
    let mut tmp = String::new();
    io::stdin().read_line(&mut tmp).unwrap();
    return tmp.split_whitespace().filter_map(|s| s.trim().parse().ok()).collect();
}

fn main() {
    parse_tuple!(usize);
    let a = parse_vec::<u64>();
    let mut count = 0;
    for v in a {
        count += v.trailing_zeros();
    }
    println!("{}", count);
}

Measured memory_bytes: 4352
INF = 10**15
N,K = map(int,input().split())
x = list(map(int,input().split()))
num = 0
positive = []
negative = []
for i in range(N):
    if x[i] == 0:
        N  -= 1
    elif x[i] < 0:
        negative.append(x[i])
    else:
        positive.append(x[i])
negative = negative[::-1]
dist = INF
if len(positive) >= K :
    dist = positive[K-1]
    
for i in range(len(negative)):
    if len(positive) > 0 and len(positive) >= K - (i+1) :
        tmp = - 2*negative[i] + positive[K-1-i-1]
        if dist > tmp:
            dist = tmp
            

if len(negative) >= K and dist > -negative[K-1]:
    dist  = -negative[K-1]

for i in range(len(positive)):
    if len(negative) > 0 and len(negative) >= K - (i+1) :
        tmp = -negative[K-1-i-1] + 2*positive[i]
        if dist > tmp:
            dist = tmp
if N == 0:
    print(x[0])
else:
    print(dist)
    

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

bool judgment_dream(string &S, int &n) {
  string s1 = "dream";
  bool result = true;
  for (int i = 0; i < s1.size(); i++) {
    if (n - i >= 0) {
      if (S.at(n - i) != s1.at(s1.size() - i - 1)) {
        result = false;
        break;
      }
    }
    else {
      result = false;
    }
  }
  if (result == true) {
    n -= s1.size();
  }
  return result;
}

bool judgment_dreamer(string &S, int &n) {
  string s1 = "dreamer";
  bool result = true;
  for (int i = 0; i < s1.size(); i++) {
    if (n - i >= 0) {
      if (S.at(n - i) != s1.at(s1.size() - i - 1)) {
        result = false;
        break;
      }
    }
    else {
      result = false;
    }
  }
  if (result == true) {
    n -= s1.size();
  }
  return result;
}

bool judgment_erase(string &S, int &n) {
  string s1 = "erase";
  bool result = true;
  for (int i = 0; i < s1.size(); i++) {
    if (n - i >= 0) {
      if (S.at(n - i) != s1.at(s1.size() - i - 1)) {
        result = false;
        break;
      }
    }
    else {
      result = false;
    }
  }
  if (result == true) {
    n -= s1.size();
  }
  return result;
}

bool judgment_eraser(string &S, int &n) {
  string s1 = "eraser";
  bool result = true;
  for (int i = 0; i < s1.size(); i++) {
    if (n - i >= 0) {
      if (S.at(n - i) != s1.at(s1.size() - i - 1)) {
        result = false;
        break;
      }
    }
    else {
      result = false;
    }
  }
  if (result == true) {
    n -= s1.size();
  }
  return result;
}

int main() {
  string S;
  cin >> S;
  int n = S.size();
  n--;
  bool result = true;
  
  while (n > 0 && result == true) {
    if (judgment_dream(S, n)) {
    }
    else if (judgment_dreamer(S, n)) {
    }
    else if (judgment_erase(S, n)) {
    }
    else if (judgment_eraser(S, n)) {
    }
    else {
      result = false;
    }
  }
  if (result) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    
    if(a>b){
        cout<<"a"<<" "<<">"<<" "<<"b"<<endl;
    }else if (a<b){
    cout<<"a"<<" "<<"<"<<" "<<"b"<<endl;    
    }else{ 
        cout<<"a"<<" "<<"=="<<" "<<"b"<<endl;
    }
}


Measured memory_bytes: 3096
#include <stdio.h>
 
 
int main()
{
    int S,h,m,s;
 
    scanf("%d",&S);
    h = S / 3600;
    m = (S - h*3600) / 60;
    s = (S - h * 3600 - m * 60);
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}

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

typedef long long ll;
ll s[5];

int main(){
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		string str;
		cin>>str;
		if(str[0]=='M')s[0]++;
		if(str[0]=='A')s[1]++;
		if(str[0]=='R')s[2]++;
		if(str[0]=='C')s[3]++;
		if(str[0]=='H')s[4]++;
	}
	ll ans=0;
	for(int i=0;i<3;i++){
		for(int j=i+1;j<4;j++){
			for(int k=j+1;k<5;k++){
				ans+=s[i]*s[j]*s[k];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define P pair<int,int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define endl '\n'
#define ll long long

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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


    vector<int> X(M), Y(M);
    rep(i,M) {
        cin >> X[i] >> Y[i];
        X[i]--, Y[i]--;
    }

    int ans = 0;
    for(int i = 0; i < M; i++){
        UnionFind Tree(N);
        for(int j = 0; j < M; j++){
            if(j == i) continue;
            Tree.unite(X[j],Y[j]);
        }
        map<int,int> mp;
        for(int j = 0 ; j < N; j++){
            int r = Tree.root(j);
            mp[r]++;
        }
        if(mp.size() != 1) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const int N = 3e3+6;
const int mod = 1e9+7;
const ll inf = 1e18;
int a[N];
void solve(){
    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    int dx = tx-sx;
    int dy = ty-sy;
    for(int i=0;i<dx;i++)cout<<"R";
    for(int i=0;i<dy;i++)cout<<"U";
    for(int i=0;i<dx;i++)cout<<"L";
    for(int i=0;i<dy;i++)cout<<"D";
    cout<<"L";
    for(int i=0;i<dy+1;i++)cout<<"U";
    for(int i=0;i<dx+1;i++)cout<<"R";
    cout<<"DR";
    for(int i=0;i<dy+1;i++)cout<<"D";
    for(int i=0;i<dx+1;i++)cout<<"L";
    cout<<"U";
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--)solve();
    return 0;
}


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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

LL n, m, res;

bool ok(LL tar){
	LL tm = m - 2 * tar;
	if(tm < 0) return false;
	LL rem = tm / 2 + n;
	if(rem < tar) return false;
	return true;
}

int main(){
	scanf("%lld %lld", &n, &m);
	LL l = 0, r = m / 2 + 10;
	while(r - l > 1){
		LL mid = (l + r) >> 1;
		if(ok(mid)) l = mid;
		else r = mid;
	}
	printf("%lld\n", l);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define MOD 1000000007
#define ALL(a) (a).begin(),(a).end()
#define ms(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10) 
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
struct edge{ int from, to, cost; };

string s;

int main()
{
	vector<P> m; vector<P> n;
	int N, M;
	while (cin >> M, M)
	{
		m.clear(); n.clear();
		int x, y;
		REP(i, M)
		{
			cin >> x >> y;
			m.push_back(P(x, y));
		}
		sort(ALL(m));
		cin >> N;
		REP(i, N)
		{
			cin >> x >> y;
			n.push_back(P(x, y));
		}
		sort(ALL(n));
		REP(i, 300) n.push_back(P(INF, INF));
		REP(i, N)
		{
			int dx, dy;
			dx = n[i].first - m[0].first; dy = n[i].second - m[0].second;

			REP(j, M)
			{
				FOR(k, i, N)
				{
					if (m[j].first + dx == n[k].first&&m[j].second + dy == n[k].second)
					{
						goto next;
					}

				}
				goto end;
			next:;
			}
			cout << dx << " " << dy << endl;

		end:;
		}
	}
	return 0;
}

Measured memory_bytes: 1232
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int const kNumClasses = 4;

vector<uint64_t> g_classes[kNumClasses];
vector<uint64_t> g_prefixSums[kNumClasses];

int main() {
  int n;
  uint64_t capacity;

  uint64_t pivot = 0;
  cin >> n >> capacity;
  for (int i = 0; i < n; ++i) {
    uint64_t weight, value;
    cin >> weight >> value;
    if (i == 0)
      pivot = weight;

    assert(weight >= pivot);
    assert(weight < pivot + kNumClasses);
    g_classes[weight - pivot].push_back(value);
  }

  for (int i = 0; i < kNumClasses; ++i) {
    auto &klass = g_classes[i];
    sort(klass.rbegin(), klass.rend());

    auto &sums = g_prefixSums[i];
    sums.push_back(0);
    for (auto const &value : klass) {
      auto const sum = sums.back() + value;
      sums.push_back(sum);
    }
  }

  uint64_t best = 0;
  for (int a = 0; a <= g_classes[0].size(); ++a) {
    uint64_t const w1 = pivot * a;
    if (w1 > capacity)
      break;

    for (int b = 0; b <= g_classes[1].size(); ++b) {
      uint64_t const w2 = w1 + (pivot + 1) * b;
      if (w2 > capacity)
        break;

      for (int c = 0; c <= g_classes[2].size(); ++c) {
        uint64_t const w3 = w2 + (pivot + 2) * c;
        if (w3 > capacity)
          break;

        uint64_t d = (capacity - w3) / (pivot + 3);
        if (d > g_classes[3].size())
          d = g_classes[3].size();

        uint64_t const curr = g_prefixSums[0][a] + g_prefixSums[1][b] +
                              g_prefixSums[2][c] + g_prefixSums[3][d];
        if (curr > best)
          best = curr;
      }
    }
  }

  cout << best << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]

L = [0]*(N+1)
for a in A:
    L[a] += 1

ans = 0
for l in L:
    ans += l*(l-1)//2
    
for a in A:
    print(ans - L[a]*(L[a]-1)//2 + (L[a]-1)*(L[a]-2)//2)

Measured memory_bytes: 26268
#include <bits/stdc++.h>
# define ll int64_t
#define rep(i,n) for(ll i=0;i<n;i++)
#define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}


int main(){
    ll n,k,sum = 0;
    cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    cin>>k;
    vector<ll> b(k);
    rep(i,k) cin>>b[i];
    
    rep(i,k) {
        ll left = 0,right = n;
        ll mid;
        while(left<right){
            mid = (left+right)/2;
            if(b[i]==a[mid]){
                sum++;
                break;
            }
            if(b[i] > a[mid]) left = mid+1;
            if(b[i] < a[mid]) right = mid;
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3820
n = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
amari = a_list[0]
kill = 0
for i in range(n):
  b = b_list[i]
  if amari > b:
    kill += b
    b = 0
  else:
    b -= amari
    kill += amari
  if b > a_list[i+1]:
    kill += a_list[i+1]
    amari = 0
  else:
    kill += b
    amari = a_list[i+1] - b
print(kill)

Measured memory_bytes: 18476
#include<bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 998244353;
const ll mod1 = 2e18 + 7;
const double tiaohe = 0.57721566490153286060651209;
const int inf = 0x3f3f3f3f;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;
const int N = 6e5 + 5;
int t;
int a[N];
int main()
{
	//freopen("in.txt", "r", stdin);
	ll n;
	while (cin >> n)
	{
		ll ans = 0;
		ll now = 1;
		while (n > 1)
		{
			n /= 2;
			ans += now;
			now <<=1;
			//debug(ans);
		}
		ans += now;
		cout << ans << endl;
	}
	return 0;
}

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

int cardno(char suit,int rank) {
	int sn;
	switch (suit){
		case 'S':
			sn=0;
			break;
		case 'H':
			sn=1;
			break;
		case 'C':
			sn=2;
			break;
		case 'D':
			sn=3;
			break;
		default:
			sn=-1;
	}
	if (sn == -1)
		return -1;
	else {
		return 13*sn + rank - 1;
	}
}

char cardsuit(int no){
	if(0<=no && no<13)
		return 'S';
	else {
		if (13<=no && no<26)
			return 'H';
		else {
			if (26<=no && no<39)
				return 'C';
			else {
				if (39<=no && no<52)
					return 'D';
				else
					return -1;
			}
		}
	}
}

int cardrank(int no){
	if (0<=no && no<52)
		return (no % 13) +1;
	else
		return -1;
}

int main() {
	int n,card[52];
	int rank;
	char suit;

	cin >> n;		// number of cards
	for (int i=0;i<52;i++)
		card[i]=0;	// card initialize
	for (int i=0;i<n;i++){
		cin >> suit >> rank;	// Card Input
		card[cardno(suit,rank)]=1;
	}
	for (int i=0;i<52;i++){
		if (card[i] != 1){
			cout << cardsuit(i) << ' ' << cardrank(i) << endl;	// Missing Card Output
		}
	}
	return 0;
}



Measured memory_bytes: 3020
n = int(input())
a = list(map(int, input().split()))
count = 0
flg = True
while flg:
    for i in range(len(a)):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            flg = False
    if flg:
        count = count + 1


print(count)


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

using namespace std;

int main(){

 int_fast64_t s; cin>>s;

 int c = 1000;

 while(s>=100){

  int finds = s%1000;
  //cout<<finds<<" "<<c<<endl;
  int mini = abs(finds-753);
   c = min(c,mini);
   s = s/10;
}

 cout<<c<<endl;

return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
constexpr long long int mod = 1000000007, MOD = 998244353;
constexpr double PI = 3.14159265358979323846;

int main() {
	long long X, K, D;
	cin >> X >> K >> D;
	X = abs(X);
	long long Nearestmove = X / D,Nearestpos=X-D*Nearestmove;
	cerr << Nearestpos << endl<<Nearestmove<<endl;
	if (K - Nearestmove < 0)cout << X - K * D;
	else if ((K - Nearestmove) % 2 != 0)cout << abs(Nearestpos - D);
	else cout << Nearestpos;

}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>

template<class T>
class FenwickTree {
 public:
  std::vector<T> data;
  FenwickTree<T>(unsigned size) : data(size + 1u, 0) {}
  T sum(unsigned index) {
    ++index;
    T ret = 0;
    while (index) {
      ret += data[index];
      index &= index - 1u;
    }
    return ret;
  }
  void add(unsigned index, T x) {
    ++index;
    while (index <= data.size()) {
      data[index] += x;
      index += index & (~index + 1u);
    }
  }
};

template<class T>
unsigned long long n_order_lte(const std::vector<T> &a) {
  std::vector<T> b(a);
  std::sort(b.begin(), b.end());
  FenwickTree<unsigned long long> fenwickTree(static_cast<unsigned>(a.size()));
  unsigned long long ans = 0;
  for (unsigned i = 0; i < a.size(); ++i) {
    unsigned x = b.end() - std::lower_bound(b.begin(), b.end(), a[i]) - 1;
    ans += x - fenwickTree.sum(x);
    x = b.end() - std::upper_bound(b.begin(), b.end(), a[i]);
    fenwickTree.add(x, 1);
  }
  return ans;
}

int main() {
  unsigned long long N;
  long long K;
  std::cin >> N >> K;
  std::vector<long long> a(N+1);
  a[0] = 0;
  for (unsigned i = 1; i <= N; ++i) {
    std::cin >> a[i];
    a[i] -= K;
  }
  for (unsigned i = 1; i <= N; ++i) {
    a[i] += a[i - 1];
  }
  std::cout << n_order_lte(a);
  return 0;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)


int nCr(int n , int r ) {
	int p = 1, k = 1;

	if (n - r < r ) {
		r = n - r;
	}
	if (r != 0) {
		while (r != 0) {
			p *= n ;
			k *= r ;
			int m = __gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else {
		p = 1;
	}
	return p ;
}

void aryan_p() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return;
}


int32_t main() {


	string s;
	cin >> s;

	if (s == "MON") {
		cout << 6;
	}
	else if (s == "TUE") {
		cout << 5;
	}

	else if (s == "WED") {
		cout << 4;
	}

	else if (s == "THU") {
		cout << 3;
	}


	else if (s == "FRI") {
		cout << 2;
	}

	else if (s == "SAT") {
		cout << 1;
	}

	else  {
		cout << 7;
	}




	return 0;
}

Measured memory_bytes: 3568
#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele　単位元#####
ide_ele = 0
#################



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

"""使用例"""

n,k=map(int,input().split())
A=[int(input()) for i in range(n)]

T=[0 for i in range(300000+1)]
T=SegTree(T,segfunc,ide_ele)

for num in A:
    now=T.query(max(0,num-k),min(num+k+1,300002))
    #print(now)
    T.update(num,now+1)

print(T.query(0,300001))



Measured memory_bytes: 121856
#include<iostream>
#include<fstream>
#include<climits>
using namespace std;

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

ll gcd(ll x, ll y) {
	if (x == 0) return y;
	return gcd(y%x, x);
}

int N;
long long A, B, C, D;

void solve() {
	if (A < B || D < B)
		cout << "No" << endl;
	else {
		long g = gcd(B, D);
		long worst = g - A % g;
		if (C >= B - worst) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> A >> B >> C >> D;
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<list>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;

struct a
{
	int b, c, d;
};
a e[500];
int dp[501][501];//????????????n????¨???????m
int main() {
	int f, g;
	while (cin >> f >> g, f | g) {
		int MAX = 500;
		for (int h = 0; h < g; h++) {
			int i, j, k;
			scanf("%d%d%d", &i, &j, &k);
			e[h] = { i,j,k };
		}
		for (int h = 0; h <= f; h++) {
			for (int i = 0; i <= MAX;i++) {
				dp[h][i] = 1 << 29;
				if (h == 0)dp[h][i] = 0;
			}
		}
		for (int h = 1; h <= f; h++) {
			for (int i = MAX; i >= 0;i--) {
				for (int j = 0; j < g; j++) {
					if (i >= e[j].d) {
						dp[h][i] = min(dp[h][i], 1 + dp[max(0,h - e[j].b)][min(MAX, i + e[j].c)]);
					}
				}
			}
		}
		if (dp[f][0] >= 100000)puts("NA");
		else cout << dp[f][0] << endl;
	}
}

Measured memory_bytes: 3436
N,M = map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]

def imp(n, m, lst):
  for i in range(m):
    if (n > 1) and (lst[i][0] == 1) and (lst[i][1] == 0):
      return True
  for i in range(0, m-1):
    for j in range(1, m):
      if (lst[i][0] == lst[j][0]) and (lst[i][1] != lst[j][1]):
        return True
  return False

def num(n, m, lst):
  if imp(n, m, lst):
    return -1
  res = []
  for i in range(n):
    res.append(0)
  for i in range(m):
    res[lst[i][0]-1] = lst[i][1]
  if (n > 1) and (res[0] == 0):
    res[0] = 1
  return("".join(map(str, res)))

print(num(N,M,List))



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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u; return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

int N, X, Y;
int num[2005] = {};
vvint G;

void bfs(int s) {
	queue<int> que;
	vint mc(N, -1);

	que.push(s);
	mc[s] = 0;
	while (!que.empty()) {
		int u = que.front(); que.pop();
		for (auto &v : G[u]) {
			if (mc[v] == -1) {
				mc[v] = mc[u] + 1;
				que.push(v);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		num[mc[i]]++;
	}
}

void Main() {
	cin >> N >> X >> Y; --X, --Y;

	G = vvint(N);
	G[X].push_back(Y);
	G[Y].push_back(X);
	for (int i = 0; i < N-1; i++) {
		G[i].push_back(i+1);
		G[i+1].push_back(i);
	}
	
	for (int i = 0; i < N; i++) {
		bfs(i);
	}

	for (int k = 1; k < N; k++) {
		cout << num[k]/2 << el;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<complex>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

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

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 3 * 1000 * 100 + 47;

int A[MAX];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	//ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	FOR(i, 0, 3 * n) cin >> A[i];
	sort(A, A + 3 * n);
	reverse(A, A + 3 * n);
	LL s = 0;
	for (int i = 1; i < 2 * n; i += 2)
	{
		s += A[i];
	}

	cout << s << endl;	
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
//#include <iostream>
//#include <string>
//#include <sstream>
//#include <vector>
//#include <algorithm>
//#include <map>
//#include <set>
//#include <math.h>
//#include <unordered_map>
//#include <queue>
//#include <stack>
//#include <iomanip>

using namespace std;

#define PI 3.141592653589793238462643383279502884
#define Max 100005
#define ll long long
#define mod 2
#define EPS 1E-9

vector< pair<int, int> >v;
void get_div(ll n)
{
	for (int i = 1; i <= sqrt(n); i++)
	{
		if (n%i == 0)
		{
			if (i*i != n)
				v.push_back(make_pair(i, (n / i)));
			else
				v.push_back(make_pair(i, i));
		}
	}
}
int get_max_sz(string s1, string s2)
{
	return max(s1.size(), s2.size());
}



int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	get_div(n);
	string tmp1, tmp2;
	int mn = INT_MAX;
	int res;
	for (int i = 0; i<v.size(); i++)
	{
		tmp1 = to_string(v[i].first);
		tmp2 = to_string(v[i].second);
		res = get_max_sz(tmp1, tmp2);
		if (res<mn)
			mn = res;
	}
	cout << mn << endl;

	return 0;
}


Measured memory_bytes: 256