akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import bisect
INF = 10**10

n = int(input())
a = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)

ans = [0] * n
lis = [INF] * n
def dfs(p, v):
    place = bisect.bisect_left(lis, a[v])
    val = lis[place]
    lis[place] = a[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(v, nv)
    lis[place] = val

dfs(-1, 0)
for item in ans:
    print(item)

Measured memory_bytes: 224964
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <queue>
#include <unordered_map>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
ll intpow(ll N, ll P){
    if(P==0) return 1;
    if(P%2==0){
        ll t = intpow(N, P/2);
        return t*t;
    }
    return N * intpow(N, P-1);
}
ll modpow(ll N, ll P,ll k){
    if(P==0) return 1;
    if(P%2==0){
        ll t = modpow(N, P/2,k)%k;
        return t*t%k;
    }
    return N * modpow(N, P-1,k)%k;
}
ll modkai(ll n,ll m,ll k){//n*(n-1)*(n-2)*...(m+1)%k
    if(n == m)return 1;
    return modkai(n-1,m,k)*n%k;
}
ll mod_cnb(ll n,ll m,ll k){//nCm%k,kは十分大きい素数
  int m_=modkai(m,0,k);
  return modkai(n,n-m,k)*modpow(m_,k-2,k)%k;
}
ll gcd(ll n,ll m){
    ll n_ = max(n,m);
    ll m_ = min(n,m);
    if(n_%m_ == 0)return m_;
    return gcd(m_,n_%m_);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}
int main(){
    ll n;cin>>n;
    map<ll,vector<ll>>m;
    rep(i,n){
        ll a,b;cin>>a>>b;
        m[b].push_back(a);
    }
    ll d;
    auto itr=m.end();
    itr--;
    d=itr->first;
    while(itr!=m.begin()){
        ll sum=0;
        rep(i,itr->second.size())sum+=itr->second[i];
        itr--;
        if(d-itr->first >= sum)d=itr->first;
        else d-=sum;
        }
    ll sum=0;
    rep(i,itr->second.size())sum+=itr->second[i];
    if(d-sum>=0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 22144
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n;
long long a[100010],b[100010];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    sort(a,a+n);
    b[(n-1)/2]=a[0];
    int l,r,ll,rr;
    l=r=(n-1)/2;
    ll=1;rr=n-1;
    int cnt=0;
    while(ll<=rr)
    {
        if(cnt%4==0)
            b[++r]=a[rr--];
        else if(cnt%4==1)
            b[--l]=a[rr--];
        else if(cnt%4==2)
            b[++r]=a[ll++];
        else b[--l]=a[ll++];
        cnt++;
    }
    long long ans1=0;
    for(int i=0;i<n-1;i++)
        ans1+=abs(b[i+1]-b[i]);
    b[(n-1)/2]=a[n-1];
    l=r=(n-1)/2;
    ll=0;rr=n-2;
    cnt=0;
    while(ll<=rr)
    {
        if(cnt%4==0)
            b[++r]=a[ll++];
        else if(cnt%4==1)
            b[--l]=a[ll++];
        else if(cnt%4==2)
            b[++r]=a[rr--];
        else b[--l]=a[rr--];
        cnt++;
    }
    long long ans2=0;
    for(int i=0;i<n-1;i++)
        ans2+=abs(b[i+1]-b[i]);
    printf("%lld\n",max(ans1,ans2));
    return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>
#include <string.h>
#define N 100005
typedef struct a{
  char name[100];
  int t;
}A;

A Q[N];
int head=0,tail=0,n,cnt=0;

void enqueue(A x){
  Q[tail]=x;
  tail=(tail+1)%N;
}
A dequeue(){
  A x = Q[head];
  head = (head+1)%N;
  return x;
}
int minimum(int a,int b){
  if(a>b)return b;
  else return a;
}

int main() {
  A u;
  int elaps=0,c;
  int i,q;
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }
  head=1;
  tail=n+1;
  while(head!=tail){
    u=dequeue();
    c=minimum(q,u.t);
    u.t -= c;
    elaps  += c;
    if(u.t > 0)enqueue(u);
    else printf("%s %d\n",u.name,elaps);
  }
  return 0;
}



Measured memory_bytes: 11856
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main() {
  int n;
  scanf("%d", &n);
  v1i v(n), u;
  rep(i, n) cin >> v[i];
  u = v;
  sort(u.begin(), u.end());
  rep(i, n){
    if(lower_bound(u.begin(), u.end(), v[i]) - u.begin() < n/2) printf("%d\n", u[n/2]);
    else printf("%d\n", u[n/2-1]);
  }
  return 0;
}

Measured memory_bytes: 3712
package main

import (
	"fmt"
	"math"
)

func main()  {
	var a, b, c, d int
	fmt.Scan(&a, &b, &c, &d)
	if AbsInt(a, c) <= d || AbsInt(a, b) <= d && AbsInt(b, c) <= d {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func AbsInt(n1 int, n2 int) int {
	return int(math.Abs(float64(n1 - n2)))
}


Measured memory_bytes: 512
n = int(input())
h = [int(num) for num in input().split()]
g = [0] * n

c = 0
g[0] = 0
for i in range(1,n):
    if h[i] <= h[i-1]:
        c += 1
    else:
        c = 0
    g[i] = c
    
print(max(g))

Measured memory_bytes: 14252
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static long cnt=0;
	public static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception {
		solution(args);
		if(in!=null){
			in.close();
		}
		pw.flush();
		pw.close();
	}

	public static void solution(String[] args) throws Exception{

		int K = nextInt();
		String S=nextString();

		if(S.length()<=K){
			System.out.println(S);
		}else{
			System.out.println(S.substring(0,K)+"...");
		}

	}


	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}

}



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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
int a, b; cin >> a >> b;
 cout << max({a+b, a-b, a*b});
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
int p[1001];
int abs(int x)
{
	return (x>=0? x:(-x));
}
int main()
{
	int x,n,a;
	int js=-1,min=99999,tmp=9999;
	cin>>x>>n;
	rep(i,1,n)
	{
	cin>>a;
	p[a]++;
    }
	
	rep(i,0,101)
	{
		if(p[i]==0)
		{
			tmp=abs(x-i);
		//	cout<<tmp<<endl;
			if(tmp<min)
			{
				min=tmp;
				js=i;
			//	cout<<tmp<<endl;
			}
			if(tmp==min && js>i)
			{
				js=i;
			}
	}}
	
	cout<<js<<endl;
	
 } 

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

using namespace std;



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int M, D;
	int d1, d2;
	int Count = 0;
	cin >> M >> D;
	
	if (D >= 20) {
		d1 = D % 10;
		d2 = (D - d1) / 10;
		
		while (d2 >= 2) {
			for (int i = d1; i > 1; i--){
				if (i*d2 <= M) {
					Count++;
				}
			}
			d2--;
			d1 = 9;
		}
	}
	cout << Count << endl;
}

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

struct UnionFind{
  vector<int> p;
  UnionFind(int n){
    p.resize(n);
    for(int i=0; i<n; i++)  p[i] = i;
  }
  int find(int x){
    if(p[x] == x)  return x;
    return p[x] = find(p[x]);
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)  return;
    p[x] = y;
  }
};

int main(){
  int n;  cin >> n;
  vector<tuple<int, int, int>> xyn(n);  // <0>:x  <1>:y  <2>:idenfi.. number
  vector<vector<pair<int, int>>> g(n);  // first:cost   second:to
  for(int i=0; i<n; i++){
    cin >> get<0>(xyn[i]) >> get<1>(xyn[i]);
    get<2>(xyn[i]) = i;
  }
  vector<tuple<int, int, int>> edge;  // 0:cost  1:from  2:to
  sort(xyn.begin(), xyn.end(), [](auto &a, auto &b){ return get<0>(a) < get<0>(b);});
  for(int i=1; i<n; i++){
    //    g[get<2>(xyn[i-1])].push_back({get<0>(xyn[i])-get<0>(xyn[i-1]), get<2>(xyn[i])});
    //    g[get<2>(xyn[i])].push_back({get<0>(xyn[i])-get<0>(xyn[i-1]), get<2>(xyn[i-1])});
    edge.push_back({get<0>(xyn[i])-get<0>(xyn[i-1]), get<2>(xyn[i-1]), get<2>(xyn[i])});
  }
  sort(xyn.begin(), xyn.end(), [](auto &a, auto &b){ return get<1>(a) < get<1>(b);});
  for(int i=1; i<n; i++){
    //    g[get<2>(xyn[i-1])].push_back({get<1>(xyn[i])-get<1>(xyn[i-1]), get<2>(xyn[i])});
    //    g[get<2>(xyn[i])].push_back({get<1>(xyn[i])-get<1>(xyn[i-1]), get<2>(xyn[i-1])});
    edge.push_back({get<1>(xyn[i])-get<1>(xyn[i-1]), get<2>(xyn[i-1]), get<2>(xyn[i])});
  }
  sort(edge.begin(), edge.end());
  long ans = 0;
  UnionFind uf(n);
  for(auto nowe : edge){
    if(uf.find(get<1>(nowe)) == uf.find(get<2>(nowe)))  continue;
    uf.unite(get<1>(nowe), get<2>(nowe));
    ans += get<0>(nowe);
  }

  //  for(int i=0; i<n; i++)
  //    cout << get<0>(xyn[i]) << " " << get<1>(xyn[i]) << get<2>(xyn[i]) << endl;

  cout << ans << endl;

  return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  for(int i=0; i<n; i++) cin >> p[i];
  int ans=0;
  for(int i=0; i<n-2; i++){
    vector<int> a(3);
    a[0] = p[i];
    a[1] = p[i+1];
    a[2] = p[i+2];
    sort(a.begin(), a.end());
    if(a[1] == p[i+1]){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


def dfs(v):
    visited[v] = 1
    for v2 in range(N):
        if graph[v][v2]==0 or visited[v2]==1:#vとv2が隣接していない or すでに訪れている場合
            continue
        dfs(v2)#隣接していて、まだ訪れていない場合


ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited = [0] * N

    dfs(0)

    bridge = 0
    if sum(visited) < N :
        bridge = 1
        ans+=1
        
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

print(ans)

Measured memory_bytes: 41308
S = input()
snum = len(S)
N = snum +1
Nar = [0 for i in range(N)]

for i in range(snum):
    if S[i] == '<':
        Nar[i+1] = Nar[i] + 1

for i in reversed(range(N-1)):
    if S[i] == '>':
        Nar[i] = max(Nar[i],Nar[i+1]+1)
sum = 0
for i in Nar:
    sum += i
print(sum)

Measured memory_bytes: 24096
A,B,C,D = map(int,input().split())

if (D-A)*(B-C)<=0:
    print(0)
    exit()
elif A<=C and D<=B:
    print(D-C)
    exit()
elif C<=A and B<=D:
    print(B-A)
    exit()
else:
    print(min(D-A,B-C))

Measured memory_bytes: 3060
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      s: chars,
    }

    if n%2 == 1 {
        return puts!("{}\n", "No");
    }

    for i in 0..n/2 {
        if s[i] != s[i + n/2] {
            return puts!("{}\n", "No");
        }
    }
    puts!("{}\n", "Yes");
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <stdexcept>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define debug(a) cout << (a) << endl
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;
template <class T>
bool chmax(T &a, const T &b)
{
	if (a < b)
	{
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
	if (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}

ll M = 1000000007;

void solve()
{
	long double a,b,h,m;
	cin>>a>>b>>h>>m;
	if(h>12){
		h-=12;
	}
	long double radh=(long double)h*M_PI/6.0+(long double)m*M_PI/360.0;
	long double radm=(long double)m*M_PI/30.0;

	long double theta=max(radh,radm)-min(radh,radm);
	long double c2=a*a+b*b-(long double)2.0*b*a*cos((long double)theta);
	//cout<<cos((long double)theta/180*M_PI)<<endl;
	printf("%.20Lf\n",sqrt((long double)c2));

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}


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

int main(){
	int n, w0, v, w;
	cin >> n >> w0;
	vector<int> sum(w0+1);
	rep(i, n){
		cin >> v >> w;
		rep(j, w0+1-w) sum[j+w] = max(sum[j+w], sum[j] + v);
		rep(j, w0+1) sum[j] = max(sum[j], j/w * v);
	}
	cout << sum[w0] << endl;
	return 0;
}


Measured memory_bytes: 3148
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <memory>
#include <functional>
#include <set>

using namespace std;

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef long long ll;
int main()
{

	string key[] = { "", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

	int n;

	cin >> n;
	for (int i = n; i > 0; i--){
		string str, tmp = "";
		cin >> str;

		int cnt = 0, temp = 0;
		string s = "";
		for (int i = 0; i < str.size(); i++){
			if (str[i] == '0'){
				if (!cnt) continue;
				tmp += key[temp][cnt - 1];
				temp = cnt = 0;
			}
			else{
				temp = str[i] - '0';
				if ((cnt>2) && (temp == 2 || temp == 3 || temp == 4 || temp == 5 || temp == 6 || temp == 8)) cnt -= 3;
				else if ((cnt>3) && (temp == 7 || temp == 9)) cnt -= 4;
				else if ((cnt>4) && temp == 1) cnt -= 5;
				cnt++;
			}
		}
		cout << tmp << endl;
	}
	return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}

typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

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

  vector<int> p(n);
  for(int i = 0; i < n; i++) cin >> p[i];

  vector<int> dp(n+1);
  dp[p[0]] = 1;
  int ans = 1;
  for(int i = 1; i < n; i++) {
    dp[p[i]] = max(dp[p[i]], dp[p[i]-1]+1);
    ans = max(ans, dp[p[i]]);
  }

  cout << n-ans << endl;
}


Measured memory_bytes: 3456
#include <stdio.h>

#define LOVE 753

int myabs(int a,int b)
{
	if (a<b) return b-a;
	else return a-b;
}

int main(void)
{
	char s[12],i;
	int min=999,sub;
	scanf("%s",s);

	for (i=0;s[i+2]!='\0' && s[i+2]!='\n';i++) {
		sub = (s[i] - '0') * 100 + (s[i+1] - '0') * 10 + s[i+2] - '0';

		sub = myabs(LOVE,sub);
		if (min>sub) min = sub;
	}

	printf("%d\n",min);
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] p = new int[N];
    int count = 0;

   for(int i = 0; i < N; i++) {
	   p[i] = sc.nextInt();
   }

   for(int i = 0; i < N; i++) {
	  if(p[i] != i+1) {
		  count++;
	  }
   }
   if(count <= 2) {
	   System.out.println("YES");
   } else {
	   System.out.println("NO");
   }

  }
}

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

string s;
string sub() {
  if (s == "zyxwvutsrqponmlkjihgfedcba") return "-1";
  if (s.size() < 26) {
    for (char c = 'a'; c <= 'z'; ++c) {
      if (s.find(c) == string::npos) {
        return s + c;
      }
    }
  }
  
  string t(s);
  next_permutation(t.begin(), t.end());
  
  string ret;
  for (int i = 0; i < t.size(); ++i) {
    ret += t[i];
    if (s[i] != t[i]) break;
  }
  return ret;
}

int main() {
  cin >> s;
  cout << sub() << endl;
}


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

int main()
{
    cin.tie(0); 
    ios::sync_with_stdio(false);

    string S;
    cin >> S; 

    string st;
    for (int i = 0; i < S.length(); ++i){
        st += "x";
    }

    cout << st << "\n";

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=1000002;
long long calc[1201],n;

int main()
{
    read(n);
    for(register long long i=1;i<=120;++i) calc[i]=(long long)pow(i,5);
    for (register int i=0;i<=120;++i)
    {
        for (register int j=0;j<=120;++j)
        {
            if(calc[i]-calc[j]==n)
            {
                printf("%d %d",i,j);
                return 0;
            }
            if(calc[i]+calc[j]==n)
            {
                printf("%d %d",i,-j);
                return 0;
            }
            if(-calc[i]-calc[j]==n)
            {
                printf("%d %d",-i,j);
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define N 100001
#define INF 1e9
using namespace std;
typedef pair<int,int> P;
int n,m,A[N],Sum[20][N];


int cost(int idx,int i){return Sum[i][n]-(Sum[i][idx+Sum[i][n]]-Sum[i][idx]);}

int mem[1<<20],used[1<<20];
int dfs(int sta,int idx){
  if(sta==(1<<m)-1)return 0;
  if(used[sta]++) return mem[sta];
  int &res=mem[sta]=INF;
  for(int i=0;i<m;i++){
    if((sta>>i)&1)continue;
    res=min(res,cost(idx,i)+dfs(sta|(1<<i),idx+Sum[i][n]));
  }
  return res;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>A[i],A[i]--;

  for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
      Sum[i][j+1]+=Sum[i][j]+(A[j]==i);
  cout <<dfs(0,0)<<endl;
}

Measured memory_bytes: 19360
import itertools
n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)[1, 2, 7, 20, 30, 40]
A = list(itertools.accumulate(a))
#print(A)[1, 3, 10, 30, 60, 100]
cnt = 0
for i in range(n-1):
  s = A[i]
  #この条件を満たしていないとそれ以上他のスライムを取り込めない
  if s*2 < a[i+1] :
    cnt = i+1

print(n-cnt)    
      
    
    


Measured memory_bytes: 14428
x1, y1, x2, y2 = map(int,input().split())
dx,dy = x2-x1,y2-y1
dx,dy = -dy,dx
x3,y3 = x2+dx,y2+dy
dx,dy = -dy,dx
x4,y4 = x3+dx,y3+dy
print(x3,y3,x4,y4)


Measured memory_bytes: 38384
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18) + 1;
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll n, m;
vector<ll> x,y;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>m;
    vector<bool> used(n,false);
    vector<int> count(n,1);
    used[0]=true;
    for (int i = 0; i < m; i++)
    {
        ll temp,temp1;
        cin >> temp>>temp1;
        temp--;
        temp1--;
        x.push_back(temp);
        y.push_back(temp1);
        if(used[temp]){
            used[temp1]=true;
            count[temp1]++;
            count[temp]--;
            if(count[temp]==0){
                used[temp]=false;
            }
        }
        else{
            count[temp]--;
            count[temp1]++;
        }
    }
    ll ans = 0;
    rep(i,n){
        if(used[i])ans++;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 2420
h = [ [ [ 0 for x in range(0, 10) ] for y in range(0, 3) ] for z in range(0, 4) ]
for i in range(0, int(input())):
    b,f,r,v = map(int, input().split())
    h[b-1][f-1][r-1] += v
c = 1
for x in h:
    for y in x:
        print(" " + " ".join(map(str, y)))
    if c < 4:
        print("#" * 20)
    c += 1

Measured memory_bytes: 7720
using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            var list = new List<int>();
            int s;

            do
            {
                s = int.Parse(Console.ReadLine());
                list.Add(s);
            } while (s != 0);

            for (int i = 0; i < list.Count-1; i++)
            {
                Console.WriteLine("Case {0}: {1}", i+1, list[i]);
            }
        }
    }
}



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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


typedef pair<LL, LL> p;

const int V_MAX = 100010;
LL dp[110][V_MAX];

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

  LL w[n];
  LL v[n];
  REP (i, n) {
    cin >> w[i] >> v[i];
  }

  REP (i, n + 1) {
    REP (j, V_MAX) {
      dp[i][j] = INF;
    }
  }

  dp[0][0] = 0;

  REP (i, n) {
    REP (j, V_MAX) {
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      if (0 <= j - v[i]) {
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
      }
    }
  }

  LL ans = 0;
  REP (j, V_MAX) {
    if(dp[n][j] <= k) ans = j;
  }

  cout << ans << endl;
}


Measured memory_bytes: 80128
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
a2 = [i % 2 for i in a].count(0)
a4 = [i % 4 for i in a].count(0)
a0 = n - a2
a2 -= a4
if a2 == 0:
    if a0 <= a4+1:
        ans = "Yes"
    else:
        ans = "No"
else:
    if a0 <= a4:
        ans = "Yes"
    else:
        ans = "No"
print(ans)


Measured memory_bytes: 14252
#include<stdio.h>
int main() {
	int a, b, c, d;
	bool s = false;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	if (a <= c) {
		if (c - a <= d) {
			s = true;
		}
		else {
			if (b <= c) {
				if (a <= b) {
					if (b - a <= d) {
						if (c - b <= d) {
							s = true;
						}
					}
				}
			}
		}
	}
	if (c <= a) {
		if (a - c <= d) {
			s = true;
		}
		else {
			if (c <= b) {
				if (b <= a) {
					if (a - b <= d) {
						if (b - c <= d) {
							s = true;
						}
					}
				}
			}
		}
	}
	if (s == true) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cmath>
#include<bitset>
typedef long long ll;
#define PB	push_back
#define FOR(n)			for(int i = 0; i < n; ++i)
#define RFOR(n)			for(int i = n; i >= 0; --i)
#define FORR(start,end) for(int i = start; i < end; ++i)
#define COUT(n)			cout << n << " " << flush
#define vi(v)			vector<int> v
#define vii(v)			vector<pair<int,int>> v
#define mii(m)			map<int, int> m
#define msi(m)			map<string, int, less<>> m
#define mmsi(m)			multimap<string, int, less<>> m
#define mkp(a,b)		make_pair(a,b)
#define ALL(obj)		obj.begin(), obj.end()
#define PI 3.141592
#define MOD 1e9+7
using namespace std;

void solve() {
	int n, a[200000];
	int kill = 0, num = 1;
	cin >> n;
	FOR(n)
		cin >> a[i];

	for (int i = 0; i < n; ++i) {
		if (a[i] != num)
			kill++;
		else
			num++;
	}
	if (num != 1)
		cout << kill << endl;
	else
		cout << -1 << endl;
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 1024
import sys


def solve(n, ab):
    s = 0
    for a, b in zip(ab[0::2], ab[1::2]):
        if a == b:
            s += 1
        else:
            s = 0
        if s >= 3:
            return True
    return False


n, *ab = map(int, sys.stdin.buffer.read().split())

print('Yes' if solve(n, ab) else 'No')


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

int main() {
  int A, B;
  cin >> A >> B;

  if (A == B)
    cout << "Draw" << endl;
  else if (A == 1)
    cout << "Alice" << endl;
  else if (B == 1)
    cout << "Bob" << endl;
  else if (A > B)
    cout << "Alice" << endl;
  else if (A < B)
    cout << "Bob" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#define INF 1000000009
#define LINF 1000000000000000009
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmax(T &a, const T&b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T&b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

int main() {
	int n;
	string s;
	cin >> n >> s;
	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		if (s[i] == 'A'&&s[i + 1] == 'B'&&s[i + 2] == 'C') ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int sx = sc.nextInt();
		int sy = sc.nextInt();
		int tx = sc.nextInt();
		int ty = sc.nextInt();
		sc.close();

		StringBuilder sb = new StringBuilder();
		for (int i = sx; i < tx; i++) {
			sb.append('R');
		}
		for (int i = sy; i < ty; i++) {
			sb.append('U');
		}

		for (int i = sx; i < tx; i++) {
			sb.append('L');
		}
		for (int i = sy; i < ty; i++) {
			sb.append('D');
		}

		sb.append('D');
		for (int i = sx; i < tx + 1; i++) {
			sb.append('R');
		}
		for (int i = sy; i < ty + 1; i++) {
			sb.append('U');
		}
		sb.append('L');

		sb.append('U');
		for (int i = sx; i < tx + 1; i++) {
			sb.append('L');
		}
		for (int i = sy; i < ty + 1; i++) {
			sb.append('D');
		}
		sb.append('R');

		System.out.println(sb.toString());
	}
}


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

int main(){
  long i,N,a=0,b=0,c=0,p,ans=0;
  cin>>N;
  vector<long> plus(N),minus(N),zero(N);
  for(i=0;i<N;i++){
    scanf("%ld",&p);
    if(p>0){
      plus[a++]=p;
      ans+=p;
    }else if(p<0){
      minus[b++]=p;
      ans-=p;
    }else{
      zero[c++]=p;
    }
  }

  if(a*b>0){
    printf("%ld\n",ans);
    ans=minus[0];
    for(i=1;i<a;i++){
      printf("%ld %ld\n",ans,plus[i]);
      ans=ans-plus[i];
    }
    printf("%ld %ld\n",plus[0],ans);
    ans=plus[0]-ans;
    for(i=1;i<b;i++){
      printf("%ld %ld\n",ans,minus[i]);
      ans=ans-minus[i];
    }
    for(i=0;i<c;i++)printf("%ld 0\n",ans);

  }else if(c>0){
    printf("%ld\n",ans);
    ans=0;
    if(b>0){
      for(i=0;i<b;i++){
        printf("%ld %ld\n",ans,minus[i]);
        ans=ans-minus[i];
      }
      for(i=1;i<c;i++)printf("%ld 0\n",ans);
    }else if(a>0){
      for(i=1;i<a;i++){
        printf("%ld %ld\n",ans,plus[i]);
        ans=ans-plus[i];
      }
      printf("%ld %ld\n",plus[0],ans);
      ans=plus[0]-ans;
      for(i=1;i<c;i++)printf("%ld 0\n",ans);
    }else{
      for(i=1;i<c;i++)printf("0 0\n");
    }

  }else if(a>0){
    sort(plus.begin(),plus.end());
    printf("%ld\n",ans-plus[0]*2);
    ans=plus[0];
    for(i=2;i<a;i++){
      printf("%ld %ld\n",ans,plus[i]);
      ans=ans-plus[i];
    }
    printf("%ld %ld\n",plus[1],ans);
  }else{
    sort(minus.begin(),minus.end(),greater<long>());
    printf("%ld\n",ans+minus[0]*2);
    ans=minus[0];
    for(i=1;i<b;i++){
      printf("%ld %ld\n",ans,minus[i]);
      ans=ans-minus[i];
    }
  }
  return 0;
}

Measured memory_bytes: 4224
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let q = read::<usize>();
    let big_int = 1000_003;
    let fact = ModFactorial::new(1000_002, big_int).fact;
    for i in 0..q {
        let v = read_vec::<i64>();
        let (x, d, n) = (v[0], v[1], v[2]);
        let x_d = (x * mod_inverse(d, big_int)) % big_int;
        if d == 0 {
            println!("{}", pow_m(x, n, big_int));
        } else {
            let large_idx = (n + x_d - 1) as usize;
            let small_idx = (x_d - 1) as usize;
            if large_idx >= big_int as usize || large_idx == 0 {
                println!("0");
                continue;
            }
            let mut temp = fact[large_idx] * mod_inverse(fact[small_idx], big_int);
            temp %= big_int;
            temp *= pow_m(d, n, big_int);
            temp %= big_int;
            println!("{}", temp);
        }
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn pow_m(n: i64, mut p: i64, m: i64) -> i64 {
    let mut r = n;
    let mut ret = 1;
    while p > 0 {
        if p % 2 == 0 {
            r = r * r % m;
            p /= 2;
        } else {
            ret = ret * r % m;
            p -= 1;
        }
    }
    ret
}

fn extgcd(a: i64, b: i64, x: &mut i64, y: &mut i64) -> i64 {
    let mut d = a;
    if b == 0 {
        *x = 1;
        *y = 0;
    } else {
        d = extgcd(b, a % b, y, x);
        *y -= (a / b) * (*x);
    }
    return d;
}

fn mod_inverse(a: i64, m: i64) -> i64 {
    let mut x: i64 = 0;
    let mut y: i64 = 0;
    extgcd(a, m, &mut x, &mut y);
    (m + x % m) % m
}

struct ModFactorial {
    fact: Vec<i64>,
}

// returns n! under mod m
impl ModFactorial {
    fn new(n: i64, m: i64) -> ModFactorial {
        let mut fact = vec![1; n as usize + 1];
        for i in 2..fact.len() {
            fact[i] = (i as i64 * fact[i - 1]) % m;
        }
        ModFactorial { fact: fact }
    }
}


Measured memory_bytes: 13180
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	string s; cin>>s;
	int ans=0;
	rep(i,0,3) if(s[i]=='o')++ans;
	cout<<700+ans*100<<endl;
	
	return 0;
}

Measured memory_bytes: 3548
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main () {
	int n;
	scanf("%d",&n);
	vector<int> tbl(2*n);
	for (int i=0;i<2*n;i++) {
		scanf("%d",&tbl[i]);
	}
	sort(tbl.begin(),tbl.end());
	long long sum=0;
	for (int i=0;i<2*n;i+=2) {
		sum+=tbl[i];
	}
	printf("%lld\n",sum);
	return 0;
}


Measured memory_bytes: 256
// C.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	LL x;
	cin >> x;
	LL y = x / 11;
	LL ans = y * 2;
	x -= y * 11;
	if (x > 6) {
		ans += 2;
	} else if (x) {
		++ans;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
li1 = []
li2 = []
li3 = []
li4 = []
li5 = []
li6 = []
li7 = []
li8 = []

for i in range(n):
    x,y,z = map(int,input().split())
    li1.append(x+y+z)
    li2.append(x+y-z)
    li3.append(x-y+z)
    li4.append(-x+y+z)
    li5.append(x-y-z)
    li6.append(-x+y-z)
    li7.append(-x-y+z)
    li8.append(-x-y-z)

print(max(sum(sorted(li1,reverse = True)[:m]),sum(sorted(li2,reverse = True)[:m]),sum(sorted(li3,reverse = True)[:m]),sum(sorted(li4,reverse = True)[:m]),sum(sorted(li5,reverse = True)[:m]),sum(sorted(li6,reverse = True)[:m]),sum(sorted(li7,reverse = True)[:m]),sum(sorted(li8,reverse = True)[:m])))


Measured memory_bytes: 38512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
map<int,vector<int> > mp;
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i,n)cin >> a[i];
    rep(i,n){
        mp[i-a[i]].push_back(i);
    }
    ll sm = 0;
    rep(i,n){
        int s = a[i]+i;
        if(mp.find(s)!=mp.end()){
            auto &v = mp[s];
            sm += v.end()-upper_bound(v.begin(),v.end(),i);
        }
    }
    cout << sm << endl;
    return 0;
}

Measured memory_bytes: 23772
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
map<ll, ll>ins;
void facterize(ll n) {
	ll a = 2;
	while (n >= a * a) {
		if (n % a == 0) {
			ins[a]++;
			ins[a] = ins[a] % 1000000007;
			n /= a;
		}
		else {
			a++;
		}
	}
	ins[n]++;
}

vector<ll>relation[20], money(20, 1);
char s[110][110];
int dp[110][110];

int keta(int x) {
	int y = 0;
	while (x > 0) {
		y++;
		x /= 10;
	}
	return y;
}

int main() {
	string s;
	cin >> s;
	int n = s.length();
	string res;
	bool flag = false;
	map<char, int>mp;
	if (n != 26) {
		rep(i, n) {
			mp[s[i]]++;
		}
		for (char i = 'a';i <= 'z';++i) {
			mp[i]++;
		}
		for (auto p : mp) {
			char a = p.first;
			int x = p.second;
			if (x == 1) {
				s += a;
				break;
			}
		}
		cout << s << endl;
	}
	else {
		if (s == "zyxwvutsrqponmlkjihgfedcba") {
			cout << -1 << endl;
			return 0;
		}
		string ans;
		string x = s;
		next_permutation(x.begin(), x.end());
		rep(i, 26) {
			if (x[i] == s[i]) {
				ans += x[i];
			}
			else {
				ans += x[i];
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdint>
#include<algorithm>
int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N, Q; std::cin >> N >> Q;
  std::vector<int64_t> A(N);
  for(auto& Ai: A) std::cin >> Ai;
  int tma = (N+1)/2;
  std::vector<int64_t> ans(tma+1, 0), step(tma+1, 0);
  for(int i = 1; i < ans.size(); ++i) ans[i] = ans[i-1] + A[N-i];
  int j = N+1-tma*2;
  for(int i = 1; i < step.size(); ++i) { step[i] = step[i-1] + A[j]; j+=2; }
  for(int i = 0; i < ans.size(); ++i) ans[i] += step[tma-i];

  for(int q = 0; q < Q; ++q) {
    int64_t X; std::cin >> X;
    int l = A.end() - std::lower_bound(A.begin(), A.end(), X);
    int ok = (l+1)/2, ng = l+1;
    auto isOK = [&](int nt) {
      int64_t tmi = *(A.end()-nt);
      auto it = std::lower_bound(A.begin(), A.end(), X+X-tmi);
      int na = (A.end()-nt)-it;
      return na+1 >= nt;
    };
    while(ng - ok > 1) {
      int mid = (ok+ng)/2;
      if(isOK(mid)) ok = mid; else ng = mid;
    }
    std::cout << ans[ok] << "\n";
  }
  return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>

#define MOD 1000000007
#define ll long long

using namespace std;

vector <ll> A;
int main(){
  ll inp;
  
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  for(ll i = 0;i< 4;i++){
    cin >> inp;
    A.push_back(inp);
  }

  if(A[1] <= A[2]) cout << "0" << endl;
  else if(A[3] <= A[0]) cout << "0" << endl;
  else{
    sort(A.begin(), A.end());
    cout << A[2]-A[1] << endl;
  }
  
  
  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)
    ind = 0
    for b, c in BC:
        for i in range(b):
            if ind == N or A[ind] >= c:
                break
            A[ind] = c
            ind += 1
    print(sum(A))


if __name__ == '__main__':
    main()

Measured memory_bytes: 23740
a=[]
for i in range(3):
    x,y,z=map(int,input().split())
    a.append(x)
    a.append(y)
    a.append(z)
b=int(input())
for i in range(b):
    c=int(input())
    if a.count(c)==1:
        a[a.index(c)]=0
if a[0]==a[1]==a[2] or a[3]==a[4]==a[5] or a[6]==a[7]==a[8]:
    print("Yes")
elif a[0]==a[3]==a[6] or a[1]==a[4]==a[7] or a[2]==a[5]==a[8]:
    print("Yes")
elif a[0]==a[4]==a[8] or a[2]==a[4]==a[6]:
    print("Yes")
else:
    print("No")

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

const int maxn=200003;

int n,a[maxn],k,res=1;

#define lson(ix) (ix<<1)
#define rson(ix) ((ix<<1)|1) 

int mn[maxn<<2],mx[maxn<<2],g[maxn];
void pushup(int id){
	mn[id]=min(mn[lson(id)],mn[rson(id)]);
	mx[id]=max(mx[lson(id)],mx[rson(id)]);
}

void build(int id,int l,int r){
	if(l==r){
		mn[id]=a[l];
		mx[id]=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(lson(id),l,mid);
	build(rson(id),mid+1,r);
	pushup(id); 
}
const int inf=0x3f3f3f3f;
int getmin(int id,int l,int r,int L,int R){
	if(l>=L&&r<=R)return mn[id];
	if(l>R||L>r)return inf;
	int mid=(l+r)/2;
	return min(getmin(lson(id),l,mid,L,R),
			   getmin(rson(id),mid+1,r,L,R));
}
int getmax(int id,int l,int r,int L,int R){
	if(l>=L&&r<=R)return mx[id];
	if(l>R||L>r)return 0;
	int mid=(l+r)/2;
	return max(getmax(lson(id),l,mid,L,R),
			   getmax(rson(id),mid+1,r,L,R));
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	g[1]=1;
	for(int i=2;i<=n;++i){
		if(a[i]>a[i-1])g[i]=g[i-1]+1;
		else g[i]=1;
	}
	for(int i=1;i<=n;++i)
		g[i]=(g[i]>=k);
	build(1,1,n);
	bool flag=g[k];
	for(int Mn,Mx,i=k+1;i<=n;++i){
		Mn=getmin(1,1,n,i-k,i-1);
		Mx=getmax(1,1,n,i-k,i-1);
		if(a[i-k]>Mn||a[i]<Mx){
			if(!(g[i]&&flag))
				++res;
		}
		if(g[i])flag=1;
	}
	printf("%d\n",res);
	return 0;
}



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

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			Question.Exec();
		}
	}

	public static class Question
	{
		public static int Calc(int value)
		{
			int total = 0;
			int ans = value / 10000;
			total += ans;
			value -= 10000 * ans;
			ans = value / 1000;
			total += ans;
			value -= 1000 * ans;
			ans = value / 100;
			total += ans;
			value -= 100 * ans;
			ans = value / 10;
			total += ans;
			value -= 10 * ans;
			total += value;

			return total;
		}
		
		public static void Exec()
		{
			var array = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
			int n = array[0];
			int a = array[1];
			int b = array[2];

			int total = 0;
			for (var i = 1; i <= n; ++i) {
				int answer = Calc(i);
				if (a <= answer && answer <= b) {
					total += i;
				}
			}

			Console.WriteLine($"{total}");

			Console.ReadKey();
		}
	}
}

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

int X;
int a,b,c;
bool t = true;      
int main() {
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> X;
    

    int res = 0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                int total = 500*i+100*j+50*k;
                if (total==X)++res;
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int d, g;
    cin >> d >> g;
    vector<pair<int, int>> vs(d);
    for (auto& v : vs)
    {
        cin >> v.first >> v.second;
    }

    vector<int> order;
    for (int i = 0; i < d; i++)
    {
        order.push_back(i);
    }
    int min_num = 100000000;

    do
    {
        int num = 0;
        int score = 0;
        for (auto o : order)
        {
            const int single_score = (o + 1) * 100;
            const int num_to_solve = min(vs[o].first, (g - score + single_score - 1) / single_score);
            score += single_score * num_to_solve;
            num += num_to_solve;
            if (num_to_solve == vs[o].first)
            {
                score += vs[o].second;
            }
            if (score >= g)
            {
                min_num = min(min_num, num);
                break;
            }
        }
    } while (next_permutation(order.begin(), order.end()));
    cout << min_num << endl;
}


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

using namespace std;

typedef long long int ll;
typedef long long unsigned int llu;
#define tc long long int t; cin>>t; while(t--)
#define  sync ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define mpi unordered_map<ll, ll>
#define mpc unordered_map<char, ll>
#define map_loop(it,m) for(auto it = m.begin(); it!=m.end(); it++)
#define rep(i,n) for(ll i=0;i<n;i++)


int main(){
  
  sync;
  string s;
  cin>>s;
  if(s[0]=='7'||s[1]=='7'||s[2]=='7')
  cout<<"Yes"<<endl;
  else
  cout<<"No"<<endl;
    
}






















Measured memory_bytes: 3652