akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
vector<ll> v[100001];
vector<pair<ll, ll>> edges;
queue<ll> q;
ll b[100001], h = 1, h_cur;
map<pair<ll, ll>, ll> m;
void bfs() {
	while(!q.empty()) {
		ll i = 1;
		h_cur = h;
		ll temp = q.front();
		q.pop();
		vector<ll> cur(h, 1);
		for(auto u: v[temp]) {
			ll node1 = temp;
			ll node2 = u;
			if(node1 > node2) {
				swap(node1, node2);
			}
			ll color = m[mp(node1, node2)];
			if(color != -1) {
				cur[color] = 0;
			}
		}
		for(auto u: v[temp]) {
			ll node2 = u;
			ll node1 = temp;
			if(node1 > node2) {
				swap(node1, node2);
			}
			if(m[mp(node1, node2)] == -1) {
				while(i < h_cur && cur[i]==0) {
					i++;
				}
				if(i >= h_cur) {
					m[mp(node1, node2)] = h++;
				}
				else {
					m[mp(node1, node2)] = i++;
				}
			}
			if(!b[u]) {
				b[u] = 1;
				q.push(u);
			}
		}
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, i, x, y;
    cin>>n;
    for(i=0; i<n-1; i++) {
    	cin>>x>>y;
    	v[x].pb(y);
    	v[y].pb(x);
    	if(x > y) {
    		swap(x, y);
    	}
    	edges.pb(mp(x, y));
    	m[mp(x, y)] = -1;
    }
    q.push(1);
    b[1] = 1;
    bfs();
    cout<<h - 1 <<"\n";
    for(auto u: edges) {
    	cout<<m[u]<<"\n";
    }

}

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

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    
    if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

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

int f(int x) {
	if (x == 0) {
		return 1;
	}
	return f(x - 1) * x;
}

int count(int *p, int n) {
	bool *vis = new bool[n + 1];
	for (int i = 1; i <= n; ++i) {
		vis[i] = false;
	}
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int ct = 0;
		for (int j = 1; j < p[i]; ++j) {
			if (!vis[j]) {
				++ct;
			}
		}
		//cout << i << ' ' << ct << endl;
		res += (ct * f(n - i - 1));
		vis[p[i]] = true;
	}
	delete []vis;
	return res;
}

int main() {
	int n;
	int *p, *q;
	cin >> n;
	p = new int[n];
	q = new int[n];
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> q[i];
	}
	int pc = count(p, n), qc = count(q, n);
	cout << abs(pc - qc) << endl;

	return 0;
}

Measured memory_bytes: 256
<?php
while(1){
    list($n,$p) = explode(" ",trim(fgets(STDIN)));
    if($n == 0 && $p == 0) break;
    $person = array_fill(0,$n,0);
    $s = $p;    // stone num in bowl
    $t = 0;     // turn
    while(1){
        if($s > 0){
            $person[$t]++;
            $s--;
        } elseif($s == 0){
            $s = $person[$t];
            $person[$t] = 0;
        }
        if($person[$t] == $p){
            echo $t."\n";
            break;
        }
        $t = ($t + 1) % $n; // Circulation
    }
}

Measured memory_bytes: 15304
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, ans;

int main()
{
	in >> N;
	std::vector<LL>A(N), Nimos(N + 1), Ximos(N + 1);
	rep(i, N)
	{
		in >> A[i];
		Nimos[i + 1] = A[i] + Nimos[i];
		Ximos[i + 1] = A[i] ^ Ximos[i];
	}
	LL l = 0, r = 0;
	while (r < N)
	{
		LL Nsum = Nimos[r + 1] - Nimos[l];
		LL Xsum = Ximos[r + 1] ^ Ximos[l];
		if (Xsum == Nsum)
		{
			++ans;
			ans += r - l;
			++r;
		}
		else
		{
			++l;
		}
	}
	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 4992
#include <algorithm>
#include <complex>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

const unsigned long long MOD = 1e9 + 7;
typedef unsigned long long ull;

ull fact(int n){
    ull ans = 1;
    for(int i = 1; i <= n; i++){
        ans *= i;
        ans %= MOD;
    }
    return ans;
}

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

    const int a = min(n, m);
    const int b = max(n, m);

    ull ans;
    if(a == b){
        ans = fact(a) * fact(b) % MOD;
        ans = ans * 2 % MOD;
    }else if(a == b - 1){
        ans = fact(a) * fact(b) % MOD;
    }else{
        ans = 0;
    }

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


Measured memory_bytes: 256
s = gets.chomp
n = s.size
i = 2
ans = 0
sa = 10000000000000
(0..n-3).each do |i|
    time = 1
    arr = []
    until time == 4
        arr << s[i]
        time += 1
        i += 1
    end
    #p arr
    arr = arr.join("").to_i
    saa = (arr - 753).abs
    sa = [sa,saa].min
end
puts sa

Measured memory_bytes: 14304
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;



public class Main{
	
	//最大公約数・最小公倍数（セットで使う）
	public static long gcm(long a, long b) {
		long result = a;
		long k = 0;
		long n = b;
		do {
			k = result % n;
			result = n;
			n = k;
		} while(k != 0);
		return result;
	}
	
	public static long lcm(long a, long b) {
		long g;
		g = gcm(a, b);
		return a/g*b;
	}
	
	static long gcd (long a, long b) {
		long temp;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return b;
	}
	
	//等差数列
	static long tousasum(int n) {
		return (long)n*((long)n+1)/2;
	}



	//素数判定
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
		return true;
	}


	//倍数判定（10進数以外のときに有用）
	static boolean isMultiple (String s, int base, int m) {
		int temp = 0;
		for (int i=0; i<s.length(); i++) {
			temp = (temp*base+Character.getNumericValue(s.charAt(i)))%m;
		}
		if (temp==0) {return true;}
		return false;
	}


	//階乗
	static long factorial (int i) {
		if (i==1) {return 1;}
		else {return i*factorial(i-1);}
	}


	//進数変換
	static String toNbase (String sm, int m, int n) {
		return Long.toString(Long.parseLong(sm,m),n);
	}
	
	public static final long gcd_n(long[] param) {
	    final int len = param.length;
	    long g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
	    for (int i = 1; i < len - 1; i++) {
	        g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
	    }
	    return g;
	}
	
	public static long lcm_n(long[] numbers) {
		long l;
		l = numbers[0];
		for (int i = 1; i < numbers.length; i++) {
			l = lcm(l, numbers[i]);
		}
		return l;
	}
	
	
 public static void main(String[] args) {
	 Scanner sc=new Scanner(System.in);
	 int N=sc.nextInt();
	 int[] H=new int[N];
	 for(int i=0;i<N;i++) {
		 H[i]=sc.nextInt();
	 }
	 
	 int max=0;
	 int temp=0;
	 
	 for(int i=0;i<N-1;i++) {
		if(H[i]>=H[i+1]) {
			temp++;
			if(max<temp) {
				max = temp;
			}
			
		}else if(H[i]<H[i+1]){
			if(max<temp) {
				max = temp;
			}
			temp=0;
		}
		
		
	 }
	 
 
	 System.out.println(max);
	 
	 
	
	 
	 
	 
 }
	


}



Measured memory_bytes: 50520
//----------------------------------------------------------------------
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
//----------------------------------------------------------------------

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

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

    Graph freq(m+1);
    REP(i, n) {
        int a, b;
        cin >> a >> b;
        if(a > m) continue;
        freq[a].push_back(b);
    }
    priority_queue<int> q;
    ll ans = 0;
    for(int i = m-1; i >= 0; --i) {
        for(int v : freq[m - i]) {
            q.push(v);
        }
        if(!q.empty()) {
            ans += q.top(); q.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632
# 2019-11-10 17:11:42(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np
# import statistics

def main():
    
    n, *v = (int(x) for x in sys.stdin.read().split())

    odds, evens = [], []
    for i in range(n):
        if i % 2 == 0:
            odds.append(v[i])
        else:
            evens.append(v[i])


    o_c = collections.Counter(odds)
    e_c = collections.Counter(evens)
    
    o_c = sorted(list((k, v) for k, v in o_c.items()), key=op.itemgetter(1), reverse=True)
    e_c = sorted(list((k, v) for k, v in e_c.items()), key=op.itemgetter(1), reverse=True)

    ans = n
    if o_c[0][0] != e_c[0][0]:
        ans = n - o_c[0][1] - e_c[0][1]
    else:
        if len(o_c) == 1 and len(e_c) == 1:
            ans = n - n // 2
        elif len(o_c) == 1 and len(e_c) >= 2:
            ans = n - e_c[1][1]
        elif len(o_c) >= 2 and len(e_c) == 1:
            ans = n - o_c[1][1]
        else:
            ans = n - max(o_c[0][1] + e_c[1][1], o_c[1][1] + e_c[0][1])
    
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 20692
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

struct LowLink {
    vector<P> bridge;
    vector<int> ord,low;
    vector<bool> used;
    vector<vector<int>> g;
    int n, k = 0;
    LowLink(const vector<vector<int>> &g) : g(g) {
        n = g.size();
        ord.resize(n, -1);
        low.resize(n, -1);
        used.resize(n, false);
    }
    void dfs(int v, int pre) {
        used[v] = true;
        ord[v] = k++;
        low[v] = ord[v];
        int cnt = 0;
        for(auto &to : g[v]) if(to != pre) {
            if(!used[to]) {
                cnt ++;
                dfs(to, v);
                low[v] = min(low[v], low[to]);
                if(low[to]>ord[v]) {
                    bridge.emplace_back(min(v,to), max(v,to));
                }
            }
            else {
                low[v] = min(low[v], ord[to]);
            }
        }
    }
};

int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> g(n);
    REP(i,m) {
        int a,b; cin >> a >> b; a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    LowLink ans(g);
    ans.dfs(0,-1);
    cout << ans.bridge.size() << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.* ; 
import java.math.*;
class Main{
  public static void main(String[] args) {
    Scanner scan = new Scanner (System.in);
	int n = scan.nextInt();
    String s = scan.next();
    char[] ch = s.toCharArray();
    int x = 0 ;
    int max = 0;
    for(int i = 0 ; i <n ; i++){
      if(ch[i] == 'I'){
        x++;
        if(x>max){
          max = x ;
        }
      }else if(ch[i] == 'D'){
        x-- ;
      }
    }
    System.out.println(max);
  }
}

Measured memory_bytes: 20820
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <numeric>
#include <ctype.h>
#include <cstdlib>
#include <string.h>
#include <cmath>
#include <cstdio>





using namespace std;


int main()
{
	int count = 0, num;

	

	while (cin >> num)
	{
		count = 0;

		for (int a = 0; a < 10; a++)
		{
			for (int b = 0; b < 10; b++)
			{
				for (int c = 0; c < 10; c++)
				{
					for (int d = 0; d < 10; d++)
					{
						if (a + b + c + d == num)
							count++;
					}
				}
			}
		}
		cout << count << endl;
	}

	

}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        // おなじ
        while(i+1 < n && a[i]==a[i+1]){
            i++;
        }
        // up
        if(i+1<n && a[i]<a[i+1]){
            while(i+1 < n && a[i]<=a[i+1]){
                // iをすすめる
                i++;
            }
        }
        // down
        else if(i+1<n && a[i] > a[i+1]){
            while(i+1 < n && a[i]>=a[i+1]){
                i++;
            }
        }
        // 分割
        ans+=1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){

			int[][] sima = new int[12][12];
			int count = 0;

			for(int i = 0; i < 12 ; i ++){
				String str = sc.next();

				for(int j = 0; j < 12; j ++){
					String[] s = str.split("");
					sima[i][j] = Integer.parseInt(s[j]);
				}
			}

			for(int i = 0; i < 12; i++){
				for(int j = 0; j < 12; j++){
					if(sima[i][j] == 1){

						IslandMap.check(i, j, sima);
						count++;
					}
				}
			}
			System.out.println(count);
		}
		sc.close();
	}
}

class IslandMap{
	static int[][] sima;
	int tate;
	int yoko;


	public IslandMap(int i, int j, int[][] sima2) {
		this.tate = i;
		this.yoko = j;
		IslandMap.sima = sima2;
	}


	public static void check(int tate , int yoko, int[][] sima){

		sima[tate][yoko] = 0;

		if(tate+1 < 12){
			if(sima[tate+1][yoko] == 1){
				check(tate+1 , yoko , sima);
			}
		}
		if(yoko+1 < 12){
			if(sima[tate][yoko+1] == 1){
				check(tate , yoko+1 , sima);
			}
		}
		if(tate-1 > -1){
			if(sima[tate-1][yoko] == 1){
				check(tate-1 , yoko , sima);
			}
		}
		if(yoko-1 > -1){
			if(sima[tate][yoko-1] == 1){
				check(tate , yoko-1 , sima);
			}
		}
	}
}

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

using namespace std;

int main() {
    int n,dum,res;
    cin >> n;
    vector<int> vc(n);
    res = 0;
    for (int i=0; i<n; i++) cin >> vc[i];
    for (int i=0; i<n; i++) {
        cin >> dum;
        if (vc[i] - dum>0) {
            res+=vc[i] - dum; 
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
/*
 * 17-3-18_ARC070_C.cpp
 *
 *  Created on: 2017/03/18
 *      Author: ryoma
 */

#include<iostream>
#include<algorithm>

using namespace std;

int X;
int main(){
	cin >> X;
	X = abs(X);
	int n=0;
	for(n=0;n*(n+1)/2<X;n++){
	}
	cout << n << endl;
	return 0;
}



Measured memory_bytes: 256
import sys


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
    if K <= 2:
        if N <= K:
            p = 1
            for n in range(N):
                p *= K - n
            print(p % MOD)
        else:
            print(0)
        return
    p = 1
    perm_k1 = [0 for _ in range(K)]
    for k in range(K):
        perm_k1[k] = p
        p *= K - 1 - k
        p %= MOD
    perm_k2 = [0 for _ in range(K - 1)]
    p = 1
    for k in range(K - 1):
        perm_k2[k] = p
        p *= K - 2 - k
        p %= MOD

    def dfs(n=0, p=-1):
        # node, parentの色を固定した時の色の塗り方
        children = [c for c in adj[n] if c != p]
        if len(children) == 0:
            return 1
        n_colors = K - 2 if n != 0 else K - 1
        if n_colors < len(children):
            return 0
        ret = perm_k2[len(children)] if n != 0 else perm_k1[len(children)]
        for c in children:
            ret *= dfs(c, n)
            ret %= MOD
        return ret

    print((K * dfs()) % MOD)


if __name__ == '__main__':
    main()

Measured memory_bytes: 123780
#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using str = string; using cstr = const str;
using ll = long long; using ull = unsigned long long; using cint = const int; using cll = const ll;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using psl = pair<string, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7;
static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}


int32_t main(int32_t argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef IMPORT_SAMPLE
    vs args(argv, argv+argc);
    string sample = make_sample(args, "sample-1");
    ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#endif


    int H, W; cin >> H >> W;
    vs S(H); REP(i, H) cin>>S[i];

    int black = 0;
    REP(i, H)
        REP(j, W) if (S[i][j] == '#') black++;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    queue<pii> que;
    que.push(mkpr(0, 0));
    vvi dist(H, vi(W, -1));
    dist[0][0] = 0;

    while(!que.empty()) {
        var pr = que.front(); que.pop();
        int x = pr.first, y = pr.second;

        if(x == H-1 and y ==  W-1) break;

        REP(i, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 or H <= nx or ny < 0 or W <= ny) continue;
            if (S[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;

            dist[nx][ny] = dist[x][y] + 1;
            que.push(make_pair(nx, ny));
        }
    }

    int ans = -1;
    int sdist = dist[H-1][W-1];
    if (sdist != -1) {
        ans = H*W - black - (sdist + 1);
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    #print(H)
    ans = []
    ansn = 0
    for _ in range(N):
        ans.append(0)
    for i in range(M):
        A,B = map(int, input().split())
        if H[A-1] < H[B-1]:
            ans[A-1] = -1
        elif H[A-1] > H[B-1]:
            ans[B-1] = -1
        else:
            ans[B-1] = -1
            ans[A-1] = -1
    for j in ans:
        if j == 0:
            ansn += 1
    #print(ansn, ans)
    print(ansn)

if __name__ == '__main__':
    main()

Measured memory_bytes: 20128
#include<stdio.h>
int main(void)
{
	int w,n,i;
	scanf("%d",&w);
		while(w!=-1){
		n=w-10;
		w=1150;
		if(n>0){
			for(i=0;i<10;i++){
				n--;
				w=w+125;
				if(n==0)  break;
			}
		}
		if(n>0){
			for(i=0;i<10;i++){
				n--;
				w=w+140;
				if(n==0)  break;
			}
		}
		while(n>0){
			n--;
			w=w+160;
			if(n==0)  break;
		}
		w=4280-w;
		printf("%d\n",w);
		scanf("%d",&w);
	}
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int
#define va vector<long long int> a 
#define vb vector<long long int> b
#define M 1000000007
using namespace std;
ll t;
void fast(){cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);}
ll power(ll x,ul y,ll p){ll res = 1;x = x % p;if(x == 0)return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
void solve(){
	ll n,x,count=0;
	cin>>n;
	map<ll,ll> v1;
	for(ll i=0;i<n;i++){
		cin>>x;
		v1[i+x]++;
		if(i-x>0) count+=v1[i-x];
	}
	cout<<count<<"\n";
 }
int main(){
	fast();
	solve();
	return 0;
}



Measured memory_bytes: 17396
from queue import LifoQueue


def print_sol(c, sol):
    print('Case #{}: {}'.format(c, sol))


def rd_int():
    return int(input())


def rd_str():
    return input()


def rd_str_lst():
    return input().split(' ')


def sp_str_lst():
    return list(input())


def rd_int_lst():
    return [int(i) for i in rd_str_lst()]


def sp_int_lst():
    return [int(i) for i in sp_str_lst()]


def dfs(g, i, v):
    """
    recursive post order dfs
    Args:
        g: array of graph nodes
        i: node to traverse
        v: visited array

    Returns: a post order dfs of graph g
    """
    v[i] = True
    for j in g[i]:
        if not v[j]:
            dfs(g, j, v)

    print(i)


def dfs_iter(g, i, n):
    v = [False] * n
    stack = LifoQueue()
    stack.put(i)
    while stack.not_empty:
        u = stack.get()
        v[u] = True
        print(u)
        for i in g[u]:
            if not v[i]:
                stack.put(i)


def main():
    a = rd_int()
    a2 = a * a
    a3 = a2 * a
    print(a + a2 + a3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9704
import java.math.*

fun main(args: Array<String>) {
    val s = readInputLine()
    val nums = s.toCharArray().map { it.toString().toInt() }
    
    var ans = Int.MAX_VALUE
    
    for (i in 2 until nums.size) {
        val tmp = Math.abs(753 - (nums[i] + nums[i - 1] * 10 + nums[i - 2] * 100))
        if (tmp < ans) {
            ans = tmp
        }
    }
    
    println(ans)
}
 
fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 33688
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 200000;

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

vector<pair<ll,ll>> v;
int n;

int main(){
    cin >> n;
    rep(i,n){
        pair<ll,ll> p;
        cin >> p.first>>p.second;
        v.push_back(p);
    }
    
    sort(all(v),compare_by_b);
    
    ll tl = INF;
    
//    rep(i,n){
//        cout << v[i].first <<' '<<v[i].second<<endl;
//    }
    
    rep(i,n){
        tl = min(tl,v[i].second);
        //cout << "tl"<<' '<<tl<<endl;
        tl -= v[i].first;
        if(tl<0){
            No;
            return 0;
        }
    }
    
    Yes;
    
    return 0;
}


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

using namespace std;

/*int gcd(int a,int b){
	if(b==0){
		return a;
	}
    return gcd(b,a%b);
}*/

int gcd(int a, int b) {
  int A = max(a, b);
  int B = min(a, b);
  if (A < 1 || B < 1) {
    return A;
  }
  return gcd(B, A % B);
}


int main()
{
	int N,X;
	cin >> N>>X;
	vector<int>A1;

	for(int i=0;i<N;i++){
		int v;
		cin >> v;
		A1.emplace_back(abs(v-X));

	}

	int S = A1[0];

	for(int i=1;i<N;i++){



		S = gcd(S,A1[i]);



	}

	cout <<S<<endl;
	return 0;
}

Measured memory_bytes: 892
use std::fmt::Debug;
use std::str::FromStr;

pub struct TokenReader {
    reader: std::io::Stdin,
    tokens: Vec<String>,
    index: usize,
}

impl TokenReader {
    pub fn new() -> Self {
        Self {
            reader: std::io::stdin(),
            tokens: Vec::new(),
            index: 0,
        }
    }

    pub fn next<T>(&mut self) -> T
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index += 1;
        self.tokens[self.index - 1].parse().unwrap()
    }

    pub fn vector<T>(&mut self) -> Vec<T>
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index = self.tokens.len();
        self.tokens.iter().map(|tok| tok.parse().unwrap()).collect()
    }

    pub fn load_next_line(&mut self) {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();

        self.tokens = line
            .split_whitespace()
            .map(String::from)
            .collect();
        self.index = 0;
    }
}

enum Res {
    Pairwise,
    Setwise,
    NotCoprime
}

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn add_mask(mut num: i32, count: &mut Vec<i32>) {
    let mut factor = 2;
    while factor <= num / factor {
        if num % factor == 0 {
            count[factor as usize] += 1;
        }
        while num % factor == 0 {
            num /= factor;
        }
        factor += 1;
    }
    if num > 1 {
        count[num as usize] += 1;
    }
}

fn solve(nums: &Vec<i32>) -> Res {
    let mut all_gcd = nums[0];
    let mut count = vec![0; 1e6 as usize + 2];

    for &num in nums.iter() {
        all_gcd = gcd(all_gcd, num);
        add_mask(num, &mut count);
    }

    if count.into_iter().all(|x| x < 2) {
        Res::Pairwise
    } else if all_gcd == 1 {
        Res::Setwise
    } else {
        Res::NotCoprime
    }
}

fn main() {
    let mut reader = TokenReader::new();
    let _ = reader.next::<usize>();
    let nums = reader.vector();

    match solve(&nums) {
        Res::Pairwise => println!("pairwise coprime"),
        Res::Setwise => println!("setwise coprime"),
        Res::NotCoprime => println!("not coprime"),
    }
}


Measured memory_bytes: 64396
import java.util.Scanner;

public  class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if (a < b && b < c) {
            System.out.println( "Yes" ); }
        else {
            System.out.println( "No");
        }

    }
}


Measured memory_bytes: 26228
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int inf = 1000000000;

int main(void) {

  double t;
  while( cin >> t ){
    double sum = 0.0;
    for(int i=0; i<10; i++){
      sum += t;
      if( i % 2 == 0 ) t = t * 2;
      else t = t / 3;
    }
    printf("%.10lf\n", sum);
  }

  return 0;
}

// EOF

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n, m;
  std::cin >> n >> m;
  std::vector<int64_t> h(n);
  std::cin >> h;

  std::vector<bool> f(n, true);

  for (int64_t i = 0; i < m; i++) {
    int64_t a, b;
    std::cin >> a >> b;
    a--;
    b--;

    if (h[a] <= h[b]) {
      f[a] = false;
    }
    if (h[b] <= h[a]) {
      f[b] = false;
    }
  }

  std::cout << std::count(f.cbegin(), f.cend(), true) << std::endl;

  return 0;
}


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


signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    int ans = 0;
    int c[10][10] = {0};
    for (int i = 1; i <= N; i++) {
        int a = i;
        int b = i % 10;
        while (a >= 10){
            a /= 10;
        } 
        c[a][b]++;
    }
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            ans += c[i][j] * c[j][i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
double len(double x,double xx,double y,double yy){
  return pow((x-xx)*(x-xx)+(y-yy)*(y-yy),0.5);
}
int main(){
  double x[3],y[3];
  for(int i=0;i<3;i++){
    cin>>x[i]>>y[i];
  }
  double ans=0;
  double co[3],si[3];
  for(int i=0;i<3;i++){
    double a=len(x[i],x[(i+1)%3],y[i],y[(i+1)%3]);
    double b=len(x[i],x[(i+2)%3],y[i],y[(i+2)%3]);
    double c=len(x[(i+2)%3],x[(i+1)%3],y[(i+2)%3],y[(i+1)%3]);
    co[i]=(a*a+b*b-c*c)/(2*a*b);
    si[i]=pow(1-co[i]*co[i],0.5);
  }
  for(int i=0;i<3;i++){
    double a=len(x[i],x[(i+1)%3],y[i],y[(i+1)%3]);
    double r=a/(2+(1+co[i])/si[i]+(1+co[(i+1)%3])/si[(i+1)%3]);
    ans=max(r,ans);
  }
  cout<<fixed<<setprecision(10)<<ans<<endl;
}
    

Measured memory_bytes: 384
while(1):
    [a,b]=[int(x) for x in raw_input().split()]
    if a==0:
        break
    else:
        n=int(raw_input())
        S=[[-1 for x in range(b+1)] for y in range(a+1)]
        for i in range(a+1):
            S[i][0]=0
        for i in range(b+1):
            S[0][i]=0
        for i in range(n):
            [bx,by]=[int(x) for x in raw_input().split()]
            S[bx][by]=0
        S[1][1]=1
        for h in range(1,b+1):
            for x in range(1,a+1):
                if S[x][h]==-1:
                    S[x][h]=S[x-1][h]+S[x][h-1]
        print S[a][b]

Measured memory_bytes: 4268
#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 ll long long
#define INF 999999999
using namespace std;
int main() {
  ll N, A, B;
  std::cin >> N >> A >> B;
  ll ans;
  ans = (B-A)*(N-2)+1;
  if (A > B) {
    std::cout << 0 << '\n';
  }
  else if ( N == 1 && B == A) {
    std::cout << 1 << '\n';
  }
  else if ( N == 1 && B != A) {
    std::cout << 0 << '\n';
  }
  else{
    std::cout << ans << '\n';
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String[] args) {
    
	  Scanner sc = new Scanner(System.in);
	  
	  int a = sc.nextInt();
	  
	  int b = sc.nextInt();
	  
	 if(a<b){
		 System.out.println("a < b");
	 }else if(a>b){
		 System.out.println("a > b");
	 }else if(a==b){
		 System.out.println("a == b");
	 }
	 
	  
  }
}

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

using namespace std;


int main(){
    int A,B,s,t,u,v;
    cin >> A >> B;
    int ans = 0;

    for(int i=A;i<=B;i++){
        s = i % 10;t=(i/10000)%10;
        u=(i/10)%10;v=i/1000%10;
        if(s==t && u==v){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

// セグメント木
// ref:https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
template <typename Mnd>
struct segment_tree {
    int sz;
    vector<Mnd> data;
    function<Mnd(Mnd, Mnd)> f;
    Mnd e;
    //サイズだけ指定して初期化
    segment_tree(int _sz, function<Mnd(Mnd, Mnd)> _f, Mnd _e) : f(_f), e(_e) {
        sz = 1;
        while (sz < _sz) sz <<= 1;
        data.assign(sz * 2, e);
    }
    //参照渡しなので代入とかもできる
    Mnd& operator[](const int& k) {
        return data[k + sz];
    }
    //木を構築 O(n)
    void build() {
        for (int i = sz - 1; i > 0; i--)
            data[i] = f(data[2 * i], data[2 * i + 1]);
    }
    //更新しつつ木を再構築 O(log n)
    void update(int k, Mnd x) {
        data[k += sz] = x;
        while (k >>= 1) data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    //[a,b)でのクエリに答える　O(log n)
    Mnd query(int a, int b) const {
        Mnd l = e, r = e;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) l = f(l, data[a++]);
            if (b & 1) r = f(r, data[--b]);
        }
        return f(l, r);
    }
};

// 各項の順序を保ったまま最小値0,最大値(要素種)-1以下にする
template <typename T>
vector<int> simplify(vector<T>& a) {
    int n = a.size();
    map<T, int> dic;
    for (int i = 0; i < n; i++) dic[a[i]] = 0;
    int k = 0;
    for (auto itr = dic.begin(); itr != dic.end(); itr++) (*itr).second = k++;
    vector<int> res(n);
    for (int i = 0; i < n; i++) res[i] = dic[a[i]];
    return res;
}
// 転倒数を計算
// depend:segment_tree
template <typename T>
long long inversion_number(vector<T>& a) {
    using lint = long long int;
    int n = a.size();
    vector<int> b = simplify(a);
    segment_tree<lint> count(
        n, [](lint a, lint b) { return a + b; }, 0);
    lint res = 0;
    for (int i = 0; i < n; i++) {
        res += count.query(b[i] + 1, n);
        count.update(b[i], count[b[i]] + 1);
    }
    return res;
}
// 累積和
struct cumulative_sum {
    using lint = long long int;
    int sz;
    // data[i]:元の数列
    vector<lint> data;
    // cum[i]:[0,i)の和
    vector<lint> sum;
    // 要素数を指定して初期化
    cumulative_sum(const int _sz) : sz(_sz) {
        data.assign(sz, 0);
        sum.assign(sz + 1, 0);
    }
    lint& operator[](const int k) {
        return data[k];
    }
    // dataに基づいてsumを構築
    void build() {
        for (int i = 0; i < sz; i++) sum[i + 1] = sum[i] + data[i];
    }
    // [a,b)の和を求める
    lint query(const int a, const int b) {
        return sum[b] - sum[a];
    }
};

int main() {
    lint n, k;
    cin >> n >> k;
    cumulative_sum a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= k;
    }
    a.build();
    cout << n * (n + 1) / 2 - inversion_number(a.sum) << endl;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;

const int MOD = 1000000007;

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

    vector<vector<long long> > dp(H + 1, vector<long long>(W, 0));
    dp[0][0] = 1;

    rep(i, H) {
        for (int bit = 0; bit < 1 << (W - 1); bit++) {
            bool ok = true;
            for (int k = 0; k < W - 2; k++) {
                if ((bit & (1 << k)) && (bit & (1 << (k + 1)))) ok = false;
            }
            if (!ok) continue;

            rep(j, W) {
                int nj = j;
                if (bit & (1 << j)) {
                    nj = j + 1;
                } else if (j > 0 && bit & (1 << (j - 1))) {
                    nj = j - 1;
                }
                dp[i + 1][nj] += dp[i][j];
                dp[i + 1][nj] %= MOD;
            }
        }
    }

    cout << dp[H][K - 1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30) - 1;
int main()
{
    int N, M, P;
    int D[20009];
    int minv = INF;
    cin >> N >> M >> P; M++;

    D[0] = P;
    D[M] = D[0] + N;
    for ( int i = 1; i < M; i++ ) {
        cin >> D[i];
        D[i + M] = D[i] + N;
    }

    sort(D, D + M * 2);
    for ( int i = 0; i < M; i++ ) {
        int l = D[i + 1], r = D[i + M];
        int p = P;
        if ( p < l ) p += N;
        minv = min( { minv, r - l + (r - p), r - l + (p - l) } );
    }

    cout << minv * 100 << endl;

    return ( 0 );
}



Measured memory_bytes: 3212
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int a,b;
int s[2000001] ;
int main()
{
    for(int i=0;i<2000001;i++)
    	s[i]=-1000000+i;
	cin>>a>>b;
	for(int i=1000000+b-a+1;i<=1000000+b+a-1;i++)
		cout<<s[i]<<" ";
}

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

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

    // N個の要素の配列で初期化
    vector<int> vec(N);
    for(int i=0; i<N; ++i) cin >> vec.at(i);

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

    bool flg = true;

    for(int i=0; i<(N-1); ++i){
        if(vec.at(i) == vec.at(i+1)) flg = false;
    }

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int H,W,N;cin >> H >> W >> N;
  H = max(H,W);
  cout << (N+H-1)/H << endl;
  return 0;
}


Measured memory_bytes: 256
/*Lower_Rating*/
/*NIKKEI-2 A*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<map>
using namespace std;

#define LL long long
#define MAXN 100000
#define MAXM 2000000
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
#define INF 1000000000000000000
#define mem(x,p) memset(x,p,sizeof(x))

LL read(){
  LL x=0,F=1;char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
  return x*F;
}

int add(int x,int y){return (x+y>=MOD)?x+y-MOD:x+y;}
int dec(int x,int y){return (x-y<0)?x-y+MOD:x-y;}
int mul(int x,int y){return 1LL*x*y%MOD;}

int n,a,b,c;
int main()
{
    n=read();
    printf("%d",(n-1)/2);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long 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)
{
    string s;
    cin >> s;
    set<string> st;
    ll n = s.size();

    if(n == 1){
        cout<<1<<endl;
        return 0;
    }
    if(n == 2){
        if(s[0] == s[1]) cout<<1<<endl;
        else cout<<2<<endl;
        return 0;
    }

    ll dp[n]{};
    dp[0] = 1;
    if(s[0] == s[1]) dp[1] = 1;
    else dp[1] = 2;
    if(s[0] != s[1] && s[1] != s[2]) dp[2] = 3;
    else dp[2] =2;
    for(int i=3; i<n; i++){
        if(s[i-1] == s[i]) dp[i] = dp[i-3] + 2;
        else dp[i] = dp[i-1] + 1;
    }

    cout << dp[n-1] << endl;
    return 0;
}

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

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) {
    init(newn);
  }
  void init(int newn) {
    n = 1;
    while(n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while(k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for(int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) vl = f(vl, dat[l++]);
      if(r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};

long long n;
vector<long long> x, id;

long long solve();

int main() {
  cin >> n;
  x.resize(n);
  for(int i = 0; i < n; ++i) cin >> x[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = n * (n + 1) / 2;
  auto f = [&](long long l, long long r) {
    return max(l, r);
  };
  auto idf = [](long long l, long long r) {
    return x[l] < x[r];
  };
  id.resize(n);
  for(int i = 0; i < n; ++i) id[i] = i;
  sort(id.begin(), id.end(), idf);
  SegmentTree<long long> seg(n, f, 0);
  for(int i = 0; i < n; ++i) {
    seg.update(id[i], i + 1 + seg.query(0, id[i]));
  }
  return res - seg.query(0, n);
}


Measured memory_bytes: 6580
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){
    int X,K,D;
    cin>>X>>K>>D;
    X=abs(X);
    if(X/D<K){
        int c=K-X/D;
        X=X%D;
        if(c%2==1) X=abs(X-D);
    }
    else X=X-D*K;

    cout<<X<<endl;
}
//1000000000000000
//1000000000000000
//1000000000000000


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

int main() {
  int N, D, i;
  double *x, *y;
  double *distance;
  int count = 0;

  scanf("%d%d", &N, &D);

  x = malloc(sizeof(double *) * N);
  y = malloc(sizeof(double *) * N);
  distance = malloc(sizeof(double *) * N);

  for (i = 0; i < N; i++) {
    scanf("%lf%lf", &x[i], &y[i]);
  }
  for (i = 0; i < N; i++) {
    distance[i] = sqrt((x[i] * x[i]) + (y[i] * y[i]));
    if (distance[i] <= D) count++;
    // printf("%d %d %f\n", x[i], y[i], distance[i]);
  }

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

  free(x);
  free(y);
  free(distance);
  return 0;
}

Measured memory_bytes: 6704
// Author : Epsilon573
// If it works, don't touch it.

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ll mod  = 1e9+7;
const ld eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf  = LLONG_MAX;
const ll minf = LLONG_MIN;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cerr << #x << " " << x << endl

ll func(ll n)
{
    return n*(n+1)/2;
}

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

    ll n,ans = 0;
    cin >> n;

    map<ll,ll> m;

    for(ll i=2 ; i*i <= n ; ++i)
    {
        while(n%i==0)
        {
            m[i]++;
            n /= i;
        }
    }

    if(n>1) m[n]++;

    for(auto x : m)
    {
        ll freq = x.second;

        ll l=0 , r=freq;
        while( l<r )
        {
            ll mid = (l+r+1)/2;

            if(func(mid) == freq) 
            {
                l = r = mid; break;
            }
            if( func(mid) > freq )
            {
                r = mid - 1;
            }
            else
                l = mid;
        }

        ans += l;
    }

    cout << ans;

    return 0;
} 

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

#define ff first
#define ss second
using namespace std;
#define maxn 2000006
#define pb push_back
#define ll long long
#define lll __int128
#define vll vector<ll>
#define mll map<ll,ll>
#define MOD 1000000007
#define pll pair<ll,ll>
#define ull unsigned long long
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
inline void fastio() {ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);}

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



int main() {
	fastio();

	ll n; cin >> n;
	vector<ll> l(n); f(i, 0, n - 1) cin >> l[i];
	sort(l.begin(), l.end());
	ll ans = 0;
	f(i, 0, n - 3) {
		f(j, i + 1, n - 2) {
			ll ind = lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin();
			ans += (n - ind);
		}
	}

	cout << ((n * (n - 1) * (n - 2)) / 6) - ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<limits.h>
using namespace  std;
typedef long long int ll;
typedef long double ld;
ll dp[3003][3003];
int main()
{
	string a;
	string b;
	cin>>a;
	cin>>b;
	ll n=a.length();
	ll m=b.length();
	//fillv(dp,0);
	for (ll i=0;i<=n;i++)
		dp[i][0]=0;
	for (ll i=0;i<=m;i++)
		dp[0][i]=0;
	 stack <char> s;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			if(a[i-1]==b[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	ll i=n;
	ll j=m;
	// cout<<dp[n][m];
	while(i>=1&&j>=1)
	{
		if(a[i-1]==b[j-1])
		{
			s.push(a[i-1]);
			i--;
			j--;
		}
		else
		{
		if(dp[i-1][j]>dp[i][j-1])
			i--;
		else 
			j--;
		}
		
	}
	while(!s.empty())
	{
		cout<<s.top();
		s.pop();
	}
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<20;


int main(){
    int n;cin >> n;
    vector<P> v;
    for (int i = 0; i < n; i++) {
        LL x,y;
        cin >> x >> y;
        v.pb(P(x+y,x-y));
    }
    for (int i = 0; i < n-1; i++) {
        if(abs(v[i+1].fs)%2!=abs(v[i].fs)%2){
            puts("-1");
            return 0;
        }
    }
    int m;
    vector<LL> d;
    if(v[0].fs%2){
        m = 31;
        cout << m << endl;
        for (int i = 0; i < m; i++) {
            cout << (1LL<<i) << " ";
            d.pb(1LL<<i);
        }
        puts("");
    }
    else{
        m = 32;
        cout << m << endl;
        cout << 1 << " ";
        d.pb(1);
        for (int i = 0; i < m-1; i++) {
            cout << (1LL<<i) << " ";
            d.pb(1LL<<i);
        }
        puts("");
    }
    for (int i = 0; i < n; i++) {
        vector<bool> x(m),y(m);
        LL s = v[i].fs,t = v[i].sc;
        LL ssum=0,tsum=0;
        for (int j = m-1; j >= 0; j--) {
            if(ssum - s <= 0){
                ssum += d[j];
                x[j] = true;
            }
            else{
                ssum -= d[j];
                x[j] = false;
            }
            if(tsum - t <= 0){
                tsum += d[j];
                y[j] = true;
            }
            else{
                tsum -= d[j];
                y[j] =false;
            }
        }
        LL a=0,b=0;
        for (int j = 0; j < m; j++) {
            if(x[j]&&y[j]) cout << "R";
            else if(x[j]&&!y[j]) cout << "U";
            else if(!x[j]&&y[j]) cout << "D"; 
            else cout << "L";
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 256