akhauriyash/Code-Regression huggingface dataset:
N,M,X = map(int,input().split())
A =  list(map(int,input().split()))
#print(A)
left = []
right = []
for i in A:
    if i > X:
        right.append(i)
    else:
        left.append(i)
    
#print(right,left)
print(min(len(right),len(left)))

Measured memory_bytes: 9164
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc080/tasks/abc080_d

"""
import sys
from sys import stdin
from heapq import heappop, heappush, heappushpop
input = stdin.readline


def prep_programs(programs):
    # 同じチャンネルで連続録画する場合はまとめる
    channels = [[] for _ in range(31)]
    res = []

    for s, t, c in programs:
        channels[c].append([s, t])

    for i in range(1, 31):
        channels[i].append([-1, -1])

    for i in range(1, 31):
        prev_start = channels[i][0][0]
        for a, b in zip(channels[i], channels[i][1:]):
            if a[1] == b[0]:
                pass
            else:
                res.append([prev_start, a[1], i])
                prev_start = b[0]
    return res


def solve(programs, N, C):
    programs.sort()
    programs = prep_programs(programs)
    programs.sort()

    max_used = 1
    R = []

    heappush(R, 0)
    for s, t, c in programs:
        end_time = heappushpop(R, t)
        if end_time >= s:
            heappush(R, end_time)
            max_used = len(R)
    return max_used


def main(args):
    programs = []
    N, C = map(int, input().split())
    for _ in range(N):
        s, t, c = map(int, input().split())
        programs.append([s, t, c])
    ans = solve(programs, N, C)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

#define mp make_pair
#define ff first
#define ss second
#define pii pair <int,int>
#define pb push_back
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std ;
typedef long long ll ;


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n ;
	cin >> n;
	if(n%1000 == 0){
		cout << 0 ;
		return 0;
	}
	cout << 1000 - (n%1000) ;

	return 0 ;
}


Measured memory_bytes: 3560
import java.util.*;
import java.io.*;
public class Main {
	public static class Jewels implements Comparable<Jewels> {
		int c;
		long v;
		Jewels(){}
		Jewels(long v,int c) {
			this.c=c;
			this.v=v;
		}
		@Override
		public int compareTo(Jewels o) {
			if (o.v>v) return 1;
			if (o.v<v) return -1;
			return o.c-c;
		}
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n=(int)in.nval;
		in.nextToken();
		int k=(int)in.nval;
		ArrayList<Integer>[] arr=new ArrayList[k+1];
		for (int i=1;i<=k;++i) arr[i]=new ArrayList<>();
		for (int i=0;i<n;++i) {
			in.nextToken();
			int c=(int)in.nval;
			in.nextToken();
			int v=(int)in.nval;
			arr[c].add(v);
		}
		ArrayList<Jewels> J=new ArrayList<>();
		PriorityQueue<Jewels> X=new PriorityQueue<>();
		PriorityQueue<Jewels> Y=new PriorityQueue<>();
		PriorityQueue<Jewels> Z=new PriorityQueue<>();
		for (int i=1;i<=k;++i) {
			arr[i].sort(new Comparator<Integer>() {
				public int compare(Integer a,Integer b) {
					return b-a;
				}
			});
			J.add(new Jewels(arr[i].get(0)+arr[i].get(1),i));
			J.add(new Jewels(arr[i].get(0)+arr[i].get(1),i));
			for (int j=2;j<arr[i].size();++j) J.add(new Jewels(arr[i].get(j)*2,i));
			Y.add(new Jewels(arr[i].get(0)+arr[i].get(1),i));
			if (arr[i].size()>=3) Z.add(new Jewels(0L+arr[i].get(0)+arr[i].get(1)+arr[i].get(2),i));
		}
		J.sort(null);
		long min_value=Long.MAX_VALUE;
		long min_pair=Long.MAX_VALUE;
		long sum=0;
		int[] C=new int[k+1];
		boolean[] col=new boolean[k+1];
		for (int i=0;i<n;++i) {
			long value=J.get(i).v;
			int color=J.get(i).c;
			long ans=-2;
			if (C[color]==0) {
				while (!Y.isEmpty()&&col[Y.peek().c]) Y.poll();
				while (!Z.isEmpty()&&col[Z.peek().c]) Z.poll();
				if (!X.isEmpty()) ans=Math.max(ans,sum+X.peek().v);
				if (!Y.isEmpty()) ans=Math.max(ans,sum-min_value+Y.peek().v*2);
				if (!Z.isEmpty()) ans=Math.max(ans,sum-min_pair+Z.peek().v*2);
				col[color]=true;
			} else {
				ans=sum+value;
				if (C[color]==1) {
					for (int j=2;j<arr[color].size();++j)
						X.add(new Jewels(arr[color].get(j)*2,color));
					min_pair=value*2;
				} else {
					X.poll();
					min_value=value;
				}
			}
			++C[color];
			sum+=value;
			out.printf("%d\n",ans/2);
		}
		out.flush();
	}
}

Measured memory_bytes: 135556
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;


int main()
{
	FAST;
	string str;
	cin >> str;

	int a = 0;
	int b = str.size()-1;
	
	while(str[a] != 'A')
	    a++;
	while(str[b] != 'Z')
	   b--;
	cout << b-a+1;
	return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define iter(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end();++it)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = ~(1<<31);
const double pi = acos(-1);

vi edg[100020];

int main() {
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	rep(i,0,n-1) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		edg[a].push_back(b);
		edg[b].push_back(a);
	}
	int colors[100020];
	memset(colors,-1,sizeof(colors));
	vi fen,snu;
	fen.push_back(0);
	snu.push_back(n-1);
	int left = n;
	while(left != 0) {
		vi holdfen;
		rep(i,0,fen.size()) {
			if(colors[fen[i]] != -1) continue;
			colors[fen[i]] = 0;
			left--;
			rep(a,0,edg[fen[i]].size()) if(colors[edg[fen[i]][a]] == -1) {
				holdfen.push_back(edg[fen[i]][a]);
			}
		}
		fen = holdfen;
		vi holdsnu;
		rep(i,0,snu.size()) {
			if(colors[snu[i]] != -1) continue;
			colors[snu[i]] = 1;
			left--;
			rep(a,0,edg[snu[i]].size()) if(colors[edg[snu[i]][a]] == -1) {
				holdsnu.push_back(edg[snu[i]][a]);
			}
		}
		snu = holdsnu;
	}
	int s = 0, f = 0;
	rep(i,0,n) {
		if(colors[i] == 1) s++;
		else f++;
	}
	if(s < f) cout << "Fennec" << endl;
	else cout << "Snuke" << endl;

	return 0;
}

Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

char a, b;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> a >> b;
	if (a == 'H') {
		cout << b << endl;
	}
	else if (b == 'H') cout << 'D' << endl;
	else cout << 'H' << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int search(int A, int B, int C, int D)
{
    int b = B, c = C, d = D;
    int i;
    
    for(i = 7; i >= 0; i--)
    {
        b = B; c = C; d = D;
        switch(i)
        {
            case 0 : b = -B; c = -C; d = -D; break;
            case 1 : b = -B; c = -C; break;
            case 2 : b = -B; d = -D; break;
            case 3 : b = -B; break;
            case 4 : c = -C; d = -D; break;
            case 5 : c = -C; break;
            case 6 : d = -D; break;
            case 7 : break;
        }
        if((A+b+c+d) == 7)
            return i;
    }
    
    return i;
}

int main()
{
    int N;
    int A,B,C,D;
    char op[3] = "+++";
    
    scanf("%d", &N);
    A = N / 1000;
    B = (N - (A * 1000)) / 100;
    C = (N - (A * 1000) - (B * 100)) / 10;
    D = (N - (A * 1000) - (B * 100) - (C * 10));
    int i = search(A, B, C, D);
    
    switch(i)
    {
        case 0 : op[2] = '-'; op[1] = '-'; op[0] = '-'; break;
        case 1 : op[2] = '-'; op[1] = '-'; break;
        case 2 : op[2] = '-'; op[0] = '-'; break;
        case 3 : op[2] = '-'; break;
        case 4 : op[1] = '-'; op[0] = '-'; break;
        case 5 : op[1] = '-'; break;
        case 6 : op[0] = '-'; break;
        case 7 : break;
    }
    
    printf("%d%c%d%c%d%c%d=7\n", A,op[2],B,op[1],C,op[0],D);
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int a[N], b[N];

signed main()
{
	IO_OP;
	
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for(int i = 1; i <= m; i++) {
		cin >> b[i];
		b[i] += b[i - 1];
	}
	int mx = 0;
	for(int i = 0, j = m; i <= n; i++) {
		if(a[i] > k) break;
		while(a[i] + b[j] > k) j--;
		mx = max(mx, i + j);
	}
	cout << mx << endl;

}





Measured memory_bytes: 6736
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(Scanner())
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(Scanner())
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for bit := 0; bit < n; bit++ {
		for l := 0; l+bit < n; l++ {
			r := bit + l
			if r > 0 && l < n-1 {
				dp[l][r] = larger(a[l]-dp[l+1][r], a[r]-dp[l][r-1])
			} else if r > 0 {
				dp[l][r] = a[r] - dp[l][r-1]
			} else if l < n-1 {
				dp[l][r] = a[l] - dp[l+1][r]
			} else {
				dp[l][r] = a[l]
			}
		}
	}
	fmt.Println(dp[0][n-1])
}
func larger(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}


Measured memory_bytes: 56260
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	int a, b;

	scanf("%d %d", &a, &b);

	printf("%d\n", (b - 1 + a - 2) / (a - 1));

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> prl;
typedef vector<ll> vcl;
typedef map<ll,ll> mapl;
typedef unordered_map<ll,ll> umap;
#define pb push_back
#define all(v) v.begin(), v.end()
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repi(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;

int main() {
    // your code goes here
    ll n;
    cin >> n;
    if(n%10==3) cout << "bon" << endl;
    else if(n%10==0||n%10==1||n%10==6||n%10==8) cout << "pon" << endl;
    else cout << "hon" << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define N ((ll)(2e6+100))
#define MAX ((ll)(1e18+100))
#define ARRS ((ll)(2e6+100))
#define MOD ((ll)(1e9+7))
#define pb push_back

ll n,a,b;

int main(){
	cin>>n>>a>>b;
	if((b-a)%2==0)
		cout<<"Alice";
	else cout<<"Borys";
}


Measured memory_bytes: 256
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
  
using namespace std;

class Pr
{
  public:
   bool operator()(const int& x, const int& y) const {
     return x > y;
   }
};
  
int main(){
  int n,k;
  cin >> n >> k;
  long h[n];
  for(int i=0;i<n;i++)cin >> h[i];
    long sum = 0;
    long tmp = 0;
 
  sort(h,h+n,Pr());
  
  for(int j=k;j<n;j++){
    sum += h[j];
  }
  cout << sum << endl;
  
  return 0;
  
}

Measured memory_bytes: 2424
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
lenc = len(c)
a.sort()
c.sort()

from bisect import bisect_left,bisect_right
ret = 0
for i in b:
    ret += bisect_left(a,i) * (lenc - bisect_right(c,i))
print(ret)

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

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

long long MOD = 1000000000 + 7;

ll N, M, X;
vector<ll> C;
vector<vector<ll>> A;

ll min_val = 1000000000000000000;

void solve(vector<int> v, int num){
  if(num < N) { 
    solve(v,num+1);
    v.push_back(num);
    solve(v,num+1);
  } else { 
    ll cost = 0;
    vector<ll> val(M,0);

    for(int i = 0; i < v.size(); i++){
      cost += C[v[i]];
      for(int j = 0; j < M; j++){
        val[j] += A[v[i]][j];
      }
    }

    for(int j = 0; j < M; j++){
      if(val[j] < X){
        return;
      }
    }
    if(min_val > cost){
      min_val = cost;
    }

  }


}

int main(){
  cout << setprecision(10);
  cin >> N >> M >> X;
  C.assign(N,0);
  A.assign(N, vector<ll>(M,0));

  for(int i = 0; i < N; i++){
    cin >> C.at(i);
    for(int j = 0; j < M; j++){
      cin >> A[i][j];
    }
  }

  vector<int> v;

  solve(v,0);

  if(min_val == 1000000000000000000){
    cout << -1 << endl;
  } else{
    cout << min_val << endl;
  }

}


Measured memory_bytes: 3640
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
long long n;
vector<bool> honest(15, true);
vector<vector<pair<long long, bool> > > a(15);
long long maxv = 0;

void dfs(long long x){
    if(x == n){
        long long count = 0;
        bool flag = true;
        for(long long i = 0; i < n; i++){
            if(honest[i] == true){
                count++;
                for(long long j = 0; j < a[i].size(); j++){
                    if(a[i][j].second != honest[a[i][j].first]){
                        count = 0;
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(flag == true){
            maxv = max(maxv, count);
        }
        return;
    }

    dfs(x+1);
    honest[x] = false;
    dfs(x+1);
    honest[x] = true;
}

int main(){
    cin >> n;

    for(long long i = 0; i < n; i++){
        long long A;
        cin >> A;
        for(long long j = 0; j < A; j++){
            long long x, y;
            cin >> x >> y;
            x--;
            if(y == 1){
                a[i].push_back(make_pair(x, true));
            }
            else{
                a[i].push_back(make_pair(x, false));
            }
        }
    }

    dfs(0);

    cout << maxv << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

int N, Q;
string s;
vector<char> t;
vector<int> d;

bool go_right(int pos) {
  REP(i,t.size()) {
    if(s[pos] == t[i]) {
      pos += d[i];
    }
    if(pos >= N) return true;
    if(pos < 0) return false;
  }
  return false;
}

bool go_left(int pos) {
  REP(i,t.size()) {
    if(s[pos] == t[i]) {
      pos += d[i];
    }
    if(pos < 0) return true;
    if(pos >= N) return false;
  }
  return false;
}

int main() {
  cin>>N>>Q;
  cin>>s;
  t = vector<char>(Q);
  d = vector<int> (Q);
  REP(i,Q) {
    string ts, ds; cin>>ts>>ds;
    t[i] = ts[0];
    if(ds[0] == 'L') d[i] = -1;
    else d[i] = +1;
  }
  int ans = 0;

  int left = 0, right = N;
  while(true) {
    if(left + 1 == right) break;
    int mid = (left + right) / 2;
    // midが右に出るか
    if(go_right(mid)) right = mid;
    else left = mid;
  }
  //  cout << left << " " << right << endl;
  ans = right;

  left = 0, right = N;
  while(true) {
    if(left + 1 == right) break;
    int mid = (left + right) / 2;
    // midが左に出るか
    if(go_left(mid)) left = mid;
    else right = mid;
  }
  //  cout << left << " " << right << endl;
  ans -= right;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1540
#include <iostream>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)

int dp[1001][1001];

int main(){
  int a;
  cin >> a;
  rep(i,a) {
  string x,y;

  cin >> x >> y;

  int n = x.size();
  int m = y.size();
  rep(i,n+1) dp[i][0] = 0;
  rep(j,m+1) dp[0][j] = 0;

  rep(i,n) {
    rep(j,m) {
      if(x[i] == y[j]) {
        dp[i + 1][j + 1] = max(dp[i][j] + 1,max(dp[i + 1][j],dp[i][j + 1]));
      } else {
        dp[i + 1][j + 1] = max(dp[i + 1][j],dp[i][j + 1]);
      }
    }
  }

  //rep(i,n+1) {
  //  rep(j,m+1)  {
  //    cout << dp[i][j] << " ";
  //  }
  //  cout << endl;
  //}
  cout << dp[n][m] << endl;
  }

}




Measured memory_bytes: 7056
n = int(input())
if n < 2 ** 1:
    print(2**0)
elif n < 2 ** 2:
    print(2 ** 1)
elif n < 2 ** 3:
    print(2 ** 2)
elif n < 2 ** 4:
    print(2 ** 3)
elif n < 2 ** 5:
    print(2 ** 4)
elif n < 2 ** 6:
    print(2 ** 5)
elif n <= 100:
    print(2 ** 6)


Measured memory_bytes: 3060
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
import std.format;

void main()
{
	auto ab = readln.split.to!(int[]), A = ab[0], B = ab[1];
	auto S = readln.chomp;

	if(count(S, '-') == 1 && S[A] == '-')
	{
		writeln("Yes");
	}
	else
	{
		writeln("No");
	}
}

Measured memory_bytes: 256
#include <cstdio>

int n, m;
int a[5];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) a[i] = -1;
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        if (~a[x] && a[x] ^ y) return puts("-1"), 0;
        a[x] = y;
    }
    if (n == 1) return printf("%d\n", ~a[1] ? a[1] : 0), 0;
    if (!a[1]) return puts("-1"), 0;
    for (int i = 1; i <= n; ++i) printf("%d", ~a[i] ? a[i] : (i == 1 ? 1 : 0));
    return 0;
}


Measured memory_bytes: 128
nax = 3005
dp = [[0 for _ in range(nax)] for _ in range(nax)]
mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c
def subtract(a, b):
    c = a - b
    if c < 0:
        c += mod
    return c

# dp[i][j] - the number of ways to put numbers in prefix of size 'i'
# such that the last number is 'j'
def main():
    n = int(raw_input())
    s = raw_input()    
    pref_sum = [0 for _ in range(n+1)]
    dp[1][1] = 1
    pref_sum[1] = 1
    for length in range(2, n+1):
        
        for b in range(1, length+1):
            if s[length-2] == '<':
                L = 1
                R = b-1
            else: # == '>'
                L = b
                R = length-1
            
            dp[length][b] = add(dp[length][b], subtract(pref_sum[R], pref_sum[L-1]))
            
            # for i in range(L, R+1):
            #     dp[length][b] = add(dp[length][b], dp[length-1][i])
                
            # for a in range(1, length):
            #     real_a = a
            #     if a >= b:
            #         real_a += 1
            #     if (real_a < b) != (s[length-2] == '<'):
            #         continue
            #     dp[length][b] = add(dp[length][b], dp[length-1][a])
        for b in range(1, length+1):
            pref_sum[b] = dp[length][b]
            pref_sum[b] = add(pref_sum[b], pref_sum[b-1])
        
    answer = 0
    for i in range(1, n+1):
        answer = add(answer, dp[n][i])
    answer = int(answer)
    print(answer)
    
main()

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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

class Graph{
    public:
    ll size;
    const ll INF = 1e15;

    struct edge{
        ll from, to, cost;
    };

    vector<ll> dist;
    vector<edge> edges;

    Graph(ll nv){
        size = nv;
        dist = vector<ll>(nv);
    }

    void add_edge(ll x, ll y, ll cost){
        edges.push_back((edge){x, y, cost});
    }

    // O(|V||E|)
    void bellman_ford(ll s){
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        while(true){
            bool update = false;
            for(edge e: edges){
                if(dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost){
                    dist[e.to] = dist[e.from] + e.cost;
                    update = true;
                }
            }
            if(!update) break;
        }
    }

    // if there is a negative cycle can reach from s
    bool negative_cycle(ll s){
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        for(ll i=0;i<size;i++){
            for(edge e: edges){
                // cout << e.from << " " << e.to << " " << e.cost << endl;
                if(dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost){
                    dist[e.to] = dist[e.from] + e.cost;

                    if(i == size - 1){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll v, e, r; cin >> v >> e >> r;
    Graph graph(v);
    for(int i=0;i<e;i++){
        ll s, t, d; cin >> s >> t >> d;
        graph.add_edge(s, t, d);
    }

    if(graph.negative_cycle(r)){
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }

    graph.bellman_ford(r);
    for(ll i=0;i<v;i++){
        ll ans = graph.dist[i];
        if(ans == graph.INF) cout << "INF" << endl;
        else cout << ans << endl;
    }
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
void File()
{
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
}
int countDivisors(long long  n){
int cnt = 0;
for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
        // If divisors are equal,
        // count only one
        if (n / i == i)
            cnt++;

        else // Otherwise count both
           cnt+=2;
    }
}
return cnt;
}

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pair<int,int> > vii;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef map<long, long> mll;
typedef set<int> si;
typedef set<string> sst;
typedef set<long> sl;
typedef long long ll;
typedef pair<int, int> pii;
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n-1);i >= 0;i--)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define mp(x,y)  	make_pair((x),(y))
#define pb(x)    	push_back((x))
#define all(v)  	((v).begin()),((v).end())
#define sz(x)  		((int) (x).size())
#define setzero(a)	memset(a,0,sizeof(a))
#define bits(a) 	__builtin_popcountll(a)
#define fr first
#define sc second
#define el      	 "\n"
#define pii pair<int, int>
#define sortva(v) sort(all(v))
#define sortvd(v) sort(v.rbegin(),v.rend())
#define sortaa(a,n) sort(a,a+n)
#define sortad(a,n) sort(a,a+n),reverse(a,a+n)
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1,v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1,v2,v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1,v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1,v2,v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
#define sfstr(v) scanf("%s", v);
#define sfs1(v) cin>>v;
#define ndl puts("")
#define SS stringstream
#define rep(i, a, n)	for(int i = a; i<=n; i++)
int const N = 3e3 + 9, MOD = 1e9+7 , oo = 1e9+7;
vector<vector<int>>adj(N);
vi start(N),finish(N);
int visited[N];


int arr[N];
int n;


string str;
int k,s,x,y,z,c;
int main()
{

    cin>>k>>s;
    for (x=0;x<=k;x++){
        for (y=0;y<=k;y++){
            z=s-x-y;
            if (z>=0&&z<=k)c++;
        }
    }


    cout<<c;













/*
*/













return 0;
}


Measured memory_bytes: 384
p = {"A":True, "B":False, "C": False}

while True:
    try:
        s, t = raw_input().split(",")
    except EOFError as e:
        break
    p[s], p[t] = p[t], p[s]

for i in p:
    if p[i]:
        print("%s" % (i, ))

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define V vector
#define L long
#define W V<L>
L E=70,M=2e17,i,a,b;W S(V<W>p){if(!E){return{1,0};}V<V<W>>T(2);for(W x:p){T[x[1]&1].push_back({x[0]/2,x[1]/2});if(x[0]&1){T[(x[1]+1)&1].push_back({x[0]/2,(x[1]+1)/2});}}for(L i;i<2;i++){L c=0;for(W x:T[!i]){L Q=(2*x[0]+x[1])%3;c^=Q+1;}if(!c){E--;W A=S(T[i]);A[0]*=2;A[1]*=2;A[1]+=i;return A;}}for(W&v:p){v[0]++;}W A=S(p);A[0]--;return A;}int main(){cin>>i;V<W>p(i);while(i--){cin>>a>>b;p[i]={a+M,b+M};}W x=S(p);cout<<x[0]-M<<" "<<x[1]-M;}

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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ll> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("a.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	vector<vector<int>> a(3, vector<int>(3));
	map<int, pair<int, int>> mp;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
		{
			int x;
			cin >> x;
			mp[x] = { i, j };
		}

	int n;
	cin >> n;
	vector<int> b(n);
	for (auto &i : b)
	{
		cin >> i;
		if (mp.count(i))
		{
			int x, y;
			tie(x, y) = mp[i];
			a[x][y] = 1;
		}
	}

	for (int i = 0; i < 3; ++i)
	{
		int s = 0, s1 = 0, s2 = 0;
		for (int j = 0; j < 3; ++j)
		{
			s += a[j][i];
			s1 += a[j][j];
			s2 += a[j][2-j];
		}

		if (accumulate(a[i].begin(), a[i].end(), 0) == 3 || s == 3 || s1 == 3 || s2 == 3)
		{
			cout << "Yes\n";
			return 0;
		}
	}

	cout << "No\n";

	return 0;
}


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

int main()
{
  int N, X;
  cin >> N >> X;
  int L[N];
  for (int i = 0; i < N; i++)
  {
    cin >> L[i];
  }

  int cnt = 1;
  int dist = 0;
  for (int i = 0; i < N; i++)
  {
    dist += L[i];
    if (dist <= X)
      cnt++;
    else
      break;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int n,m,i,j,k,found,ans;
    char s[1000001];
while(1){
    scanf("%d",&n);
    if(n==0) break;
    scanf("%d",&m);
    scanf("%s",s);


    i=0;ans=0;
    while(i<m-2*n){
	found=1;
	for(j=i;j<=i+2*(n-1);j=j+2){
	    if(s[j]=='O'||s[j+1]=='I'){
		found=0;
		break;
	    }
	}
	if(found==1){
	    if(s[j]=='I'){
	        ans++;
		i=i+2;
	    }else{
	        i=j-1;
	    }
        }else{
	    i=j+1;
	}
    }
    printf("%d\n",ans);
}

    return 0;
}

Measured memory_bytes: 1576
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            string s = Console.ReadLine();
            Console.WriteLine(s.Last() == '3' ? "bon" : new[] { '0', '1', '6', '8' }.Contains(s.Last()) ? "pon" : "hon");
        }
    }
}

Measured memory_bytes: 26132
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = pow(10,9) + 7;

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(){

    int N, M;
    cin >> N >> M;
    if(N == M){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <time.h>
#include <functional>
using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll beki(ll a, ll b) {
    ll tmp = 1;
    REP(i, b) tmp *= a;
    return tmp;
}

ll X;
ll A, B;
ll C[100010];

int main() {
    cin >> X;
    ll i;
    for (i = 0; i < 1000; i++) {
        ll tmp = i * i * i * i * i;
        //if (tmp > beki(10, 9)) break;
        C[i] = tmp;
    }

    REP(j, i) {
        REP(k, i) {
            if (C[j] - C[k] == X) {
                cout << (ll)pow(C[j], (float)1/5) << " " << (ll)pow(C[k], (float)1/5) << endl;
                return 0;
            }
            else if (-C[j] - C[k] == X) {
                cout << -(ll)pow(C[j], (float)1/5) << " " << (ll)pow(C[k], (float)1 / 5) << endl;
                return 0;
            }
            else if (C[j] - (-C[k]) == X) {
                cout << (ll)pow(C[j], (float)1 / 5) << " " << -(ll)pow(C[k], (float)1 / 5) << endl;
                return 0;
            }
            else if (-C[j] - (-C[k]) == X) {
                cout << -(ll)pow(C[j], (float)1 / 5) << " " << -(ll)pow(C[k], (float)1 / 5) << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 4112
n, m = map(int, input().split())
if m & 1:
    if n & 1:
        left_1 = 1
        right_1 = n // 2
        left_2 = (n // 2) + 1
        right_2 = n
    else:
        left_1 = 1
        right_1 = n // 2 - 1
        left_2 = (n // 2) + 1
        right_2 = n
else:
    if n & 1:
        left_1 = 1
        right_1 = n // 2
        left_2 = (n // 2) + 1
        right_2 = n
    else:
        left_1 = 1
        right_1 = n // 2 - 1
        left_2 = (n // 2) + 1
        right_2 = n
for _ in range(m // 2):
    print(left_1, right_1)
    left_1 += 1
    right_1 -= 1
for _ in range(m // 2, m):
    print(left_2, right_2)
    left_2 += 1
    right_2 -= 1


Measured memory_bytes: 70092
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vector<pii> A(N);
  set<int> S;
  rep(i,0,N){
    cin>>A[i].first;
    A[i].second=i+1;
    S.insert(A[i].first-1);
  }
  int memo=0;
  sort(ALL(A));
  vi ans(N*N);
  rep(i,0,N){
    rep(j,0,A[i].second-1){
      while(S.count(memo)) memo++;
      ans[memo]=A[i].second;
      if(memo>=A[i].first-1){
        cout<<"No"<<endl;
        return 0;
      }
      memo++;
    }
  }
  memo=N*N-1;
  reverse(ALL(A));
  rep(i,0,N){
    rep(j,0,N-A[i].second){
      while(S.count(memo)) memo--;
      ans[memo]=A[i].second;
      if(memo<=A[i].first-1){
        cout<<"No"<<endl;
        return 0;
      }
      memo--;
    }
  }
  cout<<"Yes"<<endl;
  rep(i,0,N) ans[A[i].first-1]=A[i].second;
  rep(i,0,N*N) cout<<ans[i]<<" ";
  cout<<endl;
  }



Measured memory_bytes: 3200
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define REPI(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) REPI(i,0,n)

typedef long long int ll;

int SURP = 1000000007;

int main(){
	int N,A,B;
	ll ret2 = 0;

	cin >> N >> A >> B;

	ll v[N];
	REP(i,N) cin >> v[i];
	sort(v, v + N);
	reverse(v, v + N);

	ll comp[N+1][N+1];
	REP(i,N+1){
		REP(j,N+1){
			if(i == 0) comp[i][j] = 0;
			else if(i < j) comp[i][j] = 0;
			else if(j == 0) comp[i][j] = 0;
			else if(j == 1) comp[i][j] = i;
			else if(i == j) comp[i][j] = 1;
			else comp[i][j] = comp[i-1][j-1] + comp[i-1][j];

		}
	}

	double ret = 0.0;
	REP(i,A){
		ret += (double)v[i];
	}
	ret /= (double)A;

	if(v[0] != v[A-1]){
		int tmp1 = 0;
		int tmp2 = N - A;
		REP(i,A){
			if(v[i] == v[A-1]){
				tmp1 = A - i;
				break;
			}
		}
		REPI(i,A,N){
			if(v[A-1] != v[i]){
				tmp2 = i - A;
				break;
			}
		}
		ret2 = comp[tmp1+tmp2][tmp1];
	}else{
		int tmp = N;
		REPI(i,A,N){
			if(v[0] != v[i]){
				tmp = i;
				break;
			}
		}
		REPI(i,A,B+1){
			ret2 += comp[tmp][i];
		}
	}

	cout << fixed << setprecision(6) << ret << endl;
	cout << ret2 << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

//Bug Party
public class Main{

	class B implements Comparable<B>{
		int a, b;
		public B(int a, int b) {
			this.a = a;
			this.b = b;
		}
		public int compareTo(B o) {
			return o.b-b;
		}
	}
	
	int n;
	B[] r;
	
	boolean ok(int x){
		if(x==0)return true;
		PriorityQueue<B> q = new PriorityQueue<B>(x, new Comparator<B>() {
			public int compare(B o1, B o2) {
				return o2.a-o1.a;
			}
		});
		long A = 0;
		for(int i=0;i<x-1;i++){
			A+=r[i].a;
			q.add(r[i]);
		}
		for(int i=x-1;i<n;i++){
			long w = (long)x*r[i].b-r[i].a;
			if(A<=w)return true;
			A+=r[i].a;
			q.add(r[i]);
			A-=q.poll().a;
		}
		return false;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		r = new B[n];
		for(int i=0;i<n;i++)r[i]=new B(sc.nextInt(), sc.nextInt());
		Arrays.sort(r);
		int L = 0, R = n;
		while(R-L>1){
			int m = (L+R)/2;
			if(ok(m))L=m;
			else R=m;
		}
		System.out.println(ok(R)?R:L);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {

	    public static void main(String[]args){
	    	Scanner scan=new Scanner(System.in);
	    	int a=scan.nextInt();
	    	int b=scan.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: 25940
#include <iostream>
#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

const int MN=20;
const int M=(1<<18)+5;
int n,m;
int s;
map<int,int,greater<int>> ma;

priority_queue<int> pq;
queue<int> qu;

int main()
{
	scanf("%d",&n);
	m=1<<n;
	for(int i=0;i<m;i++)
	{
		scanf("%d",&s);
		ma[s]++;
	}
	pq.push(m);
	for(auto p:ma)
	{
		int cnt=p.second;
		if((int)pq.size()<cnt)
		{
			printf("No\n");
			return 0;
		}
		for(int i=0;i<cnt;i++)
		{
			qu.push(pq.top()); pq.pop();
		}
		while(!qu.empty())
		{
			for(int i=1;i<qu.front();i<<=1)
				pq.push(i);
			qu.pop();
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 13184
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <queue>
#include <sstream>
using namespace std;
#define mp make_pair
#define pb push_back
#define re return
#define fi first
#define se second
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<vi> vvi;
string s;
int k;
int main() {
	cin>>s>>k;
	int i=0;
	while(s[i]=='1'){
		k--;
		if(k==0){
			cout<<'1'<<endl;
			return 0;
		}
		i++;
	}
	cout<<s[i]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

void calcCrossPoint(
    double p1x, double p1y,
    double p2x, double p2y,
    double p3x, double p3y,
    double p4x, double p4y,
    double &cx, double &cy)
{
    double t = (p2y - p1y) * (p4x - p3x) - (p2x - p1x) * (p4y - p3y);
    cx = (p3y * p4x - p3x * p4y) * (p2x - p1x) - (p1y * p2x - p1x * p2y) * (p4x - p3x);
    cy = (p3y * p4x - p3x * p4y) * (p2y - p1y) - (p1y * p2x - p1x * p2y) * (p4y - p3y);
    cx /= t;
    cy /= t;
}

int main(){

    int Q;
    std::cin >> Q;
    for(int q = 0; q < Q; q++)
    {
        double p0x, p0y;
        std::cin >> p0x >> p0y;
        double p1x, p1y;
        std::cin >> p1x >> p1y;
        double p2x, p2y;
        std::cin >> p2x >> p2y;
        double p3x, p3y;
        std::cin >> p3x >> p3y;
        double cx, cy;
        calcCrossPoint(p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y, cx, cy);
        printf("%.9f %.9f\n", cx, cy);
    }
    return 0;
}


Measured memory_bytes: 3252
#include <bits/stdc++.h>
 
using namespace std;
 
int a[10][10][10],c[10][10],N;
bool visited[10][10][10];
 
bool valid(int x,int y,int z){
    if(0 > x || N <= x) return false;
    if(0 > y || N <= y) return false;
    if(0 > z || N <= z) return false;
    if(a[y][x][z] == -1) return false;
    return true;
}
 
int check(int x,int y,int z,int p){
    int max = 0,l[2] = {0};
    int dx[] = {-1,1,0,0,-1,1,-1,1,-1,1,0,0,-1,1,-1,1,-1,1,0,0,-1,1,-1,1,0,0};
    int dy[] = {0,0,-1,1,-1,1,1,-1,0,0,-1,1,-1,1,1,-1,0,0,-1,1,-1,1,1,-1,0,0};
    int dz[] = {0,0,0,0,0,0,0,0,-1,1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1,-1,1};
    for(int i = 0 ; i < 26 ; i++){
	int nx = x + dx[i],ny = y + dy[i],nz = z + dz[i];
	while(valid(nx,ny,nz) && a[ny][nx][nz] == p){
	    l[i%2]++;
	    nx += dx[i];
	    ny += dy[i];
	    nz += dz[i];
	}
	if(i % 2){
	    max = std::max(max,l[0]+l[1]+1);
	    l[0] = l[1] = 0;
	}
    }
    return max;
}
 
int main(){
    int M,P;
    while(cin >> N >> M >> P, N){
	memset(a,-1,sizeof(a));
	memset(c,0,sizeof(c));
	int win = -1, turn = -1;
	for(int i = 0 ; i < P ; i++){
	    int x,y;
	    cin >> x >> y;
	    x--; y--;
	    a[y][x][c[y][x]] = i%2;
	    if(win == -1){
		if(check(x,y,c[y][x],i%2) >= M){
		    win = i%2;
		    turn = i+1;
		}
	    }
	    c[y][x]++;
	}
	if(win == -1){
	    cout << "Draw" << endl;
	}else{
	    if(win == 1){
		cout << "White " << turn << endl;
	    }else{
		cout << "Black " << turn << endl;
	    }
	}
    }
    return 0;
}

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

int main(void) {
  string s;
  int n1, n2;
  cin >> s;
  n1 = stoi(s.substr(0,2));
  n2 = stoi(s.substr(2,2));
  int check = ((1 <= n1 && n1 <= 12) ? 2 : 0) + ((1 <= n2 && n2 <= 12) ? 1 : 0);
  string res[4] = {"NA", "YYMM", "MMYY", "AMBIGUOUS"};
  cout << res[check] << endl;
  return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



string s;
void solve(){
	cin >> s;
	
	cout << s.substr(0,5) << " " << s.substr(6,7) << " " << s.substr(14,5) << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

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

using std::min;
using std::max;
using std::swap;

using std::string;

using std::vector;


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

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

    int cnt = 0;
    for(int i = 0; i < n-1; i++){
        if(p[i] == i){
            swap(p[i], p[i+1]);
            cnt++;
        }
    }
    for(int i = n-1; i > 0; i--){
        if(p[i] == i){
            swap(p[i], p[i-1]);
            cnt++;
        }
    }

    cout << cnt << endl;


    return 0;
}


Measured memory_bytes: 640
#include<iostream>

using namespace std;

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

	if (a + b == 15) {
		cout << "+" << endl;
	}
	else if (a*b == 15) {
		cout << "*" << endl;
	}
	else {
		cout << "x" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb  push_back
#define ppb pop_back
#define mp  make_pair
#define SIZE 100005
pll arr[SIZE];
bool compare(pll a,pll b){
	if(a.first<b.first){
		return true;
	}
	else if(a.first>b.first){
		return false;
	}
	else{
		return a.second>b.second;
	}
}
int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll N;
	cin>>N;
	for(ll i=0;i<N;++i){
		ll x,l;
		cin>>x>>l;
		arr[i]=mp(x+l,x-l);
	}
	sort(arr,arr+N,compare);
	ll cnt=1;
	ll k=0;
	for(ll i=1;i<N;++i){
		if(arr[i].second>=arr[k].first){
			cnt++;
			k=i;
		}
		// cout<<arr[i].second<<" "<<arr[i].first<<endl;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)//cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}


	
int main() {
	ios::sync_with_stdio(false);
	int N,M;cin>>N>>M;
	set<int>a,b;
	for(int i=0;i<N;++i){
		int x;cin>>x;a.emplace(x);
	}
	for(int i=0;i<M;++i){
		int x;cin>>x;b.emplace(x);
	}
	set<int>c(a);
	for(auto k:b){
		c.emplace(k);
	}
	set<int>d;
	for(auto k:b){
		if(a.find(k)!=a.end())d.emplace(k);
	}
	swap(c,d);
	cout<<c.size()<<' '<<d.size()<<endl;
	for(auto x:c)cout<<x<<endl;
	for(auto x:d)cout<<x<<endl;
	
	return 0;	
}


Measured memory_bytes: 25992
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, K int
	fmt.Scan(&N)
	fmt.Scan(&K)
	l := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&l[i])
	}
	sort.Ints(l)
	ans := 0
	for i := 0; i < K; i++ {
		ans += l[len(l)-1-i]
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
//AtCoder ABC083 C - Multiple Gift
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

int main() {
    uint64_t X,Y;
    cin>>X>>Y;
    auto v=X;
    ll ans=0;
    while(v<=Y){
        v*=2;
        ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N,K = map(int, input().split())
s = input()
ans = ""
for i in range(N):
    if i==K-1:
        if s[i]=="A":
            a = "a"
        elif s[i] == "B":
            a = "b"
        else:
            a = "c"
        ans += a
    else:
        ans += s[i]
print(ans)


Measured memory_bytes: 3060
module Main where

import Control.Applicative
import Numeric

main :: IO ()
main = do
  { [n] <- getInts
  ; call n
  }

call :: Int -> IO ()
call n = putStr " " >> putInts (filter (\ i -> p i || r i) [1 .. n])
  where
    p i = i `mod` 3 == 0
    r i = '3' `elem` show i


-- call n = check_num n 1 1

-- check_num :: Int -> Int -> Int -> IO ()
-- check_num n i x = if x `mod` 3 == 0
--   then putStr " " >> putStr (show i) >> end_check_num n i x
--   else include3 n i x

-- include3 :: Int -> Int -> Int -> IO ()
-- include3 n i x = if x `mod` 10 == 3
--   then putStr " " >> putStr (show i) >> end_check_num n i x
--   else let x' = x `div` 10
--        in if x' /= 0 then include3 n i x'
--           else end_check_num n i x'

-- end_check_num :: Int -> Int -> Int -> IO ()
-- end_check_num n i x = let i' = i + 1
--                       in if i' <= n then check_num n i' i'
--                          else putStrLn ""

--

getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""



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

using ll=long long;
int main(){
    ll n,c;
    cin>>n>>c;
    vector<ll> x(n);
    vector<ll> v(n);
    for(int i=0;i<n;i++) cin>>x[i]>>v[i];
    auto func=[&](){
        
    ll res=0;
    ll sum=0;
    for(int i=0;i<n;i++){
        sum+=v[i];
        res=max(res,sum-x[i]);
    }

    stack<pair<ll,ll>> rev;
    rev.push({0LL,n});
    sum=0;
    for(int i=n-1;i>=0;i--){
        auto ret=rev.top();
        sum+=v[i];
        if(ret.first<sum-(c-x[i])){
            rev.push({sum-(c-x[i]),i});
        }
    }
    
    sum=0;
    for(int i=0;i<n;i++){
        sum+=v[i];
        while(rev.top().second<=i){
            rev.pop();
        }
        
        res=max(res,sum-x[i]*2+rev.top().first);
    }
    
    return res;
    };
    ll res=func();
    for(int i=0;i<n;i++){
        x[i]=c-x[i];
    }
    reverse(x.begin(),x.end());
    reverse(v.begin(),v.end());
    res=max(res,func());
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 3472
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repp(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;

signed main(){
    int n, sum = 0;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n){
        cin >> a[i];
        sum += a[i];
    }
    sum /= n;
    int a1 = 0, a2 = 0;
    // cout << sum << endl;
    rep(i, 0, n){
        a1 += (a[i] - sum)*(a[i] - sum);
        a2 += (a[i] - sum - 1)*(a[i] - sum - 1); 
    }
    cout << min(a1, a2) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ld INF = 1e9+123;
#define VEC(type,A,N) vector<type> A(N+10)
#define VECi(type,A,N,i) vector<type> A(N+10,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N+10,vector<type>(M+10))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N+10,vector<type>(M+10,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}

int main(){
    ll L,R;
    cin>>L>>R;
    ll min=INF;
    ll minR=L+2019<R?L+2019+1:R+1;
    FOR(i,L,minR){
        FOR(j,L,minR){
            if(i!=j){
                ll t=(i*j)%2019;
                min=min>t?t:min;
            }
        }
    }
    cout<<min;
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256