akhauriyash/Code-Regression huggingface dataset:
A,B = map(int,input().split())
count = 0
k = B-A
for j in range(k+1):
    a = A+j
    a = str(a)
    a = list(a)
    L = len(a)
    flag = 0
    for i in range(int(L/2)):
        if a[i] == a[-i-1]:
            pass
        else:
            flag = 1
            break
    if flag == 0:
        count+=1
print(count)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 2e5 + 9, maxV = 1e6 + 9, MOD = 998244353, SQ = 335, lg = 20, bs = 29;

ll fastPow(ll a, ll b) {
	ll ret = 1;
	while(b) {
		if(b & 1) ret = ret * a % MOD;
		b >>= 1, a = a * a % MOD;
	}
	return ret;
}

ll fac[maxN][2], pws[maxN];

ll ncr(int n, int k) {
	return fac[n][0] * fac[k][1] % MOD * fac[n - k][1] % MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int n, m, k;
	cin >> n >> m >> k;

	fac[0][0] = 1;
	for(int i = 1; i <= n; i++) fac[i][0] = fac[i - 1][0] * i % MOD;
	fac[n][1] = fastPow(fac[n][0], MOD - 2);
	for(int i = n - 1; i >= 0; i--) fac[i][1] = fac[i + 1][1] * (i + 1) % MOD;
	pws[0] = 1;
	for(int i = 1; i <= n; i++) pws[i] = pws[i - 1] * (m - 1) % MOD;
	ll ans = 0;
	for(int i = 0; i <= k; i++) {
		ans = (ans + ncr(n - 1, i) * pws[n - 1 - i]) % MOD;
		//debug(ans);
	}
	ans = ans * m % MOD;
	cout << ans << '\n';
}



Measured memory_bytes: 8280
#include<bits/stdc++.h>
using namespace std;
char s[100001];
int main()
{
    gets(s);
    int i,z=0;
    for(i=1;i<strlen(s);i++)
    if(s[i]!=s[i-1])
    z++;
    printf("%d\n",z);
    return 0;
}

Measured memory_bytes: 384
//Created Time:2019年12月19日 星期四 21时02分54秒
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 100005

using namespace std;

int n;
int val[N];

vector < int > G[N];

void dfs(int ,int);

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", val + i);
	for(int i = 1; i < n; ++i){
		int u, v; scanf("%d%d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
	}
	if(n == 2){
		if(val[1] != val[2]) puts("NO");
		else puts("YES");
		return 0;
	}
	for(int i = 1; i <= n; ++i){
		if(G[i].size() == 1) continue;
		dfs(i, 0);
		if(val[i]) puts("NO");
		else puts("YES");
		return 0;
	}
	return 0;
}

void dfs(int u, int fa){
	int sz = G[u].size(), mx = 0; long long sum = 0;
	if(sz == 1) return ;
	for(int i = 0; i < sz; ++i){
		int v = G[u][i]; if(v == fa) continue;
		dfs(v, u); sum += val[v];  mx = max(mx, val[v]);
	}
	if(sum < val[u] || val[u] * 2 < sum || mx > val[u]){ puts("NO"); exit(0); }
	long long x = sum - val[u];  val[u] -= x;
	return ;
}


Measured memory_bytes: 14080
#include <stdio.h>
#include <string.h>
int main(void){
  int n,i,t,c,num[10]={1,5,3,3,3,3,3,4,3,4};
  char s[1025];
  char m[10][5]={{""},{' ','.',',','!','?'},{'c','a','b'},{'f','d','e'},{'i','g','h'},{'l','j','k'},{'o','m','n'},{'s','p','q','r'},{'v','t','u'},{'z','w','x','y'}};
  scanf("%d",&n);
  while(n--){
    scanf("%s",s);
    c=t=0;
    for(i=0;i<strlen(s);i++){
      if('1'<=s[i]&&s[i]<='9'){
	t=s[i]-'0';
	do{
	  c++;
	  i++;
	}while(s[i-1]==s[i]);
      }
      if(s[i]=='0'){
        if(t)
	putchar(m[t][c%num[t]]);
	c=t=0;
      }
    }
    puts("");
  }
  return 0;
}

Measured memory_bytes: 584
n, c = map(int, input().split())
r = [[0 for i in range(c)] for j in range(100000)]  # テレビ局の番組表
for dummy in range(n):  # 入力
    s, t, c = map(int, input().split())
    for j in range(s - 1, t):
        r[j][c - 1] = 1  # 放送中なら1
ans = 0
for i in range(100000):
    if sum(r[i]) > ans:
        ans = sum(r[i])  # 同時に放送されている番組の最大数
print(ans)

Measured memory_bytes: 40308
#include <iostream>
#include <string>
//#include <conio.h>
using namespace std;
bool calc(string *strA, string *strB, int n, int m, int diff, int line, int column);
int main() {
	
	int n = 0;
	int m = 0;
	cin >> n;
	cin	>> m;
	string *strA = new string[n];
	string *strB = new string[m];
	for (int i = 0; i < n; i++) {
		cin >> strA[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> strB[i];
	}
	int line = 0;
	int column = 0;
	bool isIncludeA = false; 
	if (n < m) goto Last;
	isIncludeA = calc(strA, strB,n, m, n-m, line,column);
	Last:
	if (isIncludeA) cout << "Yes";
	else cout << "No";
	//line 縦,column 横
	//_getch();
}
bool calc(string *strA, string *strB, int n, int m, int diff, int line, int column) {
	for (int i = 0; i < m; i++) {
		if (strA[i + line].substr(column, m) == strB[i]) {
			if (i == m - 1) {
				return true;
			}
			else { 
				continue;
			}
		}
		else {
			if (diff > column) {
				column++;
			}
			else
			{
				if (diff > line ) {
					line++;
					column = 0;
				}
				else {
					return false;
				}

			}
			//cout << "n " << diff << " line " << line << " column " << column << endl;
			calc(strA, strB, n, m, diff, line, column);
			break;
		}
	}

}



Measured memory_bytes: 888
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<52;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

char s,t;

int main(){
	cin>>s>>t;
	if(s=='H'^t=='D') cout<<'H'<<endl;
	else cout<<'D'<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
using namespace std;

using LL = long long;

const LL MAX_S = 1 << 17;

LL dp[41][MAX_S];
int n, x, y, z;
const LL MOD = 1000000007;

void shift(int& s, int x)
{
	s <<= x;
	s += (1 << (x - 1));
	s &= (MAX_S - 1);
}

int main(void)
{
	cin >> n >> x >> y >> z;
	int no = 0;
	shift(no, x);
	shift(no, y);
	shift(no, z);
	dp[0][0] = 1;
	for (int i = 0; i < n; ++i)
	{
		for (int s = 0; s < MAX_S; ++s)
		{
			for (int p = 1; p <= 10; ++p)
			{
				int t = s;
				shift(t, p);
				if ((t & no) == no)
				{
					dp[i + 1][t] = 0;
				}
				else
				{
					dp[i + 1][t] += dp[i][s];
					dp[i + 1][t] %= MOD;
				}
			}
		}
	}
	LL seven = 1;
	for (int i = 0; i < n; ++i)
	{
		seven *= 10;
		seven %= MOD;
	}
	LL hod = 0;
	for (int s = 0; s < MAX_S; ++s)
	{
		//for (int i = 0; i < dp[n][s]; ++i)cout << static_cast<std::bitset<17>>(s) << endl;
		//if (dp[n][s] > 1)
		//	n = n;
		hod += dp[n][s];
		hod %= MOD;
	}
	LL ans = seven - hod;
	ans += MOD; ans %= MOD;
	cout << ans << endl;
	return 0;
}


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

using namespace std;

typedef long long lint;

int n;
int v[101];

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

    lint sum = 0;
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    sort(v + 1, v + n + 1);

    int rez = 0;
    for(int i = 1; i <= n; i ++)
    {
        sum += v[i];

        if(sum <= x)
        {
            if(i != n)
                rez = i;

            if(i == n && sum == x)
                rez = n;
        }
    }

    cout << rez << "\n";

    return 0;
}


Measured memory_bytes: 256
# ABC081B - Shift only
def main():
    n = int(input())
    A = set(map(int, input().split()))
    ans = 0
    while all(i % 2 == 0 for i in A):
        A = [i // 2 for i in A]
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
i, o, t, j, l, s, z = map(int, input().split())
ans = 0
ans += o
num = 0
if i % 2 == 1:
	num += 1
if j % 2 == 1:
	num += 1
if l % 2 == 1:
	num += 1
if num >= 2 and i * j * l != 0:
	ans += 3
	i -= 1
	j -= 1
	l -= 1
ans += 2 * (i // 2)
ans += 2 * (j // 2)
ans += 2 * (l // 2)

print(ans)

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

int main() {
    int a,b,w;
    cin >> w >> a >> b;
    if(a+w <= b) cout << b-(a+w) << endl;
    else if(b+w <= a) cout << a-(b+w) << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
 
#define int long long
 
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}
 
using namespace std;
 
 
const ll mod=1000000007;

ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
 
typedef pair < int , int > pii ;
typedef pair < long long  , long long > pll ;
 
const int N = 2e5 + 123;
 
int n , m , k , q;
int a[N];
string s;
int up(vector < int > &v , int p){
	int id = upper_bound(all(v) , p) - v.begin();
	return v[id] - p;
}
int lw(vector < int > &v , int p){
	int id = lower_bound(all(v) , p) - v.begin();
	return p - v[id - 1];
}

main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string s;
	cin >> s;
	n = sz(s) + 1;
	s = '>' + s + '<';
	vector < int > v;
	for(int i = 1; i <= n ; i++){
		if(s[i] == '<' && s[i - 1] == '>')
			v.pb(i);
	}
	v.pb(5e5 + 123);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(s[i] == '<' && s[i - 1] == '>')
			continue;
		if(s[i] == '>' && s[i - 1] == '<'){
			ans += max(lw(v , i) , up(v , i));
			continue;
		}
		if(s[i - 1] == '<')
			ans += lw(v,i);
		else ans += up(v,i);
	}
	cout << ans ;
}

Measured memory_bytes: 2736
import math

n=int(input())
info=[]
for i in range(n):
    x,y=map(int,input().split())
    info.append([x,y])
total=0
for i in range(n-1):
    for j in range(i+1,n):
        total+=math.sqrt((info[i][0]-info[j][0])**2+(info[i][1]-info[j][1])**2)
print(total*2/n)

Measured memory_bytes: 3064
import Control.Applicative
import Control.Monad

rInt s = read s :: Int

main  = do
	ss <- (map (map rInt) . map words . lines) <$> getContents
	mapM (mapM putStrLn . rect) $ takeWhile (\(h:(w:_)) -> h/=0 && w/=0) ss 
		where rect (h:(w:_)) = replicate h (replicate w '#') ++ [""]

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


#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define MAXX 500005
#define INF INT_MAX

#define PI   3.14159265358979323846264338327950

#define PB push_back
#define PF push_front
#define F first
#define S second

#define fixx(n) fixed << setprecision(n)

#define ll 	 long long 
const int mod = 1e9 + 7;

int dp[5000];
int main()
{
	FAST;
	int n;
	cin >> n;
	dp[0 ] = 1;
	for(int i = 3; i <= n; i ++){
		for(int j = 3; j <= n; j ++){
			if(i - j >= 0){
				dp[i] = (dp[i] + dp[i-j])%mod;
			}
		}
	}
	cout << dp[n];
	return 0;
}

Measured memory_bytes: 3584
function Main(input) {
	input = input.trim().split(" "); 
	var a = BigInt(input[0], 10);
	var b = BigInt(input[1], 10);
    var c = BigInt(input[2], 10);
    var d = BigInt(input[3], 10);
    
  	var ans = a * c;
  	if(a * d > ans) ans = a * d;
  	if(b * c > ans) ans = b * c;
  	if(b * d > ans) ans = b * d;

    console.log(ans.toString());
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29612
// ABC_169_C

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

#define forn(i, n) for(int i = 0; i < (int)n; ++i)

int main()
{
	ll a;
	double b;
	cin >> a >> b;

	ll tmp = b * (ll)100 + 0.001;

	ll ans = (a * tmp) / (ll)100;

	cout << ans << "\n";

	return 0;
}

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

using namespace std;

#define fRead(x)        freopen(x,"r",stdin)
#define fWrite(x)       freopen (x,"w",stdout)

#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define INF             2e16
#define PI              acos(-1.0)
#define mk              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())


#define FastRead        ios_base::sync_with_stdio(0);cin.tie(nullptr);

const int N = 2000005;
const LL MOD = 1e9 + 7;
LL fac[N];
inline LL BigMod(LL B,LL P,LL M){LL R=1;while(P>0){if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;}return R;}

LL COM(LL a,LL b){return ((fac[a]*BigMod((fac[b]*fac[a-b])%MOD,MOD-2,MOD))%MOD+MOD)%MOD;}

LL solve(LL x,LL y)
{
    LL ans = 0;

    for(int i = 0;i <= x;i++){
        LL temp = COM(i + y + 1,y);
        ans = (ans + temp) % MOD;
    }
    return ans;
}
int main()
{
    fac[0] = 1;
    for(int i = 1;i < N;i++)fac[i] = (fac[i - 1] * i) % MOD;

    LL r1,r2,c1,c2;
    cin >> r1 >> c1 >> r2 >> c2;
//    cout << solve(r2,c2) << endl;
    LL ans = solve(r2,c2) - solve(r2,c1 - 1) - solve(r1 - 1,c2) + solve(r1 - 1,c1 - 1);

    ans = (ans % MOD + MOD) % MOD;
    cout << ans << "\n";

}



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

using namespace std;

int main()
{
  	string S;
  	cin >> S;
  	int n = 0, w = 0, s = 0, e = 0;
  	for(int i = 0; i < S.size(); i++){
		if(S.at(i) == 'N'){
          	n++;
        }
		if(S.at(i) == 'W'){
          	w++;
        }
		if(S.at(i) == 'S'){
			s++;
        }
		if(S.at(i) == 'E'){
 			e++;
        }
    }
  	if(((n == 0 && s == 0) || n*s > 0) && ((w == 0 && e == 0) || w*e > 0)){
      	cout << "Yes";
    }else{
      	cout << "No";
    }
  	return 0;
}

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

int main() {
    int N,i;
    string S;
    cin >> N >> S;

    for(i=0; i<S.size(); i++) {
        S.at(i) += N;
        if(S.at(i) > 90)
            S.at(i) = S.at(i)-26;
    }

    cout << S << endl;
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

typedef tuple<ll, int, int, int> T;

int main(){
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<ll> A(X), B(Y), C(Z);
    rep(i, X) cin >> A[i];
    rep(i, Y) cin >> B[i];
    rep(i, Z) cin >> C[i];

    sort(all(A));
    reverse(all(A));
    sort(all(B));
    reverse(all(B));
    sort(all(C));
    reverse(all(C));

    priority_queue<T> que;
    set<T> added;
    T t(A[0] + B[0] + C[0], 0, 0, 0);
    que.push(t);
    added.insert(t);

    rep(tmp, K){
        T t = que.top();
        que.pop();
        cout << get<0>(t) << endl;
        int i = get<1>(t), j = get<2>(t), k = get<3>(t);
        if(i + 1 < X){
            T u(A[i + 1] + B[j] + C[k], i + 1, j, k);
            if(!added.count(u)){
                que.push(u);
                added.insert(u);
            } 
        } 
        if(j + 1 < Y){
            T u(A[i] + B[j + 1] + C[k], i, j + 1, k);
            if(!added.count(u)){
                que.push(u);
                added.insert(u);
            } 
        } 
        if(k + 1 < Z){
            T u(A[i] + B[j] + C[k + 1], i, j, k + 1);
            if(!added.count(u)){
                que.push(u);
                added.insert(u);
            } 
        } 
    }
}

Measured memory_bytes: 896
n = gets.chomp.to_i
a,b = gets.chomp.split.map(&:to_i)
p = gets.chomp.split.map(&:to_i).sort
p_1,p_2,p_3 = [],[],[]
while p.size != 0
if p[0] <= a
  p_1 << p[0]
  p.shift
elsif p[0] > a && p[0] <= b
    p_2 << p[0]
    p.shift
elsif p[0] >= b
    p_3 << p[0]
    p.shift
end
end
puts [p_1.size,p_2.size,p_3.size].min

Measured memory_bytes: 1788
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.append(x)
a.sort()
d = set()
for i in range(n):
  d.add(a[i + 1] - a[i])
d = list(d)
ans = gcd_list(d)
print(ans)

Measured memory_bytes: 20428
def main():
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    arr = list(map(int, input().split()))
    
    tot = sum(arr) >> 1
    for i in range(0, n - 2, 2):
        tot -= arr[i]
    
    dams = [0] * n
    dams[n - 1] = 2 * tot
    
    for i in range(n - 2, -1, -1):
        dams[i] = 2 * arr[i] - dams[i + 1]
    
    print(*dams)
    
    return 0

main()

Measured memory_bytes: 14108
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(void)
{
	int a,s,d,f,g,h,i,j;
	scanf("%d",&a);
	for(i=0;i<a;i++){
		scanf("%d %d",&s,&d);
		f=s%d;
		if(f==0) f=d;
		printf("%d\n",f);
	}
	return 0;
}

Measured memory_bytes: 2744
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class AAtCoderContestScheduling {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int d; cin >> d;
      rep(i, d) {
        cout << 2 << '\n';
      }
    }
};

signed main() {
  AAtCoderContestScheduling solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int main() {
    int countN, n[10000], countQ, t[10000];

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

    cin >> countQ;
    for (int i = 0; i < countQ; i++) {
        cin >> t[i];
    }

    int match = 0;
    for (int i = 0; i < countQ; i++) {
        n[countN] = t[i];
        int key = 0;
        while (n[key] != t[i]) key++;
        if (key != countN) match++;
    }

    cout << match << endl;

    /***
    int match = 0;
    for (int i = 0; i < countN; i++) {
        for (int j = 0; j < countQ; j++) {
            if (n[i] == t[j]) {
            cout << n[i] << " " << t[j] << endl;
                match++;
                break;
            }
        }
    }

    cout << match << endl;
    ****/

}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<28
#define MAX_V 500
struct edge { int to,cap,rev; };

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

int add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
  return G[from].size()-1;
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int i=0;i<G[v].size();i++){
      edge &e = G[v][i];
      if(e.cap>0&&level[e.to]<0){
	level[e.to]=level[v]+1;
	que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t) return f;
  for(int &i=iter[v];i<G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  for(;;){
    bfs(s);
    if(level[t]<0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}
typedef pair<int,int> P;
int main(){
  int n,m,i,j,k,s,t;
  vector<P> v;
  vector<int> ans;
  cin>>n>>m;
  for(i=0;i<m;i++) {
    cin>>s>>t;
    add_edge(s,t,1);
    v.push_back(P(t,add_edge(t,s,1)));
  }
  cin>>s>>t;
  cout << max_flow(s,t) << endl;
  for(i=0;i<m;i++){
    if(G[v[i].first][v[i].second].cap) continue;
    ans.push_back(i+1);
  }
  cout<<ans.size()<<endl;
  for(i=0;i<ans.size();i++) cout<<ans[i]<<endl;
  return 0;
}

Measured memory_bytes: 3276
#include <cstdio>
#include <algorithm>
using namespace std;

int pi[233333],pp[233333][2],pc[233333];

int sou(int k,int f,int c)
{
	int i=pi[k],p=0,mmax=0;
	while(i!=0)
	{
		if(pp[i][0]!=f)
		{
			if((p+1)==c) p++; pc[(i+1)/2]=++p;
			mmax=max(mmax,sou(pp[i][0],k,p));
		}
		i=pp[i][1];
	}
	return max(mmax,p);
}

int main()
{
	int n; scanf("%d",&n);
	for(int i=1,j=0; i<n; i++)
	{
		int a,b; scanf("%d%d",&a,&b);
		pp[++j][0]=b; pp[j][1]=pi[a]; pi[a]=j;
		pp[++j][0]=a; pp[j][1]=pi[b]; pi[b]=j;
	}
	printf("%d\n",sou(1,0,-1));
	for(int i=1; i<n; i++) printf("%d\n",pc[i]);
	return 0;
}


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

int main(){

  int n, q;
  int s[100001] = {};
  int t, cnt = 0;
  int mid, right, left;

  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];
  sort(s, s+n);
  cin >> q;
  for(int i = 0; i < q; i++){
    cin >> t;
    left = 0;
    right = n;
    while(left < right){
      mid = (left + right) / 2;
      if(s[mid] == t){
        cnt++;
        break;
      }else if(t > s[mid]){
        left = mid + 1;
      }else if(t < s[mid]){
        right = mid;
      }
    }
  }
  cout << cnt << endl;
  return 0;
}


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

int main()
{
    int n;
    long long a[2];
    bool checker2 = false;
    a[0] = 0;
    a[1] = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        long long in;
        cin >> in;
        if((in % 4)== 0){
            a[0]++;
        }
        if((in % 2)== 1){
            a[1]++;
        }
        if((in % 4) == 2){
            checker2 = true;
        }
    }
    if(a[0] >= a[1]){
        cout << "Yes" << endl;
    }
    else if((a[0] == (a[1] - 1)) && (checker2 == false)){
        cout << "Yes" << endl;
        }
    else {
        cout << "No" << endl;
    }
    return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
   ll n,m,c; cin>>n>>m>>c;
   vector<ll> b(m);
   vector<vector<ll>> a(n,vector<ll>(m));
   rep(i,m) cin>>b[i];
   rep(i,n)rep(j,m) cin>>a[i][j];
   ll ans=0;
   rep(i,n){
       ll sum=0;
        rep(j,m){
            sum+=a[i][j]*b[j];
        }
        if(sum+c>0) ++ans;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3616
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second > b.second; }

int main() {
    string s[]={"Sunny","Cloudy","Rainy"};
    string a;cin>>a;
    rep(i,3){
        if(s[i]==a)cout<<s[(i+1)%3]<<endl;
    }
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

using State = string::const_iterator;

int expr(State &);
int term(State &);
int factor(State &);
int number(State &);

int expr(State &begin) {
  int val = term(begin);
  forever {
    if (*begin == '+') {
      begin++;
      val += term(begin);
    } else if (*begin == '-') {
      begin++;
      val -= term(begin);
    } else {
      break;
    }
  }
  return val;
}

int term(State &begin) {
  int val = factor(begin);
  forever {
    if (*begin == '*') {
      begin++;
      val *= factor(begin);
    } else if (*begin == '/') {
      begin++;
      val /= factor(begin);
    } else {
      break;
    }
  }
  return val;
}

int factor(State &begin) {
  if (*begin == '(') {
    begin++;
    int val = expr(begin);
    begin++;
    return val;
  }
  return number(begin);
}

int number(State &begin) {
  int val = 0;
  while (isdigit(*begin)) {
    val *= 10;
    val += *begin - '0';
    begin++;
  }
  return val;
}

main {
  int n;
  cin >> n;
  cin.ignore();
  while (n--) {
    string s;
    getline(cin, s);
    s.pop_back();
    State begin = s.begin();
    cout << expr(begin) << endl;
  }
}

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

using namespace std;

int N, L;
vector<int> vec;

void solve();
int taste(int i);

// i はindex
int taste(int i) {
  return L + i;
}

int main() {
  cin >> N >> L;
  for (int i = 0; i < N; i++) {
    vec.push_back(taste(i));
  }
  solve();
}

void solve() {
  // 絶対値が少なくなるようにするため、味が0に近いものを選ぶ
  int smallest = vec[0];
  for (auto i : vec) {
    if (i * i < smallest * smallest) {
      smallest = i;
    }
  }
  // 結果の味の総和を求める
  int total = 0;
  for (auto i : vec) {
    if (i != smallest) {
      total += i;
    }
  }
  cout << total << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<string.h>
char a[7][5]={ "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
int b[7]={7,6,5,4,3,2,1};
char d[4];
int main()
{
	scanf("%s",d);
	for(int i=0;i<7;i++)
	if(strcmp(d,a[i])==0)
	{
	printf("%d\n",b[i]);
	}
		return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0017
{
    public class Program

    {
        public static void Main(string[] args)
        {
            List<int> ans = new List<int>();
            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                List<double> input = Console.ReadLine().Split(' ').Select(double.Parse).ToList();
                double xa = input[0];  double ya = input[1];  double ra = input[2];
                double xb = input[3];  double yb = input[4];  double rb = input[5];
                double r = Math.Sqrt(Math.Pow(xb -xa, 2) + Math.Pow(yb - ya, 2));
                if (ra + rb < r)
                {
                    ans.Add(0);
                }
                else if (rb + r < ra)
                {
                    ans.Add(2);
                }
                else if (ra + r < rb)
                {
                    ans.Add(-2);
                }
                else
                {
                    ans.Add(1);
                }
            }

            foreach (int item in ans)
                Console.WriteLine(item);     
        }
    }

}


Measured memory_bytes: 18156
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define END(x) do{cout<<(x)<<endl;exit(0);}while(0)
#define debug(x) do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<#x<<': "';\
for(auto&e: x)cerr<<e<<" ";cerr<<"\n";}while(0)
#define exp2(x)  (1LL<<(x))

using namespace std;
using ll=long long;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  int A, P; cin >> A >> P;
  cout << (A*3 + P)/2 << endl;
}


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

#define deb(x) cout << #x << " " << x << "\n";
#define fo(i, n) for(i=0; i<n; i++)
#define Fo(i, k, n) for(i=k; i<n; i++)
#define endl "\n"
#define ll long long
#define vi vector<int>

// memset(arr, value, size);

int main() {
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t, i, temp = 0, a;
	cin >> t;
	Fo(i, 1, t + 1) {
		cin >> a;
		if (i % 2 && a % 2) temp++;
	}
	cout << temp;

	return 0;
}

Measured memory_bytes: 3648
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	n := readInt()

	for n > 0 {
		if n%4 == 0 {
			println("Yes")
			return
		}
		if n%7 == 0 {
			println("Yes")
			return
		}
		n -= 4
	}
	println("No")
}


Measured memory_bytes: 640
#define KAKUSUKO
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

ll a, b, x;

int main() {
    cin >> a >> b >> x;

    double ans = 0;
    if (x*2 >= a*a*b) {
        double t = (2.0*b/a) - (2.0*x/a/a/a);
        ans = atan(t) * 180.0 / M_PI;
    } else {
        double t = 2.0*x/b/b/a;
        ans = (M_PI/2.0 - atan(t)) * 180.0 / M_PI;
    }

    printf("%.10lf", ans);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main(){ 
  int N,D;
  cin >> N >> D;
  
  if(N % (2*D +1) == 0) cout << N / (2*D +1) << endl;
  else cout << N / (2*D +1) + 1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;

int a[N];

int main()
{
	int n;
	cin >> n;
	for (int i=0; i<n; i++)
		cin >> a[i];
	n = unique(a, a+n) - a;
	int cnt = 0;
	for (int i=1; i+1<n; i++)
	{
		if (a[i] > a[i-1] && a[i] > a[i+1])
			cnt++, i++;
		else
		if (a[i] < a[i-1] && a[i] < a[i+1])
			cnt++, i++;	
	}
	if (cnt != 0)
		cout << cnt + 1 << "\n";
	else
		cout << 1 << "\n";
	return 0;
}

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000001
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  if((b-a) < (2*k)){
    FOR(i, a, b+1) cout << i << endl;
  }
  else{
    FOR(i, a, a+k) cout << i << endl;
    FOR(i, b-k+1, b+1) cout << i << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(2e5+5); // TODO : change value as per problem
const ll MOD = 1e9+7;
vector<int> adj[N],adj2[N];
bool vis[N],vis2[N];
int col[N],col2[N];
int comp,comp2;
void dfs(int u){
	vis[u] = true;
	col[u] = comp;
	for(auto v:adj[u]){
		if(vis[v] == false){
			dfs(v);
		}
	}
}

void dfs2(int u){
	vis2[u] = true;
	col2[u] = comp2;
	for(auto v:adj2[u]){
		if(vis2[v] == false){
			dfs2(v);
		}
	}
}
void solve(){
	int n,k,l;
	cin >> n >> k >> l;
	for(int i =1;i<=k;i++){
		int u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i =1;i<=n;i++){
		if(!vis[i]){
			comp++;
			dfs(i);
		}
	}
	for(int i = 1;i<=l;i++){
		int u,v;
		cin >> u >> v;
		adj2[u].pb(v);
		adj2[v].pb(u);
	}
	for(int i =1;i<=n;i++){
		if(!vis2[i]){
			comp2++;
			dfs2(i);
		}
	}
	map<pll,int> wow;
	for(int i =1;i<=n;i++){
		wow[mp(col[i],col2[i])]++;
	}
	for(int i=1;i<=n;i++){
		cout << wow[mp(col[i],col2[i])] << " ";
	}
	cout << endl;

}
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

Measured memory_bytes: 33676
def euclid(a,b):
    if b == 0:
        return a 
    else:
        return euclid(b,a%b)
n,x = map(int,input().split())
cit = list(map(lambda i:int(i)-x,input().split()))

d = cit[0]
#cit-xの最大公約数
for i in range(n-1):
    d = euclid(d,cit[i+1])
    if d == 1:
        break
print(abs(d))


Measured memory_bytes: 14252
n=int(input())
a=[int(input())for _ in[0]*n]
for i in range(4):
 for j in range(n-1,i,-1):
  if a[i]>a[j]:a[i],a[j]=a[j],a[i]
p=[]
for i in range(3):
 for d in a[i+1:4]:
  c=a[i]
  p+=[int(f'{c}{d}'),int(f'{d}{c}')]
print(sorted(p)[2])


Measured memory_bytes: 5984
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vll vector<long long>
#define pll pair<long long, long long>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1e18
 

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;

// change N 
const ll N = 1e6 + 6;
ll lo[4 * N + 1], hi[4 * N + 1], delta[4 * N + 1], mini[4 * N + 1];

// change update and rmq according to question

void buildSeg(ll node, ll l, ll r)
{
    lo[node] = l;
    hi[node] = r;
    if (l == r)
    {
        return;
    }
    ll mid = l + (r - l) / 2;
    buildSeg(2 * node + 1, l, mid);
    buildSeg(2 * node + 2, mid + 1, r);
}

void prop(ll i)
{
    delta[2 * i + 1] += delta[i];
    delta[2 * i + 2] += delta[i];
    delta[i] = 0;
}

void update(ll i)
{
    mini[i] = max(mini[2 * i + 1] + delta[2 * i + 1], mini[2 * i + 2] + delta[2 * i + 2]);
}

void increment(ll i, ll l, ll r, ll val)
{
    if (r < lo[i] || l > hi[i])
    {
        return;
    }
    if (l <= lo[i] && r >= hi[i])
    {
        delta[i] = val;
        return;
    }
    prop(i);

    increment(2 * i + 1, l, r, val);
    increment(2 * i + 2, l, r, val);
    update(i);
}

ll rmq(ll i, ll l, ll r)
{
    if (r < lo[i] || l > hi[i])
    {
        return -1;
    }
    if (l <= lo[i] && r >= hi[i])
    {
        return mini[i] + delta[i];
    }
    prop(i);
    ll lefmin = rmq(2 * i + 1, l, r);
    ll rigmin = rmq(2 * i + 2, l, r);
    update(i);
    return max(lefmin, rigmin);
}

void solve()
{
    ll n,k;
    cin>>n>>k;
    ll i,j;
    ll a[n+1];
    buildSeg(1,0,N+5);
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    ll dp[n+1];
    clr(dp);
    dp[0]=0;
    for(i=0;i<=300003;i++)
    {
        increment(1,i,i,0ll);
    }
    // cout<<rmq(1,0,0)<<"\n";
    for(i=1;i<=n;i++)
    {
        // dp[i] = max(a[i]-k to a[i]+k)
        ll l = max(0ll,a[i]-k);
        ll r = min(300003ll,a[i]+k);
        ll no = rmq(1,l,r);
        // cout<<a[i]<<" "<<l<<" "<<r<<" "<<no<<"\n";
        dp[i]=no+1;
        ll no2 = rmq(1,a[i],a[i]);
        if(dp[i]>no2){
        increment(1,a[i],a[i],dp[i]);
        }
        dp[i]=max(dp[i],dp[i-1]);
    }
    cout<<dp[n]<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 48660
#include <iostream>
#include <algorithm>
#include <atomic>
#include <thread>
#include <mutex>
#include <string>
#include <string.h>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <limits.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define ll long long
#define P std::pair<int,int> 
#define INF LLONG_MAX/3
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
int q;
list<int> l;
signed main() {
	cin >> q;
	auto ite = l.end();
	rep(i, q) {
		int a;
		cin >> a;
		if (!a) {
			int x;
			cin >> x;
			ite = l.insert(ite, x);
		}
		else if (a == 1) {
			int d;
			cin >> d;
			rep(j, abs(d)) {
				if (d > 0)ite++;
				else ite--;
			}
		}
		else {
			ite = l.erase(ite);
		}
	}
	for (int i : l)cout << i << endl;
	getchar();
	getchar();
	return 0;
}


Measured memory_bytes: 18576
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	bool flg = false;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());

	for (int idx = 0; idx < N -1; idx++) {
		if (A[idx] == A[idx + 1]) {
			flg = true;
			idx = N;
		}
	}
	if (flg) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
}


Measured memory_bytes: 1024
n, m = map(int, input().split())

d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append(a)
    d.append(b)
d = sorted(d)
for i in range(1, n + 1):
  count = 0
  for j in range(len(d)):
    if d[j] == i:
      count += 1
  print(count)
  



Measured memory_bytes: 3060
#include<stdio.h>
int judge(int);
int cont=0;
int main()
{
  int a,d,n,i,m=0;
  int an[1000];
  while(1){
    scanf("%d%d%d",&a,&d,&n);
    if(a==0 && d==0&&n==0)break;
    for(i=a;i<10000000;i+=d){
      cont+=judge(i);
      if(cont==n){
	an[m]=i;
        m++;
        break;
      }
    }
    cont=0;
  }
  for(i=0;i<m;i++){
    printf("%d\n",an[i]);
  }
  return 0;
}

int judge(int n)
{
  int i;
  if(n<2)return 0;
  else if(n==2)return 1;
  if(n%2==0)return 0;
  for(i=3;i<=n/i;i+=2){
    if(n%i==0)return 0;
  }
  return 1;
}

Measured memory_bytes: 604
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10**18
mod = 10**9+7

n = list(map(int, list(input())))
def getAns(now , giri, t,f,s):
    if now == len(n):
        if t and f and s:
            return 1
        else:
            return 0
    tmp = n[now]
    ret = 0
    if giri:
        if tmp > 7:
            ret += getAns(now+1, False, t, f, True)
            ret += getAns(now+1, False, t, True, s)
            ret += getAns(now+1, False, True, f, s)
        elif tmp == 7:
            ret += getAns(now+1, giri, t, f, True)
            ret += getAns(now+1, False, True, f, s)
            ret += getAns(now+1, False, t, True, s)
        elif tmp > 5:
            ret += getAns(now + 1, False, True, f, s)
            ret += getAns(now + 1, False, t, True, s)
        elif tmp == 5:
            ret += getAns(now + 1, False, True, f, s)
            ret += getAns(now + 1, giri, t, True, s)
        elif tmp > 3:
            ret += getAns(now + 1, False, True, f, s)
        elif tmp == 3:
            ret += getAns(now + 1, giri, True, f, s)
    else:
        ret+=getAns(now+1, giri, t,f,True)
        ret+=getAns(now+1, giri, t,True,s)
        ret+=getAns(now+1, giri, True, f, s)
    return ret

ans = 0
for i in range(len(n)-1):
    ans += getAns(i+1,False,False,False,False)
print(ans + getAns(0,True,False,False,False))

Measured memory_bytes: 45416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    set<ll> st;
    rep(i, 0, 3){
        ll a;
        cin >> a;
        st.insert(a);
    }
    cout << st.size() << endl;
    return 0;
}

Measured memory_bytes: 3604
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

ll a[100002];
int main()
{
   ll n;
   cin>>n;

   for1(i,n){
   ll b;
   cin>>b;
   a[b]=i;
   }

   for1(i,n)
   cout<<a[i]<<" ";
}


Measured memory_bytes: 1536
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int ans = 1;
		while (true) {
			if (ans * 2 > n) {
				break;
			}
			ans *= 2;
		}

		System.out.println(ans);

		sc.close();
	}
}

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

int main(){
  int N;
  cin >> N;
  vector<pair<int, int>> sch;
  int tmp_a,tmp_b;
  for(int i=0; i<N; i++){
    cin >> tmp_a >> tmp_b;
    sch.push_back(make_pair(tmp_b,tmp_a));
  }

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

  uint64_t sum=0;
  bool can = true;
  for(pair<int,int> t : sch){
    sum += t.second;
    if(sum > t.first){
      can = false;
      break;
    }
  }
  
  if(can){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 2420