akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    private static int count = 0;

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

        int n = sc.nextInt();

        int[] S = new int[n];
        for (int i = 0; i < n; i++) S[i] = Integer.parseInt(sc.next());

        mergeSort(S, 0, n);

        System.out.println(Arrays.stream(S).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        System.out.println(count);
    }

    private static void mergeSort(int[] A, int left, int right) {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid, right);
            merge(A, left, mid, right);
        }
    }

    private static void merge(int[] A, int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;

        int[] L = new int[n1+1];
        int[] R = new int[n2+1];

        for (int i = 0; i < n1; i++) L[i] = A[left + i];
        for (int i = 0; i < n2; i++) R[i] = A[mid + i];

        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        for (int k = left; k < right; k++) {
            if (L[i] <= R[j]) {
                A[k] = L[i++];
            } else {
                A[k] = R[j++];
            }
            count++;
        }
    }
}



Measured memory_bytes: 119320
#include<bits/stdc++.h>
using namespace std;
const int S = 17, N = 42, M = 1e9 + 7;
int dp[N][1<<S];
int main()
{
    int n,x,y,z;
    cin >> n >> x >> y >> z;
    int s = x + y + z;
    int full = (1<<s) - 1;
    int hai = (1<<(x+y+z-1)) | (1<<(y+z-1)) | (1<<(z-1)); 
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= full; ++j) {
            for (int k = 1; k <= 10; ++k) {
                int w = ((j<<k) | (1<<(k-1))) & full;
                if ((w & hai) == hai)
                    continue;
                (dp[i+1][w] += dp[i][j]) %= M;
            }
        }
    }
    int ans = 1;
    for (int i = 0; i < n; ++i)
        ans = 10LL * ans % M;
    for (int j = 0; j <= full; ++j)
        ans = (ans + M - dp[n][j]) % M;
    cout << ans << '\n';
}


Measured memory_bytes: 20736
#include<bits/stdc++.h>
using namespace std;
static const int N = 105; 
int cont;
int n;
void BubbleSort(int *a){
	for(int i=0;i<n;i++){
		for(int j=n-1;j>i;j--)
			if(a[j]<a[j-1]){
				swap(a[j],a[j-1]);
				cont++;
			}
	}
}
int main(){
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	BubbleSort(a); 
	for(int i=0;i<n;i++){
		if(i!=n-1)
			cout<<a[i]<<" ";
		else
			cout<<a[i]<<endl;
	}
	cout<<cont<<endl;
	return 0;
}


Measured memory_bytes: 3104
using System;
namespace OJ_C_Sharp {
	class Program {
		static void Main(string[] args) {
			int n = int.Parse(Console.ReadLine());
			int[,] f = new int[n, 10];
			int[,] p = new int[n, 11];
			for (int i = 0; i < n; i++) {
				var input_f = Console.ReadLine().Split(' ');
				for (int j = 0; j < 10; j++) {
					f[i, j] = int.Parse(input_f[j]);
				}
			}
			for (int i = 0; i < n;i++){
				var input_p = Console.ReadLine().Split(' ');
				for (int j = 0; j < 11;j++){
					p[i, j] = int.Parse(input_p[j]);
				}
			}
			int max = int.MinValue;
			for (int i = 1; i < 1024;i++){
				int pro = 0;
				for (int j = 0; j < n;j++){
					int c = 0;
					for (int k = 0; k < 10;k++){
						if(((i>>k&1)==1)&&(f[j,k]==1)){
							c++;
						}
					}
					pro += p[j, c];
				}
				if(max<pro){
					max = pro;
				}
			}
			Console.WriteLine(max);
		}
	}
}


Measured memory_bytes: 11092
#include <bits/stdc++.h> 
using namespace std;
long long n,i,a,b,s,mi=0x7ffffffffffffll;
int main(){
	cin>>n;
	for (i=1;i<=n;i++){
		cin>>a>>b;
		s+=b;
		if (a>b) mi=min(mi,b);
	}
	cout<<max(0ll,s-mi);
	return 0;
}

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

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  int n,k;
  string s;
  cin >> n >> s >> k;
  char c = s[k-1] ;
  rep(i,n){
    if(s[i] != c){
      s[i] = '*';
    }
  }
  cout <<  s << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import deque
def bfs(sy,sx):
    d = [[-float("inf")] * (2+w) for i in range(h+2)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        #if p[0] == gy and p[1] == gx:
        #    break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if maze[nx][ny] != "#" and d[nx][ny] == -float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    ans = 0
    for i in range(2+w):
        for j in range(h+2):
            ans = max(ans,d[j][i])
    return ans
h,w = map(int, input().split())
maze = [["#"]*(w+2)] + [list("#" + input() + "#") for i in range(h)] + [["#"]*(w+2)]
ans = 0
for x in range(1,w+1):
    for y in range(1,h+1):
        if maze[y][x] == ".":
            ans = max(bfs(y,x),ans)
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <bitset>
#include <vector>
#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
  int H,W,K;
  std::cin>>H>>W>>K;
  std::vector<std::string> c(H);
  rep(i,H)std::cin>>c[i];

    unsigned int black = 0, count = 0;

    for(int maskR=0; maskR<(1<<H); maskR++){
        for(int maskC=0; maskC<(1<<W); maskC++){

            black = 0;
            for(unsigned int i=0; i<H; i++){
                for(unsigned int j=0; j<W; j++){
                    if(maskR&(1<<i) || maskC&(1<<j)) continue;
                    if(c[i][j] == '#') black++;
                }
            }
            if(black == K){
                count++;
            }

        }
    }

    std::cout << count << std::endl;

    //int end;
    //std::cin >> end;
    return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


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

    ll takahashi = a;
    ll aoki = b;

    if (k > a) {
        takahashi = 0;
        if(k-a > b) {
            aoki = 0;
        } else {
            aoki = b - (k-a);
        }
    } else {
        takahashi = a-k;
    }


    cout << takahashi << " " << aoki << endl;


    return 0;
}



Measured memory_bytes: 256
NUM_500 = int(input())
NUM_100 = int(input())
NUM_050 = int(input())
price = int(input())

num_500 = 0
pattern = 0
while num_500 <= NUM_500:
    num_100 = 0
    while num_100 <= NUM_100:
        num_050 = 0
        while num_050 <= NUM_050:
            if price == 500 * num_500 + 100 * num_100 + 50 * num_050:
                pattern += 1
            num_050 +=1
        num_100 += 1
    num_500 += 1
print(pattern)

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int mod=1e9+7;
int n,m,cnt,tot;
int x[100005],y[100005];
pair<int,int> v[100005];
map<int,int> id;
int r[100005];
void ins(int x,int b){
	for(;x<=cnt;x+=(x&-x))r[x]=(r[x]+b>=mod?r[x]+b-mod:r[x]+b);
}
int qry(int x){
	int res=0;
	for(;x;x-=(x&-x))res=(res+r[x]>=mod?res+r[x]-mod:res+r[x]);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	for(int i=1;i<=m;i++)scanf("%d",&y[i]);
	for(int i=1;i<=n;i++){
		int j=lower_bound(y+1,y+m+1,x[i])-y;
		// printf("%d\n",j);
		if(j==1||j==m+1)continue;
		tot++;
		v[tot]=make_pair(y[j]-x[i],y[j-1]-x[i]);
		id[x[i]-y[j-1]]=1;
	}
	for(map<int,int>::iterator it=id.begin();it!=id.end();it++)it->second=++cnt;
	sort(v+1,v+tot+1);
	tot=unique(v+1,v+tot+1)-(v+1);
	/*
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++){
		printf("%d %d\n",v[i].first,-v[i].second);
	}
	*/
	for(int i=1;i<=tot;i++)v[i].second=id[-v[i].second];
	for(int i=1;i<=tot;i++){
		// printf("!!%d %d %d\n",i,v[i].second,qry(v[i].second-1)+1);
		ins(v[i].second,qry(v[i].second-1)+1);
		// for(int i=1;i<=cnt;i++)printf("%d ",r[i]); puts("");
	}
	printf("%d\n",qry(cnt)+1);
	return 0;
}

Measured memory_bytes: 6400
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
S = readline().decode().rstrip()
T = readline().decode().rstrip()
len_S = len(S)
len_T = len(T)
N = len_S-len_T
INF = 10**31
ans = INF
for i in range(N+1):
    cnt = 0
    for j in range(len_T):
        if S[i+j] != T[j]:
            cnt += 1
    ans = min(ans,cnt)
print(ans)

Measured memory_bytes: 72856
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n, k] <- getIntList
    hs <- getIntList
    if n <= k then print 0 else print $ solve n k hs
    
solve n k hs = sum . take (n - k) $ sort hs


Measured memory_bytes: 31100
import bisect

N, K = map(int, input().split())
Xs = list(map(int, input().split()))

rlt = float('inf')
i = bisect.bisect_left(Xs, 0)
if i-K >= 0:
  rlt = abs(Xs[i-K])

for j in range(i, i+K-1):
  if j >= N:
    break
  if j - K + 1 < 0:
    continue
  rlt = min(rlt, 2*abs(Xs[j-K+1])+Xs[j], abs(Xs[j-K+1])+2*Xs[j])
  
if i + K - 1 < N:
  rlt = min(rlt, Xs[i+K-1])
  
print(rlt)

Measured memory_bytes: 85164
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
#include<tuple>
#include<utility>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define pb push_back
#define mp make_pair

int main() {
	int n, a, b;
	cin >> n;
	a = n / 100;
	b = n % 100;
	if (a <= 12 && b <= 12 && a != 0 && b != 0) {
		cout << "AMBIGUOUS" << endl;
		return 0;
	}
	else if(a <= 12 && a != 0) {
		cout << "MMYY" << endl;
		return 0;
	}
	else if (b <= 12 && b != 0) {
		cout << "YYMM" << endl;
		return 0;
	}
	else {
		cout << "NA" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

multiset<int> s;

int main(){
	int n;
	cin >> n;
	while(n--){
		int x;
		scanf("%d",&x);
		s.insert(x);
	}
	cin >> n;
	while(n--){
		int x;
		scanf("%d",&x);
		if(s.find(x)==s.end()){
			puts("NO");
			return 0;
		}
		s.erase(s.find(x));
	}
	puts("YES");
}



Measured memory_bytes: 9600
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

X, A, B = [int(input()) for _ in range(3)]

print(X - A - ((X - A) // B) * B)

Measured memory_bytes: 3572
program main
  implicit none
  integer :: n, m, queries, p, q, i, l, r
  integer, allocatable :: c(:, :), d(:, :)
  read *, n, m, queries
  allocate (c(n, n), d(0:n, 0:n))
  d(:, :) = 0
  do i = 1, m
    read *, l, r
    d(l, r) = d(l, r) + 1
  end do
  do i = 1, n
    d(i, :) = d(i, :) + d(i - 1, :)
  end do
  do i = 1, n
    d(:, i) = d(:, i) + d(:, i - 1)
  end do
  do i = 1, queries
    read *, p, q
    print "(i0)", d(n, q) - d(n, 0) - d(p - 1, q) + d(p - 1, 0)
  end do
end program main


Measured memory_bytes: 1920
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

int dx[4] = { 1,-1,4,-4 };
map<string, int>res;

void solve(void) {
    queue<string>que;
    que.push("01234567");
    while (!que.empty()) {
        string v = que.front();
        que.pop();
        int pos = 0;
        for (int i = 0; i < 8; i++)
            if (v[i] == '0')pos = i;

        for (int i = 0; i < 4; i++) {
            if (0 <= pos + dx[i] && pos + dx[i] < 8 &&
                !(pos == 3 && i == 0) && !(pos == 4 && i == 1)) {
                string u = v;
                swap(u[pos], u[pos + dx[i]]);

                if (res[u] == 0) {
                    que.push(u);
                    res[u] = res[v] + 1;
                }
            }
        }
    }
}

int main(void) {
    int in;
    res["01234567"] = 1;
    solve();
    while (true) {
        string s;
        for (int i = 0; i < 8; i++) {
            if (!(cin >> in))return 0;
            s += in + '0';
        }
        cout << res[s] - 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 5240
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let N : usize = read();
    let mut list = Vec::<i64>::new();
    for i in 0..N {
        let a: i64 = read();
        list.push(a);
    }

    let mut ans = 1145141919;
    for mut v in list {
        let mut tmp = 0;
        while v%2 == 0 {
            tmp += 1;
            v = v/2;
        }
        
        ans = std::cmp::min(ans, tmp);
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
        #include<chrono>
         
        using namespace std;
        using namespace std::chrono;
        typedef long long ll;
        typedef vector<int> vi;
        typedef pair<int,int> pi;
        #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)    
        #define F first
        #define S second
        #define PB push_back
        #define EB emplace_back
        #define MP make_pair
        #define REP(i,a,b) for(i=a;i<=b;i++)
        #define RAP(i,a,b) for(i=a;i>=b;i--)
        ll mod=1000000007;
        const int MX=0x3f3f3f3f;
        
        int main(){
            IOS;
            int n,W,i,j;
            cin>>n>>W;
            ll w[n],v[n];
            REP(i,0,n-1) cin>>w[i]>>v[i];
            ll dp[W+1]={0};
            REP(i,1,n){
                RAP(j,W,1){
                    dp[j]=dp[j];
                    if(w[i-1]<=j) dp[j]=max(dp[j],dp[j-w[i-1]]+v[i-1]);
               
                }
            }
            cout<<dp[W];
            return 0;
        }

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

#define lln long long int
using namespace std;

int gcd(int a,int b){
if(b==0){
    return a;
}
return gcd(b,a%b);
}
int main()
{
    int  n,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int p=gcd(i,j);
            for(int k=1;k<=n;k++){
                int res=gcd(p,k);
                sum=sum+res;
            }
        }
    }
    printf("%d",sum);

}


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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define INF 1000000007
#define N 100010
int n, a[N], b[N], f[N], g[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
		int k = 0;
		while ((1<<k) < a[i]) k++;
		if (a[i] == (1<<k)) b[i] = 1;
		a[i] = k;
	}
	
	for (int i = 1; i <= n; i ++)
		f[i] = g[i] = INF;
	g[0] = INF;
	int la = 0, lb = 1;
	
	for (int i = 0; i < n; i ++) {
		if (b[i] == 1) {
			f[i+1] = min(f[i+1], f[i] + a[i]-min(a[i], la));
			if (lb == 0) f[i+1] = min(f[i+1], g[i] + a[i]-min(a[i], la-1));
		} else {
			// from f
			f[i+1] = min(f[i+1], f[i] + 1 + (a[i]-1)-min(a[i]-1, la));
			g[i+1] = min(g[i+1], f[i] + a[i]-min(a[i], la));
			
			if (lb == 0) {
				// can do g
				f[i+1] = min(f[i+1], g[i] + 1 + (a[i]-1)-min(a[i]-1, la-1));
				g[i+1] = min(g[i+1], g[i] + a[i]-min(a[i], la-1));
			}
		}
		
		la = a[i];
		lb = b[i];
	}
	
	cout << min(f[n], g[n]) << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
#define rep(i,n) for(i=0;i<n;i++)
typedef struct{char s[21];int p;}P;
int main(void)
{
  int n,d,w,l,i,j,s=0;
  P p[10],t;
  for(;;){
    scanf("%d",&n);if(!n)break;
    if(s)puts("");else s=1;
    rep(i,n)scanf("%s%d%d%d",p[i].s,&w,&l,&d),p[i].p=w*3+d;
    for(i=n-1;i;i--){
      rep(j,i)
	if(p[j].p<p[j+1].p){
	  t=p[j];p[j]=p[j+1];p[j+1]=t;
	}
    }
    rep(i,n)printf("%s,%d\n",p[i].s,p[i].p);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if ((fmax(a,c)-fmin(a,c)<=d) || (fmax(b,c)-fmin(b,c)<=d && fmax(a,b)-fmin(a,b)<=d)) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3676
using System; 
using System.Collections;

namespace CSharp
{
    class Edge 
    {
        public int x, y;
        public Edge(int _x, int _y)
        {
            x = _x;
            y = _y;
        }
    }

    class Program
    {

        private static int[] parent, size;

        private static int find(int u) 
        {
            if (u == parent[u]) return u;
            return parent[u] = find(parent[u]);
        }

        private static long merge(int u, int v)
        {
            u = find(u); v = find(v);
            if (u == v) return -1L;
            int size_u = size[u], size_v = size[v];
            parent[u] = v;
            size[v] += size[u];
            size[u] = 0;
            return size_u * (size_u - 1L) * 1L / 2L + size_v * (size_v - 1L) * 1L / 2L;
        }

        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split();
            int n = int.Parse(s[0]);
            int m = int.Parse(s[1]);

            parent = new int[n + 1];
            size = new int[n + 1];

            Edge[] edges = new Edge[m];
            for (int i = 0; i < m; i++) {
                string[] es = Console.ReadLine().Split();
                int u = int.Parse(es[0]);
                int v = int.Parse(es[1]);

                edges[i] = new Edge(u, v);
            }

            for (int i = 1; i <= n; i++) {
                parent[i] = i;
                size[i] = 1;
            }

            long[] ans = new long[m];
            long tmp = n * (n - 1L) * 1L / 2L;

            for (int i = 0; i < m; i++) {
                ans[m - i - 1] = tmp;
                Edge edge = edges[m - i - 1];
                long delta = merge(edge.x, edge.y);
                if (delta == -1L) continue;
                tmp += delta;
                int nsize = size[find(edge.x)];
                tmp -= nsize * (nsize - 1L) * 1L / 2L;
            }

            for (int i = 0; i < m; i++) {
                Console.WriteLine(ans[i]);
            }
        }
    }
}


Measured memory_bytes: 22852
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();

		sc.close();

		int result = T.length();

		for (int i = 0; i < S.length() - T.length() + 1; i++) {
			String SS = S.substring(i, T.length() + i);
			int temp = 0;
			for (int j = 0; j < T.length(); j++) {
				if (SS.charAt(j) != T.charAt(j)) {
					temp++;
				}
			}
			if (temp < result) {
				result = temp;
			}
		}

		System.out.print(result);
	}

}


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

using namespace std;

int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, p;
    cin >> n >> p;
    int odd = 0;
    for(int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        odd |= (t % 2);
    }
    if(p == 0)
        cout << (1LL << n - odd) << endl;
    else
        cout << odd * (1LL << n - 1) << endl;

}


Measured memory_bytes: 256
#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;
    cin >> N;
    for (int i = 1; i < 10000; i++) {
        if (i * 1000 >= N) {
            cout << i * 1000 - N << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 3624
use std::cmp::Reverse;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();

    let mut positive = vec![];
    let mut negative = vec![];
    for _ in 0..n {
        let s = sc.chars();
        let (left, right) = compile(s);

        if left - right > 0 {
            positive.push((left, right));
        } else {
            negative.push((left, right));
        }
    }

    positive.sort_by_key(|&(_, right)| right);

    let mut left_stack = 0;
    for (left, right) in positive.into_iter() {
        if left_stack < right {
            println!("No");
            return;
        }
        left_stack -= right;
        left_stack += left;
    }

    negative.sort_by_key(|&(left, _)| left);
    let mut right_stack = 0;
    for (left, right) in negative.into_iter() {
        if right_stack < left {
            println!("No");
            return;
        }
        right_stack -= left;
        right_stack += right;
    }

    if left_stack == right_stack {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn compile(s: Vec<char>) -> (i64, i64) {
    let mut left = 0;
    let mut right = 0;
    for c in s.into_iter() {
        match c {
            '(' => {
                left += 1;
            }
            ')' => {
                if left > 0 {
                    left -= 1;
                } else {
                    right += 1;
                }
            }
            _ => unimplemented!(),
        }
    }
    (left, right)
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

using namespace std;

int main()
{
	int n,m,a,b;
	cin >> n >> m >> a >> b;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if((i<b)^(j<a))
				cout << "0";
			else
				cout << "1";
		}
		cout << endl;
	}
}

Measured memory_bytes: 1280
#include<cstdio>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;

double area(pair<double,double> a, pair<double,double> b, pair<double,double> c){
	double d1 = sqrt( pow(a.first-b.first,2) + pow(a.second-b.second,2) );
	double d2 = sqrt( pow(c.first-b.first,2) + pow(c.second-b.second,2) );
	double d3 = sqrt( pow(a.first-c.first,2) + pow(a.second-c.second,2) );
	double s = (d1+d2+d3)/2.0;
	return sqrt( s*(s-d1)*(s-d2)*(s-d3) );
}


double solve(vector<pair<double,double> > vec){
	if( vec.size() < 3 ) return 0;
	vector<pair<double,double> > new_vector = vec;
	new_vector.erase(new_vector.begin()+1);
	double a = solve(new_vector);
	double b = area(vec[0],vec[1],vec[2]);
	return a + b;
}

int main(){
	double x,y;
	vector<pair<double,double> > vec;
	while(scanf("%lf,%lf",&x,&y) != EOF){
		vec.push_back(make_pair(x,y));
	}
	printf("%.8lf\n",solve(vec));
}

Measured memory_bytes: 1092
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            B();
        }

        static void B()
        {
            var XYZ = ReadIntInputs();
            var X = XYZ[0];
            var Y = XYZ[1];
            var Z = XYZ[2];
            if (X % (Y + Z) < Z)
                Console.WriteLine(X / (Y + Z) - 1); 
            else
                Console.WriteLine(X / (Y + Z));
        }

        public static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0)
                throw new Exception("0未満");

            if (start > stop || (start == 0 && stop == 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        public static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        public static int DigitsSum(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        public static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        public static string Read()
        {
            return Console.ReadLine();
        }

        public static IList<int> ReadIntInputs()
        {
            return Read().Split(' ').Select(int.Parse).ToList();
        }

        public static int ReadInt()
        {
            return int.Parse(Read());
        }

        public static IList<string> ReadInputs()
        {
            return Read().Split(' ').ToList();
        }
    }
}

Measured memory_bytes: 13268
// Author -> Preeyadarshee Dev
//
// train hard win easy :D
// nik is love
// nik is motivation
//
// do modulo operations very carefully
// try to avoid binary search, use linear search preferrably to make calculations easier
// always make your custom binary search and watch out for overflows
// read the problems carefully
// never rely on floating point calculation
#include <bits/stdc++.h>
#define mp                    make_pair
#define pb                    push_back
#define ll                   long long
#define ss                       second
#define ff                        first
#define fr(i,a,b)   for(ll i=a;i<b;i++)
#define f(i,n)                fr(i,0,n)
#define rf(i,b,a) for(ll i=b-1;i>=a;i--)
#define r(i,n)                rf(i,n,0)
#define inf                  (ll)1<<60
#define eps                  0.000000000000001
#define endl                       '\n'
#define sz(a)                int((a).size())
#define all(c)               (c).begin(),(c).end()
#define tr(c,i)              for(typeof(c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x)         ((c).find(x) != (c).end())
#define cpresent(c,x)        (find(all(c),x) != (c).end())
#define pi                   pair<int,int>
#define pll                  pair < ll , ll >
#define PI                   3.141592653589793238462643383279502884197169399375105820974944592307816406286
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef vector< int > vi;
typedef vector< vi > vvi;
int dx[8]={-2,-2,1,-1,-1,-1,1,1};
int dy[8]={1,-1,-2,-2,-1,1,-1,1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ifstream fin;
    //ofstream fout;
    //fin.open("input.txt");
    //fout.open("output.txt");
    string s1,s2;
    cin>>s1>>s2;
    vector<vector<int>> dp((int)s1.length()+1,vector<int> ((int)s2.length()+1,0));
    for(int i=0;i<(int)s1.length();i++)
    {
        for(int j=0;j<(int)s2.length();j++)
        {
            if(s1[i]==s2[j])
            {
                dp[i+1][j+1]=dp[i][j]+1;
            }
            else
            {
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
    }
    string str;
    int i=(int)s1.length(),j=(int)s2.length();
    while(i>0&&j>0)
    {
        
        if(dp[i][j]==dp[i-1][j])
        {
            i--;
        }
        else if(dp[i][j]==dp[i][j-1])
        {
            j--;
        }
        else if(dp[i][j]==dp[i-1][j-1]+1)
        {
            if(i-1>=0)
                str.pb(s1[i-1]);
            i--;
            j--;
        }
    }
    reverse(all(str));
    cout<<str<<endl;
}


Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1000000007
#define int long long

signed main(){
    int n;cin>>n;
    int d[n];
    rep(i,n)cin>>d[i];
    int ans=0;
    rep(i,n){
        rep(j,n){
            if(i==j||i>j)continue;
            ans+=d[i]*d[j];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d; cin >> a >> b >> c >> d;
    if(max(a,c) <= min(b,d))
    {
        cout << min(b,d) - max(a,c) << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var S string
	fmt.Scan(&S)
	max, cnt := 0, 0
	for i := 0; i < len(S); i++ {
		s := S[i]
		if s == 'A' || s == 'C' || s == 'G' || s == 'T' {
			cnt++
		} else {
			if max < cnt {
				max = cnt
			}
			cnt = 0
		}
	}
	if max < cnt {
		max = cnt
	}
	fmt.Println(max)
}


Measured memory_bytes: 512
#include <stdio.h>
#define N 100

int main(){
    int G[N][N];
    int n,u,k,v,i,j;
    
    scanf("%d",&n);
    
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            G[i][j] = 0;
        }
    }
    
    for(i=0;i<n;i++){
        scanf("%d %d",&u,&k);
        u--;
        for(j=0;j<k;j++){
            scanf("%d",&v);
            v--;
            G[u][v] = 1;
        }
    }
    
    for(i=0;i<n;i++){
        for(j=0;j<n-1;j++){
            printf("%d ",G[i][j]);
        }
        printf("%d\n",G[i][n-1]);
    }
    
    return 0;
}



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

int n, q, u, v;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 0; i < q; ++i) {
    cin >> u >> v;

    if (n == 1) {
      cout << min(u, v) << endl;
    }
    else {
      if (u > v) swap(u, v);

      while (u != v) {
        //cout << u << " " << v << endl;
        v = (v + n - 2) / n;
        if (u > v) swap(u, v);
      }
      cout << u << "\n";
    } 
  }
}

Measured memory_bytes: 1280
fun longList() = readLine()?.split(" ")?.map(String::toLong) ?: TODO()
fun main(args: Array<String>) {
    val (a, b) = longList()
    if (a == 0L || b == 0L) {
        println("Zero")
        return
    }
    if (a > 0 && b > 0) {
        println("Positive")
        return
    }
    if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
        println("Zero")
        return
    }
    if ((b - a) % 2 == 0L) {
        println("Negative")
        return
    } else {
        println("Positive")
        return
    }
}


Measured memory_bytes: 36536
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAX=200005;
int p[MAX],par[MAX],chk[MAX],cnt,nchk[MAX],fin,n,m;
vector<int> conn[MAX];
void dfs(int x,int idx){
    if(chk[x]!=0) return;
    chk[x]=idx;
    for(int i=0;i<conn[x].size();i++) dfs(conn[x][i],idx);
}
int main(){
    scanf(" %d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=0;i<m;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    for(int i=1;i<=n;i++) if(chk[i]==0) dfs(i,++cnt);
    for(int i=1;i<=n;i++) nchk[i]=chk[p[i]];
    for(int i=1;i<=n;i++) if(nchk[i]==chk[i]) fin++;
    printf("%d\n",fin);
}


Measured memory_bytes: 12928
using System;

namespace Rounding
{
    class Program
    {
        static void Main(string[] args)
        {
            string itigyou = System.Console.ReadLine();
            string[] hairetu = itigyou.Split();
            int X = int.Parse(hairetu[0]);
            int A = int.Parse(hairetu[1]);
            
            if(X < A){
                Console.WriteLine("0");
            }
            else{
                Console.WriteLine("10");
            }
        }
    }
}

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

int sign(int x) {
  if (0 < x) return 1;
  if (x < 0) return -1;
  return 0;
}

int main() {
  int x, y;
  cin >> x >> y;
  int ans = abs(abs(x) - abs(y));
  if (x < y) {
    if (sign(x) == 0 || sign(y) == 0 || sign(x) == sign(y)) cout << ans << endl;
    else cout << ans + 1 << endl;
  } else {
    if (sign(x) == sign(y)) cout << ans + 2 << endl;
    else cout << ans + 1 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
typedef pair<ll, ll> LP;
 
ll POW(ll m,ll n)
{
  if(n<0) return 0;
  if(n==0) return 1;
  return m*POW(m,n-1)%MOD;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll CON(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return m*CON(m-1,n)/(m-n);
}
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
 
int main()
{
  int a,b;
  cin >> a >> b;
  if(a*b%2!=0)printf("Yes");
  else printf("No");
}

Measured memory_bytes: 256
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MagicHash             #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE MultiWayIf            #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Exception
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString             as B
import qualified Data.ByteString.Char8       as C
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import qualified Data.Foldable               as F
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import qualified Data.List                   as L
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           GHC.Exts
import           Unsafe.Coerce

main :: IO ()
main = do
    !n <- readLn :: IO Int
    xs <- U.unfoldrN n (C.readInt.C.dropWhile isSpace) <$> C.getLine
    print $ solve n xs

solve :: Int -> U.Vector Int -> Int
solve n xs = U.foldl' max (U.foldl1' gcd xs) $ U.generate n $ \i ->
    if  | i == 0 -> rs U.! 1
        | i + 1 < n -> gcd (ls U.! (i - 1)) (rs U.! (i + 1))
        | otherwise -> ls U.! (n - 2)
  where
    !ls = U.scanl1 gcd xs
    !rs = U.scanr1 gcd xs


-------------------------------------------------------------------------------
type Parser a = C.ByteString -> Maybe (a, C.ByteString)

parseInt :: Parser Int
parseInt = C.readInt . C.dropWhile isSpace

parseInt2 :: Parser (Int, Int)
parseInt2 = runStateT $
    (,) <$> StateT (C.readInt . C.dropWhile isSpace)
        <*> StateT (C.readInt . B.unsafeTail)

parseInt3 :: Parser (Int, Int, Int)
parseInt3 = runStateT $
    (,,) <$> StateT (C.readInt . C.dropWhile isSpace)
        <*> StateT (C.readInt . B.unsafeTail)
        <*> StateT (C.readInt . B.unsafeTail)

parseInt4 :: Parser (Int, Int, Int, Int)
parseInt4 = runStateT $
    (,,,) <$> StateT (C.readInt . C.dropWhile isSpace)
        <*> StateT (C.readInt . B.unsafeTail)
        <*> StateT (C.readInt . B.unsafeTail)
        <*> StateT (C.readInt . B.unsafeTail)

Measured memory_bytes: 5628
/*
  AOJ 1041
  Title:Kyudo: A Japanese Art of Archery
  @kankichi573
*/
#include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <math.h>
// #include <float.h>
// #include <stdlib.h>


main()
{
  int p,i,n,s;

  while(scanf("%d",&n) && n)
    {
      s=0;
      for(i=0;i<n/4;i++)
	{
	  scanf("%d",&p);
	  s+=p;
	}
      printf("%d\n",s);
    }
  return(0);
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, A, B;

void solve() {
	cin >> N >> A >> B;
	cout << min(A * N, B) << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



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

const int M = 1e9 + 7;
long long dp[101][4][4][4];

int main() {
    int N;
    cin >> N;
  
    dp[0][0][0][0] = 1;
    for (int len = 0; len < N; len++) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    for (int x = 0; x < 4; x++) {
                        if (x == 0 && j == 1 && k == 2) continue;
                        if (x == 0 && i == 1 && k == 2) continue;
                        if (x == 0 && i == 1 && j == 2) continue;
                        if (x == 1 && i == 0 && j == 2) continue;
                        if (x == 0 && i == 2 && j == 1) continue;

                        dp[len + 1][x][i][j] =
                            (dp[len + 1][x][i][j] + dp[len][i][j][k]) % M;
                    }
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                ans = (ans + dp[N][i][j][k]) % M;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

int imos[100010];

int main(void){
	int n;
	cin >> n;
	imos[0]++;
	rep(i,n){
		int a,b;
		cin >> a >> b;
		imos[a]++,imos[b+1]--;
	}
	rep(i,n+5) imos[i+1]+=imos[i];
	int ans=0;
	rep(i,n+5) if(i<=imos[i]) ans=i;
	cout << ans-1 << endl;
	return 0;
}

Measured memory_bytes: 3468
N,L = map(int,input().split())
List = []
ans = 0
Min = float('inf') 
for i in range(1,N+1):
    List.append(L+i-1)
    Min = min(Min,abs(L+i-1))
    if L+i-1 <0:
        ans = (-1)*Min
    else:
        ans = Min
print(sum(List)-ans)

Measured memory_bytes: 3064
using System;using System.Linq;
class A{static void Main(){
    while(true){
        long[]a=Console.ReadLine().Split().Select(long.Parse).ToArray();
    if(a.Sum()==0){break;}
    for( long i=0;;i++){
        Array.Sort(a);
       // long x=a[1];
       // long y=a[0];
    if(a[0]==0){Console.WriteLine(a[1]+" "+i);break;}
a[1]%=a[0];
        
    }
    
    }
}}

Measured memory_bytes: 9752
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6,OO=0x3f3f3f3f;
int d()
{
    int ret;
    scanf("%d", &ret);
    return ret;
}
long long lld()
{
    long long ret;
    scanf("%lld", &ret);
    return ret;
}
int arr[N];

int main(){
    int n=d();
    for(int i=0;i<n;i++){
        scanf("%d",arr+i);
        arr[i]-=i+1;
    }
    sort(arr,arr+n);

        long long sum=0;
        for(int i=0;i<n;i++)
            sum+=abs(arr[i]-arr[n/2]);
        cout<<sum<<endl;



}


Measured memory_bytes: 1024
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    # dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
    N = read_int()
    h = read_ints()
    a, b = 0, abs(h[1]-h[0])
    for i in range(2, N):
        b, a = min(abs(h[i]-h[i-1])+b, abs(h[i]-h[i-2])+a), b
    return b


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 13976
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  l=LS()

  l1=[]
  l2=[]

  for i in range(len(l)):
    if i%2==0:
      l1.append(l[i])
    else:
      l2.append(l[i])

  if n%2==0:
    l2.reverse()
    l2+=l1
    return ' '.join(str(x) for x in l2)
  else:
    l1.reverse()
    l1+=l2
    return ' '.join(str(x) for x in l1)

print(main())


Measured memory_bytes: 27984
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
t=l[0][0]
a=l[0][1]
for j in range(1,n):
  z=max((t+l[j][0]-1)//l[j][0],(a+l[j][1]-1)//l[j][1])
  t=l[j][0]*z
  a=l[j][1]*z
print(t+a)

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#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() {
  string S; cin >> S;
  int zero = 0, one = 0;
  for (auto i : S) {
    if (i == '0') ++zero;
    else ++one;
  }
  cout << 2 * min(zero, one) << endl;
}

Measured memory_bytes: 3320
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <iostream>
#include <vector>
#include <set>
#include <regex>
#include <boost/format.hpp>

using namespace std;

#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define DEBUG(_debuged) cerr << #_debuged << ":" << _debuged << endl;

struct L
{
    int t;
    int x;
    int y;
};

vector<int> loadn(int n)
{
    vector<int> v(n);
    REP(i, n)
    cin >> v[i];
    return v;
}

uint64_t modpower(const unsigned int N, const unsigned int K, const unsigned int MOD)
{
    uint64_t ret = 1;
    uint64_t k2 = N;
    REP(i, 31)
    {
        if ((K >> i) & 0x1)
        {
            ret *= k2;
            ret = ret % MOD;
        }
        k2 = (k2 * k2) % MOD;
    }
    return ret;
}

class ModCombinationMemo
{
  public:
    const unsigned int N;
    const unsigned int MOD;
    vector<uint64_t> memo = {1};

    ModCombinationMemo(uint32_t N, uint32_t MOD)
        : N(N), MOD(MOD)
    {
    }

    uint64_t c(uint64_t k)
    {
        if (memo.size() > k)
        {
            return memo[k];
        }

        FOR(i, memo.size(), k + 1)
        {
            const auto number = (memo[i - 1] * (N - i + 1)) % MOD;
            const auto reverceDeon = modpower(i, MOD - 2, MOD);
            memo.push_back(number * reverceDeon % MOD);
        }

        return memo[k];
    }
};

uint64_t c(const unsigned int N, const unsigned int K, const unsigned int MOD)
{
    if (K == 0)
    {
        return 1;
    }

    uint64_t n = 1, k = 1;

    REP(i, K)
    {
        n *= N - i;
        k *= i + 1;

        n = n % MOD;
        k = k % MOD;
    }

    uint64_t powerk = modpower(k, MOD - 2, MOD);

    return (n * powerk) % MOD;
}

int main(int argc, char *argv[], char *envp[])
{
    int D, N;
    cin >> D >> N;

    
    cout << (N == 100 ? 101 : N);
    REP(i, D) cout << "00";
    cout << endl;
}


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

#define REP(i, s,  n) for(int i = s;i < (n);i++)
#define VSORT(v) sort(v.begin(), v.end());
#define int64 long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> PP;

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

//---------------------------------------------------------------
//---------------------------------------------------------------
int64 N, M;

signed main(){
	cin >> N >> M;
	
	if(N == 1 && M == 1)		cout << 1 << endl;
	else if(N == 1)				cout << (M - 2) << endl;
	else if(M == 1)				cout << (N - 2) << endl;
	else						cout << (N * M - 2*N - 2*M + 4) << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long
#define INF 10e9

using namespace std;
using P = pair<int, int>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

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

ll int N;
int main () {
  scanf("%lld", &N);

  ll int i = 1;
  ll int j = N;

  for (ll int k=1;k<=sqrt(N);++k) {
    if (N % k == 0) {
      i = k;
      j = N / k;
    }
  }

  printf("%lld\n", i + j - 2);
}

Measured memory_bytes: 256