stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define ld long double

#define pii pair<int,int>

#define pll pair<ll,ll>

#define rep(n) for(int i=0;i<n;i+=1)

#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );

#define sc(a) scanf("%d",&a);

#define scl(a) scanf("%lld",&a);

#define scf(a) ascanf("%f",&a);

#define fi first

#define se second

#define pu push_back

#define inf 1000000001

#define MOD 1000000007 

#define INF 100000000000001

const int MAXN = 2e5+10;

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    map<int,vector<int>> m;

    map<int,int> ans;

    int n;

    pii a[MAXN];

    int b[MAXN]={0};

    cin>>n;

    rep(n) 

    {

        cin>>a[i].fi;

        a[i].se = i;

        // m[a[i]].pu(i);

    }

    sort(a,a+n);

    rep(n)

    {

        if((i+1)<=n/2)

            ans[a[i].se] = a[n/2].fi;

        else

            ans[a[i].se] = a[n/2-1].fi;     

    }

    rep(n)

    {

        cout<<ans[i]<<endl; 

    }

    return 0;



}

    

// Faster C++ solution for the same problem (measured speedup: 2.656617262906256x):
#include <bits/stdc++.h>



#define ft first

#define sd second

#define sz(x) ((int)x.size())



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



const int MAXN = 200 * 1000 + 321;













int n, ans[MAXN];

pii x[MAXN];



int main() {

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> x[i].ft, x[i].sd = i;

	sort(x, x + n);

	for (int i = 0; i < (n >> 1); i++)

		ans[x[i].sd] = x[n >> 1].ft;

	for (int i = n / 2; i < n; i++)

		ans[x[i].sd] = x[(n >> 1) - 1].ft;

	for (int i = 0; i < n; i++)

		cout << ans[i] << '\n';

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define ld long double

#define pii pair<int,int>

#define pll pair<ll,ll>

#define rep(n) for(int i=0;i<n;i+=1)

#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );

#define sc(a) scanf("%d",&a);

#define scl(a) scanf("%lld",&a);

#define scf(a) ascanf("%f",&a);

#define fi first

#define se second

#define pu push_back

#define inf 1000000001

#define MOD 1000000007 

#define INF 100000000000001

const int MAXN = 2e5+10;

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    map<int,vector<int>> m;

    map<int,int> ans;

    int n;

    pii a[MAXN];

    int b[MAXN]={0};

    cin>>n;

    rep(n) 

    {

        cin>>a[i].fi;

        a[i].se = i;

        // m[a[i]].pu(i);

    }

    sort(a,a+n);

    rep(n)

    {

        if((i+1)<=n/2)

            ans[a[i].se] = a[n/2].fi;

        else

            ans[a[i].se] = a[n/2-1].fi;     

    }

    rep(n)

    {

        cout<<ans[i]<<endl; 

    }

    return 0;



}

    

// Faster C++ solution for the same problem (measured speedup: 13.755589070519408x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)temp[i]=a[i];

	qsort(a,n,sizeof(int),inc);

	for(int i=0;i<=n/2-1;i++)

	{

		if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

	for(int i=n/2;i<n;i++)

	{

		if(temp[i]>a[n/2-1])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp> // Common file

#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update



using namespace std ;

using namespace __gnu_pbds;



typedef tree<

pair<int , int> ,

null_type,

less< pair<int , int> >,

rb_tree_tag,

tree_order_statistics_node_update>

ordered_set;



int main()

{

	ios_base::sync_with_stdio(0) ;

	cin.tie(0) ;

	int n ;

	cin>>n ;

	int arr[n] ;

	for(int i = 0 ; i < n ; ++i)

		cin>>arr[i] ;

	ordered_set s ;

	for(int i = 0 ; i < n ; ++i)

		s.insert({arr[i] , i}) ;

	for(int i = 0 ; i < n ; ++i)

	{

		s.erase({arr[i] , i}) ;

		cout<<(*s.find_by_order(n/2-1)).first<<"\n";

		s.insert({arr[i], i}) ;

	}

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 5.317059438241603x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)temp[i]=a[i];

	qsort(a,n,sizeof(int),inc);

	for(int i=0;i<=n/2-1;i++)

	{

		if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

	for(int i=n/2;i<n;i++)

	{

		if(temp[i]>a[n/2-1])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    int n, med;

    cin >> n;

    int arr[n], neww[n];



    for (int i = 0; i < n; i++)

        cin >> arr[i], neww[i] = arr[i];



    sort(neww, neww + n);

    med = neww[n / 2 - 1];



    for (int i = 0; i < n; i++)

        cout << (arr[i] <= med ? neww[n / 2] : neww[n / 2 - 1]) << '\n';



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.248272548060362x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)temp[i]=a[i];

	qsort(a,n,sizeof(int),inc);

	for(int i=0;i<=n/2-1;i++)

	{

		if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

	for(int i=n/2;i<n;i++)

	{

		if(temp[i]>a[n/2-1])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

}
// Slower C++ solution:
//In The Name Of GOD



#include <bits/stdc++.h>



using namespace std;



typedef long long ll ;

typedef long double ld ;



const ll mod = 998244353;

const ll inf = 2000000000;

const ll infll = (ll)2*1000*1000*1000*1000*1000*1000;

const ll maxn = 2*1001+1;



#define pb push_back

#define pp pop_back

#define X first

#define Y second

#define IO ios_base::sync_with_stdio(false);



int main(){

	int n;

	cin >> n;

	const int m = n;

	pair<int,int> A[m];

	int where[m];

	for(int i=0;i<m;i++){

		cin>>A[i].X;

		A[i].Y=i;

	}

	sort(A,A+m);

	for(int i=0;i<n;i++){

		where[ A[i].Y ] = i;

	}

	int l = A[n/2-1].X, r = A[n/2].X;

	for(int i=0;i<n;i++){

		if(where[i]<n/2){

			cout << r << endl;

		}else{

			cout << l << endl;

		}

	}







}

// Faster C++ solution for the same problem (measured speedup: 5.180756460395251x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)temp[i]=a[i];

	qsort(a,n,sizeof(int),inc);

	for(int i=0;i<=n/2-1;i++)

	{

		if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

	for(int i=n/2;i<n;i++)

	{

		if(temp[i]>a[n/2-1])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define ft first

#define sd second

#define sz(x) ((int)x.size())



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



const int MAXN = 200 * 1000 + 321;













int n, ans[MAXN];

pii x[MAXN];



int main() {

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> x[i].ft, x[i].sd = i;

	sort(x, x + n);

	for (int i = 0; i < (n >> 1); i++)

		ans[x[i].sd] = x[n >> 1].ft;

	for (int i = n / 2; i < n; i++)

		ans[x[i].sd] = x[(n >> 1) - 1].ft;

	for (int i = 0; i < n; i++)

		cout << ans[i] << '\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.177858799077148x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)temp[i]=a[i];

	qsort(a,n,sizeof(int),inc);

	for(int i=0;i<=n/2-1;i++)

	{

		if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

	for(int i=n/2;i<n;i++)

	{

		if(temp[i]>a[n/2-1])printf("%d\n",a[n/2-1]);

		else printf("%d\n",a[n/2]);

	}

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define ld long double

#define pii pair<int,int>

#define pll pair<ll,ll>

#define rep(n) for(int i=0;i<n;i+=1)

#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );

#define sc(a) scanf("%d",&a);

#define scl(a) scanf("%lld",&a);

#define scf(a) ascanf("%f",&a);

#define fi first

#define se second

#define pu push_back

#define inf 1000000001

#define MOD 1000000007 

#define INF 100000000000001

const int MAXN = 2e5+10;

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    map<int,vector<int>> m;

    map<int,int> ans;

    int n;

    pii a[MAXN];

    int b[MAXN]={0};

    cin>>n;

    rep(n) 

    {

        cin>>a[i].fi;

        a[i].se = i;

        // m[a[i]].pu(i);

    }

    sort(a,a+n);

    rep(n)

    {

        if((i+1)<=n/2)

            ans[a[i].se] = a[n/2].fi;

        else

            ans[a[i].se] = a[n/2-1].fi;     

    }

    rep(n)

    {

        cout<<ans[i]<<endl; 

    }

    return 0;



}

    

// Faster C++ solution for the same problem (measured speedup: 2.6222958626902653x):
#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)

//cout << fixed << setprecision(8) << a << endl;

//cout << "Case " << ca << ": " << ans << endl;

#define Fast_Input ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int main ()

{

    long long int n,i,j;

    cin >> n;

    map <long long int,long long int> ma;

    vector <long long int > v;

    vector <long long int > m;



    for(i=0;i<n;i++)

    {

        long long int x;

        cin >> x;

        v.push_back(x);

        m.push_back(x);

    }



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



    for(i=0;i<(n/2);i++)

    {

        ma[v[i]]=v[(n/2)];

    }



    for(i=(n/2);i<n;i++)

    {

        ma[v[i]]=v[(n/2)-1];

    }



    for(i=0;i<n;i++)

    {

        cout << ma[m[i]] << endl;

    }





    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define ld long double

#define pii pair<int,int>

#define pll pair<ll,ll>

#define rep(n) for(int i=0;i<n;i+=1)

#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );

#define sc(a) scanf("%d",&a);

#define scl(a) scanf("%lld",&a);

#define scf(a) ascanf("%f",&a);

#define fi first

#define se second

#define pu push_back

#define inf 1000000001

#define MOD 1000000007 

#define INF 100000000000001

const int MAXN = 2e5+10;

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    map<int,vector<int>> m;

    map<int,int> ans;

    int n;

    pii a[MAXN];

    int b[MAXN]={0};

    cin>>n;

    rep(n) 

    {

        cin>>a[i].fi;

        a[i].se = i;

        // m[a[i]].pu(i);

    }

    sort(a,a+n);

    rep(n)

    {

        if((i+1)<=n/2)

            ans[a[i].se] = a[n/2].fi;

        else

            ans[a[i].se] = a[n/2-1].fi;     

    }

    rep(n)

    {

        cout<<ans[i]<<endl; 

    }

    return 0;



}

    

// Faster C++ solution for the same problem (measured speedup: 2.655069817442655x):
#include <bits/stdc++.h>

using namespace std;



#define    ll     long long int



const int N = 200005;

pair<int, int> ara[N];

int order[N];

int araa[N];



int compare(pair<int, int> a, pair<int, int> b)

{

    return a.second < b.second;

}



int main( )

{

    int n, i, j, k, l;

    cin >> n;

    l = n / 2;

    for (i = 0; i < n; i++) {

        cin >> ara[i].first;

        ara[i].second = i;

    }

    sort(ara, ara + n);

    for (i = 0; i < n; i++) {

        order[ara[i].second] = i;

        araa[i] = ara[i].first;

    }

    sort(ara, ara + n, compare);

    for (i = 0; i < n; i++) {

        j = order[ara[i].second];

        if (j >= l) {

            cout << araa[l - 1];

        }

        else {

            cout << araa[l];

        }

        cout << '\n';

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#define NUM 200003

using namespace std;



int main() {

	int n;

	cin >> n ;

	int a[NUM] = { 0 };

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

		cin >> a[i];

	}

	int v[NUM] = { 0 };

	copy(a, a + n + 1, v);

	sort(a + 1, a + n +1);

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

		if (v[i] > a[n/2])

			cout << a[ n / 2] << endl;

		else

			cout << a[(n / 2) + 1 ] << endl;



	}

	



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.5684237797845815x):
#include<bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)

#define repk(i,k,n) for (ll i = k; i <= (ll)(n); ++i)

#define MAX 500010

#define MOD 1000000007

typedef long long  ll;



using namespace std;



ll ans;



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



	ll N;

	cin >> N;



	vector<ll> X(N),cop(N);

	rep(i,N){

		cin >> X[i];

		cop[i] = X[i];

	}



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

	ll l = N/2 - 1;

	ll lx = cop[l];



	rep(i,N){

		if(X[i]<=lx){

			cout << cop[l+1] << endl;

		}

		else{

			cout << cop[l] << endl;

		}

	}





	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int main()

{ 

   int n;

   int a[200010]={};

   int b[200010]={};

   cin>>n;

   for(int i=0;i<n;i++){

       cin>>a[i];

       b[i]=a[i];

   }

   sort(b,b+n);

   int l=b[n/2-1],r=b[n/2];

   for(int i=0;i<n;i++){

       if(a[i]<=l) cout<<r<<endl;

       else cout<<l<<endl;

   }



}


// Faster C++ solution for the same problem (measured speedup: 2.59567433241833x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

#define all(v) v.begin(), v.end()

#define MOD 1000000007

const int INF = 1LL<<30;



int main(){

    int n;

    cin>>n;

    vector<ll> l(n),h(n);

    rep(i,n) cin>>l[i],h[i]=l[i];

    sort(all(h));

    ll a=h[n/2],b=h[n/2-1];



    //cout<<a<<" "<<b<<endl;

    rep(i,n){

        if(l[i]<=b) cout<<a<<endl;

        else cout<<b<<endl;

    }

    

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cstring>



#define loop(n) for(ll i=0;i<n;i++)



using namespace std;



typedef long long int ll;



int main() {

    ll n,x[200000],y[200000];

    cin >> n;

    loop(n) cin >> x[i];

    memcpy(y,x,sizeof(ll[200000]));

    sort(y,y+n);

    ll a[2] = {y[n/2-1],y[n/2]};

    loop(n) if(x[i] <= a[0]) cout << a[1] << endl; else cout << a[0] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2230592547730312x):
#include <cstdio>

#include <algorithm>

#include <cstring>



#define loop(n) for(ll i=0;i<n;i++)



using namespace std;



typedef long long int ll;



int main() {

    ll n,x[200000],y[200000];

    scanf("%ld",&n);

    loop(n) scanf("%ld",&x[i]);

    memcpy(y,x,sizeof(ll[200000]));

    sort(y,y+n);

    ll a[2] = {y[n/2-1],y[n/2]};

    loop(n) if(x[i] <= a[0]) printf("%ld\n",a[1]); else printf("%ld\n",a[0]);

}
// Slower C++ solution:
#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <vector>

#include <map>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 2e5 + 5;



int n;

vector<int> a;

int b[maxn];

bool cmp(int x, int y)

{

    return x > y;

}



int main()

{

    cin >> n;

    for(int i=1; i<=n; i++)

    {

        scanf("%d", &b[i]);

        a.push_back(b[i]);

    }

    sort(a.begin(), a.end(), cmp);

    for(int i=1; i<=n; i++)

    {

        int mid = n/2;

        if(b[i] < a[mid-1])

            printf("%d\n", a[mid-1]);

        else

            printf("%d\n", a[mid]);

    }

    return 0;

}

/****



****/


// Faster C++ solution for the same problem (measured speedup: 5.197579493957431x):
#include<stdio.h>

#include<stdlib.h>

int a[200005],temp[200005];

int inc(const void *a, const void *b)

{

    return *(int*)a-*(int*)b;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    for(int i=0;i<n;i++)temp[i]=a[i];

    qsort(a,n,sizeof(int),inc);

    for(int i=0;i<n;i++)

    {

        if(temp[i]>=a[n/2])printf("%d\n",a[n/2-1]);

        else printf("%d\n",a[n/2]);

    }

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

  double x[200000]={},m[200000]={},av=0;

  int min,n,idx,a,b;

  cin>>n;

  for(int i=0;i<n;i++){cin>>x[i];av+=x[i];}

  av/=n;

  for(int i=0;i<n;i++)m[i]=x[i];

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6315290937721698x):
#include<bits/stdc++.h>

using namespace std;

int main(){

  double av;

  int x[200000]={},m[200000]={},min,n,idx,a,b;

  cin>>n;

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

  for(int i=0;i<n;i++)m[i]=x[i];

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

  double x[200000]={},m[200000]={},av=0;

  int min,n,idx,a,b;

  cin>>n;

  for(int i=0;i<n;i++){cin>>x[i];av+=x[i];}

  av/=n;

  for(int i=0;i<n;i++)m[i]=x[i];

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6319726689738818x):
#include<bits/stdc++.h>

using namespace std;

int main(){

  double av;

  int x[200000]={},m[200000]={},min,n,idx,a,b;

  cin>>n;

  for(int i=0;i<n;i++){cin>>x[i];m[i]=x[i];}

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

  double x[200000]={},m[200000]={},av=0;

  int min,n,idx,a,b;

  cin>>n;

  for(int i=0;i<n;i++){cin>>x[i];av+=x[i];}

  av/=n;

  for(int i=0;i<n;i++)m[i]=x[i];

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6319726689738818x):
#include<bits/stdc++.h>

using namespace std;

int main(){

  double av;

  int x[200000]={},m[200000]={},n,a,b;

  cin>>n;

  for(int i=0;i<n;i++){cin>>x[i];m[i]=x[i];}

  sort(m,m+n);

  a=m[n/2];

  b=m[n/2-1];

  av=(a+b)/2;

  for(int i=0;i<n;i++)

    if(av>=x[i])cout<<a<<endl;

    else cout<<b<<endl;

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

using namespace std;



int main(){

    int N;

    int A[200000]={};

    cin >> N;

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

        cin >> A[i];

        A[i] -= (i+1);

    }

    sort(A,A+N);

    int b = A[N/2];

    long long sum=0;

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

        sum += abs(A[i] - b);

    }

    cout << sum << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.7912608236888923x):
#include <bits/stdc++.h>

using namespace std;

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

#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)

long long mo = 1e9 + 7;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> Pii;

typedef pair<ll,ll> Pll;

template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }

template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}

ld PI=3.14159265358979323846;



int main(){

    ll N;

    cin >> N;

    vector<ll> A(N);

    rep(i,N){

        cin >> A[i];

        A[i] -= i+1;

    }

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

    ll mid = A[N/2];

    ll ans = 0;

    rep(i,N){

        ans += abs(A[i] - mid);

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include<iostream>

#include<string>

#include<cstdlib>

#include<vector>

#include<algorithm>

#include<functional>



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

#define ll long long int



using namespace std;



int to_int(string s) {

  return atoi(s.c_str());

}



//vector<ll> a;



int main() {

  int n;

  cin >> n;



 // a.reserve(n);

  vector<int> a(300000);

  for(int i=0;i<n;i++) {

    cin >> a[i];

    a[i] -= i+1;

  }



  sort(a.begin(), a.begin()+n);

  long long  b;

  if(n%2 == 0) {

    b = a[n/2 -1];

  } else {

    b = a[(n-1)/2];

  }



  long long  r = 0;



  for(int i=0;i<n;i++) {

    r += abs(a[i] - b);

  }



  cout << r << endl;

return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.202928703945311x):
#include<iostream>

#include<string>

#include<cstdlib>

#include<vector>

#include<algorithm>

#include<functional>



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

#define ll long long int



using namespace std;



int to_int(string s) {

  return atoi(s.c_str());

}



//vector<ll> a;



int main() {

  int n;

  cin >> n;



 // a.reserve(n);

  vector<int> a;

  a.reserve(300000);

  for(int i=0;i<n;i++) {

    cin >> a[i];

    a[i] -= i+1;

  }



  sort(a.begin(), a.begin()+n);

  long long  b;

  if(n%2 == 0) {

    b = a[n/2 -1];

  } else {

    b = a[(n-1)/2];

  }



  long long  r = 0;



  for(int i=0;i<n;i++) {

    r += abs(a[i] - b);

  }



  cout << r << endl;

return 0;

}