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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

ll N, M, Q;
ll maxi;
vector<tuple<ll, ll, ll, ll>> Queries;
vector<ll> A;

void dfs(ll index) {
    if(index == N + 1) {
        ll count = 0;
        iter(i, Queries) {
            if(A[get<1>(i)] - A[get<0>(i)] == get<2>(i)) count += get<3>(i);
        }
        maxi = max(maxi, count);
        return;
    }
    repi2(i, A[index], M) {
        A[index + 1] = i;
        dfs(index + 1);
    }
}

int main(void) {
    cin >> N >> M >> Q;
    A.resize(N + 2, 1);
    rep(i, Q) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        Queries.emplace_back(a, b, c, d);
    }
    dfs(0);
    cout << maxi << endl;
    return 0;
}


Measured memory_bytes: 3640
/*
このコード、と～おれ!
Be accepted!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define p push
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

const int INF = 1073741823;
const int MINF = -1073741823;
const ll LINF = ll(4661686018427387903);
const ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/


int main() {

	int n, a, x, y;
	scanf("%d", &n);
	vector<vector<pair<int, int>>> aa(n);
	rep(i, n) {
		scanf("%d", &a);
		rep(j, a) {
			scanf("%d%d", &x, &y);
			aa[i].pb(make_pair(x - 1, y));
		}
	}
	int ans = 0, anstmp = 0;
	vector<int> ishonest(n);
	for(ll i = 0; i < (1 << n); ++i) {
		fill(all(ishonest), -1);
		anstmp = 0;
		rep(j, n) {
			if (i & (1 << j)) {//jth peaple is honest
				if (ishonest[j] == -1) {
					ishonest[j] = 1;
					++anstmp;
				}
				else if (ishonest[j] != 1) {
					anstmp = MINF;
				}
				for (auto ab : aa[j]) {
					if (ishonest[ab.first] == -1) {
						if ((1 << ab.first) & i) {
							if (ab.second == 1) {
								ishonest[ab.first] = ab.second;
								anstmp += ab.second;
							}
							else {
								anstmp = MINF;
							}
						}
						else {
							if (ab.second == 0) {
								ishonest[ab.first] = ab.second;
								anstmp += ab.second;
							}
							else {
								anstmp = MINF;
							}
						}
					}
					else {
						if (ishonest[ab.first] != ab.second)anstmp = MINF;
					}
				}
			}
		}
		//printf("%d\n", anstmp);
		ans = max(ans, anstmp);
	}

	printf("%d\n", ans);

	Please AC;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;
struct UnionFind{
	vector<int>par,size;
	int find(int x){
		return (par[x]==x?x:par[x]=find(par[x]));
	}
	bool merge(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return false;
		if(size[x]>size[y])swap(x,y);
		par[x]=y;
		size[y]+=size[x];
		return true;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	UnionFind(int x):size(x,1),par(x){
		iota(all(par),0);
	}
};
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int N,Q;cin>>N>>Q;
	UnionFind uf(N);
	while(Q--){
		int t,u,v;cin>>t>>u>>v;
		if(!t)uf.merge(u,v);
		else cout<<uf.same(u,v)<<"\n";
	}
}

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

int main()
{
    string str;
    int n,maxi,x;

    while(cin>>n)
    {
        x=maxi=0;

        cin>>str;

        for(int i=0; i<n; i++)
        {
            if(str[i]=='I')
            {
                x++;

                if(x>maxi)
                    maxi=x;
            }

            if(str[i]=='D')
            {
                x--;

                if(x>maxi)
                    maxi=x;
            }
        }

        cout<<maxi<<endl;
    }

    return 0;
}


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


int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int n, m;
	cin >> n >> m;

	string s3;
	cin >> s3;

	map<string, int> map;

	map[s1] = n;
	map[s2] = m;

	map[s3]--;

	cout << map[s1] << " " << map[s2];
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	//f©Ç¤©ð»Ê·éÖ
	private boolean isPrime(int n){
		for(int i=2; i * i <= n; i++){
			if(n % i == 0){
				return false;
			}
		}
		return true;
	}

	public void doIt(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			//næèºÌfð©é
			for(int i = n - 1;; i--){
				if(isPrime(i)){
					System.out.print(i +" ");
					break;
				}
			}
			//næèãÌfðÝé
			for(int i = n + 1;; i++){
				if(isPrime(i)){
					System.out.println(i);
					break;
				}
			}
		}
		
	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();

	}

}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
#include <vector>
#include <algorithm>
#define ll long long
#define mod 1000000007
#define test int t; cin>>t; while(t--)
#define f for(int i=0;i<n;i++)
#define f1 for(int i=1;i<n-1;i++)
#define read(x) ll x; cin>>x;
#define TIME  cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";

using namespace std;
/*ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b);}
int combi(int n, int k)
{
    int C[k+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j-1];
    }
    return C[k];
}
int factorial(int n)
{
    return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
}
ll power(ll x,ll n)
{
    if(n==0) return 1;
    if(n&1) return x*power(x,n/2)*power(x,n/2);
    else
        return power(x,n/2)*power(x,n/2);
}*/
/*int gcd(int a, int b){
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int lcm(int a, int b)
{
    return (a*b)/gcd(a, b);
}*/
int main() {

   ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
   // static const auto _ = []() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); return 0; }();

    ll n,d,k=0; cin>>n>>d;
    vector<pair<ll,ll>> v;
    while(n--)
    {
        ll x,y; cin>>x>>y;
        v.push_back(make_pair(x,y));
    }
    for(auto x:v)
    {
        double c=sqrt(x.first*x.first + x.second*x.second);
        if(c<=d) k++;
    }
cout<<k<<endl;
//TIME
}

Measured memory_bytes: 7440
import java.util.Scanner;
import java.util.Stack;

public class Main{
    //problem from izu
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String next = in.nextLine();
        String[] str = next.split(" ");
        //System.out.println(str[1]);
        Stack<Integer> stack = new Stack<>();
        int length = str.length;
        for(int i = 0; i<length; i++){
            if(str[i].charAt(0)=='+' || str[i].charAt(0)=='-' || str[i].charAt(0)=='*'){
                int a = stack.pop();
                int b = stack.pop();
                if(str[i].charAt(0)=='+'){
                    stack.push(a+b);
                } else if(str[i].charAt(0)=='-'){
                    stack.push(b-a);
                } else if(str[i].charAt(0)=='*'){
                    stack.push(a*b);
                }
            }
            else {
                int temp = 0;
                for(int k = 0; k<str[i].length(); k++){
                    temp*=10;
                    temp+=(str[i].charAt(k) - '0');
                }
                stack.push(temp);
                //System.out.println(temp);
            }
        }
        System.out.println(stack.pop());
        
    }

}



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

long long N, M;
string S;
string T;

long long gcd (long long a, long long b)
{
    if (b==0)
    {
        return a;
    }

    else
    {
        return gcd(b, a%b);
    }
}

long long lcm (long long a, long long b)
{
    return (a*b)/gcd(a,b);
}

int main()
{
    cin>>N>>M;
    cin>>S;
    cin>>T;
    
    long long L=lcm(N,M);
    long long g=gcd(N,M);

    for (int i=0; i<g; i++)
    {
        if (S[i*N/g]!=T[i*M/g])
        {
            cout<<"-1"<<endl;
            return 0;
        }
    }

    cout<<L<<endl;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#define endl  "\n"
#define ll long long
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6)
    {
        if ((n % i == 0) || (n % (i + 2) == 0))
            return false;
    }
    return true;
}
int32_t main()
{
	int n;
	cin >> n;
	
	int x=n%500;
	int cnt=0;
	cnt+=(n/500)*1000;
	
	cnt+=(x/5)*5;
	cout << cnt;
}


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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<int, int> mp;
    int N; cin >> N;
    rep(i, N){
        int k; cin >> k;
        mp[k]++;
    }
    int ans = 0;
    for(auto x : mp){
        if(x.second % 2 == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
 
#define int             long long
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int, int>
#define mk(arr,n,type)  type *arr=new type[n];
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqmax           priority_queue<int>
#define pqmin           priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define trailzrobits(x) __builtin_ctzll(x)
#define leadzrobits(x)  __builtin_clzll(x)
#define paritybits(x)   __builtin_parityll(x)
#define gcd             __gcd
#define lcm(x, y)       (x * y) / gcd(x, y)
#define mod             1000000007
#define endl            '\n'
#define PI              3.14159265358979323846
#define inf             1e18
#define sp(x,y)         fixed<<setprecision(y)<<x

void __print(int x) {cout<<x;}
void __print(float x){cout<<x;}
void __print(double x){cout<<x;}
void __print(ld x) {cout<<x;}
void __print(char x){cout <<'\''<<x<<'\'';}
void __print(const char *x){cout <<'\"' <<x<<'\"';}
void __print(const string &x) {cout<<'\"'<<x<<'\"';}
void __print(bool x) {cout<<(x?"true":"false");}
template<typename T,typename V>     void __print(const pair<T,V> &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
template<typename T>                void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}void _print() {cout << "]\n";}
template <typename T,typename... V> void _print(T t, V... v) {__print(t);if(sizeof...(v))cout<<", ";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_print(x)
#else 
#define dbg(x...)
#endif

int power(int x, int y, int p = mod){
    int res = 1;
    x %= p;
    while(y > 0){
        if(y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res; 
}

int inv(int x, int p = mod){
    return power(x, p - 2) % p;
}

const int N = 1e6 + 6;

struct activity{
    int a, b, c;
};
 
int32_t main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--){
       
        int n; cin>>n;
        mk(arr, n+1, activity);
        for(int i=1; i<=n; i++)
            cin>>arr[i].a>>arr[i].b>>arr[i].c;

        int dp[n+1][3];
        dp[1][0] = arr[1].a;
        dp[1][1] = arr[1].b;
        dp[1][2] = arr[1].c;

        for(int i=2; i<=n; i++){
            dp[i][0] = arr[i].a + max(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = arr[i].b + max(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = arr[i].c + max(dp[i-1][0], dp[i-1][1]);
        }

        int ans = max({dp[n][0], dp[n][1], dp[n][2]});
        cout<<ans;
    }

    return 0;

}

Measured memory_bytes: 4992
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;




int main() {

ll N,K;
cin>>N>>K;
cout<<min(N%K,K-N%K)<<endl;
return 0;
}

Measured memory_bytes: 3600
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int i=1;
  while(++i<=n){
    int x=i;
    if(x%3==0){
      cout << " " << i;
      continue;
    }
    while(x){
      if(x%10==3){
    cout << " " << i;
    break;
      }
      x/=10;
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

vector<int> divisor(int n){
    vector<int> res;
    for(int i = 1; i * i <= n; i++){
    if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    vector<int> da = divisor(a);
    vector<int> d;
    rep(i, 0, da.size()){
        if(b % da[i] == 0){
            d.push_back(da[i]);
        }
    }
    sort(d.begin(), d.end());
    int ans = 0;
    vector<bool> f(d.size(), true);
    rep(i, 1, d.size()){
        if(f[i]){
            ans++;
            rep(j, i + 1, d.size()){
                if(d[j] % d[i] == 0){
                    f[j] = false;
                }
            }
        }
    } 
    cout << ans + 1 << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int a[55], b[55];
int n, m;
bool graph[55][55], visited[55];
void dfs(int x) {
	if(visited[x]) {
		return;
	}
	visited[x] = true;
	for(int i = 0; i < n; i++) {
		if(graph[x][i]) {
			dfs(i);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
	}
	int ans = 0;
	for(int i = 0; i < m; i++) {
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
		fill(visited, visited + 55, false);
		dfs(0);
		for(int i = 0; i < n; i++) {
			if(!visited[i]) {
				ans++;
				break;
			}
		}
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
	}
	cout << ans << endl;
	return 0;	
}


Measured memory_bytes: 892
using System;
using System.Collections.Generic;
using System.Linq;
using static AtCoder.Io;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var hw = ReadIntArray();
            var h = hw[0];
            for (int i = 0; i < h; i++)
            {
                var c = ReadString();
                Console.WriteLine(c);
                Console.WriteLine(c);
            }
        }
    }

    public static class Io
    {
        public static string ReadString() => Console.ReadLine();
        public static string[] ReadStringArray() => ReadString().Split(' ');
        public static int ReadInt() => int.Parse(ReadString());
        public static long ReadLong() => long.Parse(ReadString());
        public static int[] ReadIntArray() => ReadStringArray().ParseInt().ToArray();
        public static long[] ReadLongArray() => ReadStringArray().ParseLong().ToArray();
        public static IEnumerable<int> ParseInt(this IEnumerable<string> source) => source.Select(int.Parse);
        public static IEnumerable<long> ParseLong(this IEnumerable<string> source) => source.Select(long.Parse);
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define FOR(i, m, n) for(int i = (int)m; i < (int)n; i++)
#define REP(i, n) FOR(i, 0, n)
using ll = long long;
ll mod = 1000000007;
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(char a = '0'; a <= '9'; a++) {
        for(char b = '0'; b <= '9'; b++) {
            for(char c = '0'; c <= '9'; c++) {
                int pos = 0;
                REP(i, n) {
                    if(pos == 0 && s[i] == a) pos++;
                    else if(pos == 1 && s[i] == b) pos++;
                    else if(pos == 2 && s[i] == c) pos++;
                }
                if(pos == 3) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define OUT(s) cout << s << "\n";

using namespace std;
// https://atcoder.jp/contests/abc161

int X,Y,Z,T;

void Main()
{
    T = X;
    X = Y;
    Y = T;

    T = X;
    X = Z;
    Z = T;
    string s = to_string(X) + " " + to_string(Y) + " " + to_string(Z);
    OUT(s);
}

int main()
{
	cin.tie(0);
    ios::sync_with_stdio(false);
	// cout << fixed << setprecision(15);
    cin >> X >> Y >> Z;
	Main();
    return 0;
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)**2
k = 0
for i in range(a[0], a[-1]+1):
  if (N*i-sum(a))**2 < s:
    s = (N*i-sum(a))**2
    k = i
    
l = 0    
for j in range(N):
  l = l + (k-a[j])**2
      
print(l)

Measured memory_bytes: 3064
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
aa = inpl()
ed = set()
dd = defaultdict(int)

for a in aa:
	ed.add(a)
	dd[a] += 1

CNTs = []
for i in ed:
	CNTs.append(dd[i])

CNTs.sort()
L = len(CNTs)
ans = 0
for i in range(L-K):
	ans += CNTs[i]

print(ans)


Measured memory_bytes: 41424
#include<bits/stdc++.h>
using namespace std;
vector<int> edges[100001];
int visited[100001];
void dfs(long long int v){
	for(int i=0;i<edges[v].size();i++){
		if(visited[edges[v][i]]!=1){
			visited[edges[v][i]]=1;
			dfs(edges[v][i]);
		}
	}
}
int main(){
	long long int n,m, a, b, ct=0;
	cin>>n>>m;
	for(int i=0;i<100001;i++){
		visited[i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(!visited[i]){
			ct++;
			visited[i]=1;
			dfs(i);
		}
	}
	cout<<ct-1;
	
}

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

template <typename Arg1>
void pn(Arg1&& arg1)
{ cout<<arg1<<"\n";}
template <typename Arg1, typename... Args>
void pn(Arg1&& arg1, Args&&... args)
{ cout<<arg1<<"\n"; pn(args...); }

template <typename Arg1>
void ps(Arg1&& arg1)
{ cout<<arg1<<" ";}
template <typename Arg1, typename... Args>
void ps(Arg1&& arg1, Args&&... args)
{ cout<<arg1<<" "; ps(args...); }

template <typename Arg1>
void pvs(Arg1&& arg1, ll n)
{ for(ll i=0;i<n;i++)ps(arg1[i]); }
template <typename Arg1>
void pvn(Arg1&& arg1, ll n)
{ for(ll i=0;i<n;i++)pn(arg1[i]); }

template <typename Arg1>
void bug(Arg1&& arg1)
{ cout<<"->"<<arg1<<endl; }

ll lcm(ll a,ll b) 
{ return (a*b)/__gcd(a,b); }

ll mulmod(ll a,ll b,ll mod) 
{ ll res=0; a=a%mod; 
    while(b>0)
    { if(b%2==1) res=(res+a)%mod; 
      a=(a*2)%mod; b/=2; }
    return res % mod; } 

ll powmod(ll x,ll y,ll p) 
{ ll res=1; x=x%p;
    while(y>0) 
    { if (y&1) res=(res*x)%p; 
      y=y>>1; x=(x*x)%p; } 
    return res; } 

ll modInverse(ll n, ll p) 
{ return powmod(n, p-2, p); } 

ll log(ll n, ll b)
{ ll c=0;
	while(n>(b-1))
	{ c++; n/=b; } return c; }

ll fib(ll n) 
{ double phi=(1+sqrt(5))/2; 
  return round(pow(phi,n)/sqrt(5)); } 

vector<bool> prime;
void sieve(int n)
{ prime.resize(n,true);
	for(int p=2;p*p<=n;p++)
		if(prime[p])
			for(int i=p*p;i<=n;i+=p)
				prime[i]=false; }

void yes(){pn("Yes");}
void no(){pn("No");}
void bug(){cout<<"here"<<endl;}

#define MOD 1000000007 //10^9+7
#define pi 3.14159265358979323846
#define f0(i,n) for(i=0;i<n;i++)
#define f1(i,n) for(i=1;i<=n;i++)
#define fd(i,n) for(i=n-1;i>=0;i--)
#define fn(i,s,d) for(i=s;i<d;i++)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define pl pair<ll,ll>
#define pd pair<double,double>
#define vl vector<ll>
#define vb vector<bool>
#define vd vector<double>
#define vpl vector<pl>
#define vpd vector<pd>
#define vs vector<string>
#define vvl vector<vl>
#define vvs vector<vs>
#define vvpl vector<vpl>
#define ff first
#define ss second
#define um unordered_map
#define dsort(v) sort(v); reverse(v);
#define maxpq(v) priority_queue<v>
#define minpq(v) priority_queue<v,vector<v>,greater<v>>

void solve()
{
	ll i,j;
	ll n;
	cin>>n;
	ll val = 7%n;
	fn(i,1,1e7)
	{
		if(val==0)
		{
			pn(i);
			return;
		}
		val = (val*10)+7;
		val%=n;
	}
	pn(-1);
	return;
}

int main()
{
	#ifdef Deeksha
		// freopen("../Downloads/validation_input.txt", "r", stdin);
		freopen("../Downloads/_input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
    #endif
	std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	solve();/* 
	ll t;
	cin>>t;
	for(ll tt=1;tt<=t;tt++)
	{
		// cout<<"Case #"<<tt<<": ";
		solve();
	}
	//*/
}



Measured memory_bytes: 3708
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		 String num;
		 int S;
		 int M;
		 int s;
		 int H;
		  try{
			  //System.out.println("??°????????\????????????????????????");
			   num = input.readLine();
			  S=Integer.parseInt(num);
			  //System.out.println(S+"?§???§??????");
			  H=S/3600;
			  M=S%3600/60;
			  s=S%3600%60;

			  System.out.println(H+":"+M+":"+s);

		    }catch(IOException e)
		    {   System.out.println("Exception : " + e);
		    }


	}

}

Measured memory_bytes: 24304
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<string,string> P;

int n,d;
int ans=0;
set<string> mp[201][18];
int cnt[201][201];
vector<P> vec;
string str[201];

void dfs(int v,string s,int nd,int uk=0){
	if(nd==0){
		mp[v][s.size()].insert(s);
		for(int i=0;i<n;i++){
			if(mp[i][s.size()].find(s)!=mp[i][s.size()].end()){
				cnt[v][i]++;
				cnt[i][v]++;
			}
		}
		for(int i=0;i+1<s.size();i++){
			swap(s[i],s[i+1]);
			dfs(v,s,nd+1);
			swap(s[i],s[i+1]);
		}
		for(int i=0;i<s.size();i++){
			dfs(v,s.substr(0,i)+s.substr(i+1),nd+1);
			for(int j=0;j<26;j++){
				string gu="";
				gu+=('a'+j);
				dfs(v,s.substr(0,i)+gu+s.substr(i+1),nd+1,1);
				dfs(v,s.substr(0,i)+gu+s.substr(i),nd+1,1);
			}
		}
		for(int i=0;i<26;i++){
			string gu="";
			gu+=('a'+i);
			dfs(v,s+gu,nd+1);
		}
	}else if(nd==1){
		mp[v][s.size()].insert(s);
		if(d==2){
			for(int i=0;i<n;i++){
				if(mp[i][s.size()].find(s)!=mp[i][s.size()].end()){
					cnt[v][i]++;
					cnt[i][v]++;
				}
			}
		}
	}
}

void solve(){
	vec.clear();
	for(int i=0;i<n;i++){
		for(int j=0;j<18;j++){
			mp[i][j].clear();
		}
	}
	scanf("%d",&d);
	ans=0;
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<n;i++){
		cin >> str[i];
		dfs(i,str[i],0);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(cnt[i][j]>0){
				ans++;
				vec.push_back(P(min(str[i],str[j]),max(str[i],str[j])));
			}
		}
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++){
		cout << vec[i].first << "," << vec[i].second << endl;
	}
	printf("%d\n",ans);
}

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		solve();
	}
	return 0;
}


Measured memory_bytes: 18280
#include <stdio.h>

int main(){
  int n,count=0;
  scanf("%d",&n);
  int d[n];
  for(int i=0;i<n;i++){
    scanf("%d",&d[i]);
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      count+=d[i]*d[j];
    }
  }
  printf("%d",count);
}

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


void solve(std::string S){
    int ans =0;
    string days[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    for(auto day:days){
        if(S==day){
            cout <<7-ans << endl;
            break;
        }
        ans++;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()

#define MAX_D 210
#define MAX_N 210

int D, N;
int T[MAX_D];
int A[MAX_N];
int B[MAX_N];
int C[MAX_N];

int dp[MAX_D][101]; // last_score

int main() {
  cin >> D >> N;
  rep(i, D) cin >> T[i];
  rep(i, N) cin >> A[i] >> B[i] >> C[i];

  rep(i, D) rep(j, 101) dp[i][j] = -1;
  dp[0][0] = 0;
  rep(day, D) {
    rep(k, 101) {
      rep(i, N) {
        if (dp[day][k] != -1) {
          int temp = T[day];
          if (A[i] <= temp && temp <= B[i]) {
            int x = C[i];
            if (day == 0) dp[day+1][x] = dp[day][k];
            else          dp[day+1][x] = max(dp[day+1][x], dp[day][k] + abs(x-k));
          }
        }
      }
    }
  }

  int ans = 0;
  rep(k, 101) ans = max(ans, dp[D-1+1][k]);
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3184
parseline(str=readline()) = parse.(Int, split(str))
function Cmod(n, k, Mod)
    ret = 1
    for i in 1:k
        ret *= mod((n-i+1)*invmod(i, Mod) , Mod)
        ret = mod(ret, Mod)
    end
    return ret
end
function Bouquet()
    n, a, b = parseline()
    Mod = 10^9 + 7
    ret = powermod(2, n, Mod) - 1 - Cmod(n, a, Mod) - Cmod(n, b, Mod)
    println(mod(ret,Mod))
end
Bouquet()

Measured memory_bytes: 181436
#include<iostream>
#include<string>
#include<algorithm>

int main(){

    std::string s;
    std::cin >> s;

    for(const auto& e : s){
        if(e == '7'){
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }

    std::cout << "No" << std::endl;

    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <functional>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

namespace _{struct _{_(){ // initialize
  cin.tie(0); ios::sync_with_stdio(false);
}}_;}
template <typename T, size_t size>
inline size_t len(const T (&)[size]) { return size; }
#define println(s) cout << s << '\n';
#define str to_string
#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()


int main() {
  int L, A, B, C, D;
  cin >> L >> A >> B >> C >> D;
  cout << L - max((int)ceil((float)A/C), (int)ceil(((float)B/D))) << '\n';
  return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
#define Maxc 400010

int n, x;
long long Res;
vector<int > Up;
int Count[Maxc];

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		scanf("%d", &x);
		if (x>n) continue;
		if (i>x) Up.push_back(i-x);
		Count[i+x]++;
	}
	for (auto p: Up) Res+=Count[p];
	printf("%lld\n", Res);
}

Measured memory_bytes: 5852
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
 
using namespace std;
 
typedef long long ll;
const ll nmax = 1e9 + 7;
const ll mod = 998244353;
const double PI = 2 * asin(1);

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

    float ans = 0;
    for (int i = 0; i < N; i ++) {
        double X;
        string N;
        cin >> X >> N;

        if (N == "JPY") {
            ans = ans + X;
        } else {
            ans = ans + X * 380000;
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl

int n,k;
set<int>s;
bool bad[200005];
int a[200005];
int b[200005];

int main()
{
    SPEED;  
    
    cin>>n>>k;
    
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>=2)
            if(a[i]>a[i-1])
                b[i-1]++;
    }
    
    for(int i=1;i<=n;i++)
        b[i]+=b[i-1];

    for(int i=1;i<=k;i++)
        s.insert(a[i]);

    for(int i=1;i<=n-k;i++)
    {
        if((*s.begin())==a[i] && (*s.rbegin())<a[i+k] && (b[i+k-2]-b[i-1])!=k-1)
            bad[i]=1;
        s.erase(a[i]);
        s.insert(a[i+k]);
    }
    
    int ans=n-k+1;
    int cnt=0;
    for(int i=1;i<=n-k+1;i++)
    {
        if(b[i+k-2]-b[i-1]==k-1)
            cnt++;
        if(i>1 && bad[i-1])
            ans--;
    }

    if(cnt)
        ans-=cnt-1;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 11264
#include <cstdio>
int d[1000000];
int main() {
	int i,j,r=0,n;
	for(i=2;i<500000;i++) {
		if(d[i])continue;
		for(j=i*2;j<=999999;j+=i)d[j]=1;
	}
	for(i=2;i<=999999;i++) {
		if(!d[i])r++;
		d[i]=r;
	}
	while(scanf("%d",&n)!=EOF) {
		printf("%d\n",d[n]);
	}
}

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

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

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N;
  cin >> N;
  vi p(N);
  rep(i,N) {
    cin >> p[i];
  }
  sort(rng(p));
  int sum = 0;
  rep(i,N-1) {
    sum += p[i];
  }
  sum += p[N-1] / 2;
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
import re
while True:
    s = input()
    if s=='.': break
    s = re.sub(u'[a-zA-Z .]+','',s)
    while '()' in s or '[]' in s:
        s = s.replace('()','').replace('[]','')
    print('yes' if len(s)==0 else 'no')

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

int main() {
  int N;
  cin >> N;
  for(int i=1; i<N+1; i++) {
    int sum=0;
    for(int x=1; x<sqrt(i)+1; x++) {
      for(int y=x; y<sqrt(i)+1; y++) {
        for(int z=y; z<sqrt(i)+1; z++) {
          if ((x+y+z)*(x+y+z)-((x*y)+(y*z)+(x*z)) == i && x == y && y == z) {
            sum++;
          }
          else if ((x+y+z)*(x+y+z)-((x*y)+(y*z)+(x*z)) == i && x != y && x != z && y != z) {
            sum = sum + 6;
          }
          else if ((x+y+z)*(x+y+z)-((x*y)+(y*z)+(x*z)) == i) {
            sum = sum + 3;
          }
        }
      
      }
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 3492
N = int(input())
ans = True
tprev = 0
xprev = 0
yprev = 0
for _ in range(N):
    tnow,xnow,ynow = list(map(int,input().split()))
    time = abs(xnow-xprev) + abs(ynow-yprev)
    if time > tnow-tprev or (tnow-tprev-time)%2 == 1:
        ans = False
        break
    tprev = tnow
    xprev = xnow
    yprev = ynow
if ans:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegtreeMax():
    def __init__(self, aa):
        self.inf = 10 ** 16
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = max(self.tree[u * 2 + 1], self.tree[u * 2 + 2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最大値
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return -self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

    # [l,r)でrから左を見たとき、初めにaを超える値のインデックス
    def OverL(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u]<=a: return -1
        if ur-ul==1:return ul
        um = (ul + ur) // 2
        ret = self.OverL(l, r, a, u * 2 + 2, um, ur)
        if ret != -1: return ret
        return self.OverL(l, r, a, u * 2 + 1, ul, um)

    # [l,r)でlから右を見たとき、初めにaを超える値のインデックス
    def OverR(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u] <= a: return self.n
        if ur - ul == 1: return ul
        um = (ul + ur) // 2
        ret = self.OverR(l, r, a, u * 2 + 1, ul,um)
        if ret != self.n: return ret
        return self.OverR(l, r, a, u * 2 + 2, um,ur)

mx=300005
n,k=MI()
st=SegtreeMax([0]*mx)
for _ in range(n):
    a=II()
    val=st.max(max(0,a-k),min(mx,a+k+1))
    st.update(a,val+1)
print(st.tree[0])


Measured memory_bytes: 103008
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int main(void){
	int D,L,sum=0;
	cin>>D>>L;
	sum+=D/L;
	D-=L*(D/L);
	sum+=D;
	cout<<sum<<endl;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1000000000 + 7;

bool debug = 0;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll cmin = INF;
    for (int i = -100; i <= 100; i++) {
        ll c = 0;
        for (int j = 0; j < n; j++) {
            c += (i - a[j]) * (i - a[j]);
        }
        cmin = min(cmin, c);
    }
    cout << cmin << endl;
}

int main() {
    if (debug) {
        while (true) {
            cout << "********" << endl;
            solve();
        }
    } else {
        solve();
    }
    return 0;
}

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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		Console.WriteLine(Math.Min(B, A * N));
	}
	int N,A,B;
	public Sol(){
		var d = ria();
		N = d[0]; A = d[1]; B = d[2];
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 11092
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  int n = readln.chomp.to!int;
  long min = 1;
  long sum = readln.chomp.to!long - 1;
  foreach (i; 1..n) {
    long a = readln.chomp.to!long;
    sum += (a - 1) / (min + 1);
    
    if (min + 1 == a) {
      min++;
    }
  }
  sum.writeln;
}


Measured memory_bytes: 1276
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
#define MOD 1000000007
int main() {
  string s;
  cin >> s;
  int n = s.length();
  int p = 13;
  int ten = 1;
  int q = 0;

  vector<vector<int>> d(n + 1, vector<int>(13, 0));
  vector<vector<int>> dp(n + 1, vector<int>(13, 0));
  for(int i = n - 1; i >= 0; i--) {
    if(s[i] == '?') {
      for(int j = 0; j <= 9; j++) {
        if(i == n - 1) {
          int a = j * ten % p;
          d[i][a] = 1;
          dp[i][a] = 1;
          dp[i][a] %= MOD;
        } else {
          int a = j * ten % p;
          for(int k = 0; k < 13; k++) {
            if(d[i + 1][k] == 1) {
              d[i][(a + k) % p] = 1;
              dp[i][(a + k) % p] += dp[i + 1][k];
              dp[i][(a + k) % p] %= MOD;
            }
          }
        }
      }
      q++;
    } else {
      int a = (s[i] - '0') * ten % p;
      if(i == n - 1) {
        d[i][a] = 1;
        dp[i][a] = 1;
      } else {
        for(int k = 0; k < 13; k++) {
          if(d[i + 1][k] == 1) {
            d[i][(a + k) % p] = 1;
            dp[i][(a + k) % p] += dp[i + 1][k];
            dp[i][(a + k) % p] %= MOD;
          }
        }
      }
    }
    ten *= 10;
    ten %= p;
  }
  cout << dp[0][5] << '\n';
  return 0;
}

Measured memory_bytes: 17536
// #include "d.h"
#include <bits/stdc++.h>

using namespace std;

const int L = 128;
const string C = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

int n, cnt[62];

int query(const string &t)
{
	cout << "? " << t << "\n";
	int r;
	cin >> r;
	return r;
}

string f(int l, int r)
{
	if (l == r)
		return string(cnt[l], C[l]);
	string a = f(l, (l+r)/2),
		   b = f((l+r)/2+1, r);
	size_t i = 0, j = 0;
	for (int _=a.size(); _ >= 0; _--)
	{
		for (; j < b.size() && query(a.substr(0, i) +
				b[j] + a.substr(i)) == n - int(a.size()) - 1;
				i++, j++)
			a.insert(a.begin() + i, b[j]);
		i++;
	}
	return a;
}

string find_password()
{
	for (int i=0; i<62; i++)
	{
		cnt[i] = L - query(string(L, C[i]));
		n += cnt[i];
	}
	return f(0, 61);
}

int main()
{
	ios_base::sync_with_stdio(false);
	string s = find_password();
	cout << "! " << s << "\n";
	return 0;
}

Measured memory_bytes: 3744
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

N, M = rdi()
a = []
b = []
for i in range(M):
        ai, bi = rdi()
        a.append(ai)
        b.append(bi)

c = {}
for i in range(N):
        c[i+1] = 0
for i in range(M):
        ai = a[i]
        bi = b[i]
        c[ai] += 1
        c[bi] += 1
for i in range(N):
        print c[i+1]

Measured memory_bytes: 4332
import math

A,B,H,M = map(int, input().split())

h = ((60*H+M)*0.5)%360
m = (6*M)%360

theta = abs(h-m)
len = math.sqrt(A*A+B*B-2*A*B*math.cos(math.radians(theta)))
print(len)

Measured memory_bytes: 62660
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());//キーボード入力

		int[] ary=new int[n];//配列作成
		int i=0;

		StringTokenizer st=new StringTokenizer(br.readLine());

		while(i<n) {
			int a=Integer.parseInt(st.nextToken());
			ary[i]=a;
			i++;
		}

		int max=ary[0];
		int min=ary[0];
		long sum=0;

		for(i=0;i<ary.length;i++) {
			int v=ary[i];
			if(v>max) {
				max=v;
			}
			if(v<min) {
				min=v;
			}
			sum=sum+v;
		}
		System.out.println(min+" "+max+" "+sum);
	}

}



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

int main() {
 int n,m,c;
 cin >> n>> m>> c;
 vector<int> b(m) ;
   for (int i;i<m;i++){
     cin >> b.at(i);
   }
  int ans =0;
  for (int j=0;j<n;j++){
    int score =0;
    for (int i=0;i<m;i++){
      int a ;
      cin >>a;
      score +=(a*b.at(i));
    }
    if (score>-c){
      ans ++ ;
    }
  }
   cout <<ans;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	// 階乗
	public static long factorial (int n) {
		long sum = 1;
		for (; n >= 2; n--)
			sum *= n;
		return sum;
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		System.out.println(factorial(sc.nextInt()));

	}

}

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

int main(){
    int a,b; cin >> a >> b;
    if(a==1) a=14;
    if(b==1) b=14;
    if(a>b) cout << "Alice" << endl;
    else if(b>a) cout << "Bob" << endl;
    else cout << "Draw" << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
#include <stdio.h>
#include <vector>
#define int long long
using namespace std;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int mypow(int x, int y) {
	if (y == 0)return 1;
	if (y % 2)return mypow(x, y - 1)*x;
	else return mypow(x, y / 2)*mypow(x, y / 2);
}
int Max(int x, int y) {
	if (x > y)return x;
	else return y;
}
int Min(int x, int y) {
	if (x < y)return x;
	else return y;
}
int kai(int x) {
	int cnt = 1;
	if (x == 0)return 1;
	cnt = kai(x - 1);
	return x * cnt;
}
inline void shoki()
{
	srand((unsigned int)time(NULL));
}

/*Library End!*/

signed main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a <= c && b <= d) {
		if (c <= b)cout << b - c << endl;
		else cout << 0 << endl;
	}
	else if (a <= c && b > d)cout << d - c << endl;
	else if (a > c&&b <= d)cout << b - a << endl;
	else {
		if (a >= d)cout << 0 << endl;
		else cout << d-a << endl;
	}
}

Measured memory_bytes: 256