stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int n;

    cin >> n;

    vector<int>a(n);

    map<int,int> m;

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

        cin >> a[i];

        m.insert(make_pair(a[i],i));

    }

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

    int ans = 0;

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

        if(m[a[i]] % 2 != i % 2){

            ans++;

        }

    }

    int temp = ans % 2;

    ans /= 2;

    ans += temp;

    cout << ans;

    return 0;

}


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

#include<algorithm>

using namespace std;

#define MAXN 100010

int n,ans;

struct node

{

	int x,id;

}a[MAXN];

bool cmp(node A,node B)

{

	return A.x<B.x;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

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

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

		ans+=((a[i].id&1)!=(i&1));

	printf("%d\n",ans/2);

}
// Slower C++ solution:
//============================================================================

// Author      : JCH

// Copyright   :

// Description : Contest ACM Div2

//============================================================================



#include <bits/stdc++.h>

#define endl '\n'

using namespace std;



#define pii pair<int,int>



vector<pii> A;

int n, x;



int main() {



	cin >> n;

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

		cin >> x;

		A.push_back(pii(x,i));

	}



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



	int c = 0;

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

		if ((A[i].second + i) % 2)

			c++;

	}

	cout << c << endl;



	return 0;

}


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

#include<algorithm>

using namespace std;

#define MAXN 100010

int n,ans;

struct node

{

	int x,id;

}a[MAXN];

bool cmp(node A,node B)

{

	return A.x<B.x;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

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

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

		ans+=((a[i].id&1)!=(i&1));

	printf("%d\n",ans/2);

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

using namespace std;

const int maximo = 1e5;

int arr[maximo+10];

int ordenado[maximo+10];

int cant = 0;

int main()

{

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

	//freopen(".in","r",stdin);

	//entrada

	int n ; cin >> n;

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

        {cin >> arr[i];ordenado[i]=arr[i];}



    //solution

    sort(ordenado,ordenado+n);

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

    {

        int a = lower_bound(ordenado,ordenado+n,arr[i])-arr;

        if (abs(a-i)%2 != 0) cant++;

    }

    cout << cant/2 << "\n";











    return 0;

}


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

#include<algorithm>

using namespace std;

#define MAXN 100010

int n,ans;

struct node

{

	int x,id;

}a[MAXN];

bool cmp(node A,node B)

{

	return A.x<B.x;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

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

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

		ans+=((a[i].id&1)!=(i&1));

	printf("%d\n",ans/2);

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

using namespace std;



const int MAXN = 1e5 + 10;

int n, ans;

pair <int, int> in[MAXN];



int main() {

	cin >> n;

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

		cin >> in[i].first;

		in[i].second = i;

	}

	sort(in, in + n);

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

		if(in[i].second % 2 != i % 2)

			ans++;

	}

	cout << ans;

	return 0;

}

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

#include<algorithm>

using namespace std;

#define MAXN 100010

int n,ans;

struct node

{

	int x,id;

}a[MAXN];

bool cmp(node A,node B)

{

	return A.x<B.x;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

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

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

		ans+=((a[i].id&1)!=(i&1));

	printf("%d\n",ans/2);

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

using namespace std;



const int MAXN = 1e5 + 10;

int n, ans;

pair <int, int> in[MAXN];



int main() {

	cin >> n;

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

		cin >> in[i].first;

		in[i].second = i;

	}

	sort(in, in + n);

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

		if(in[i].second % 2 != i % 2)

			ans++;

	}

	cout << ans / 2;

	return 0;

}

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

#include<algorithm>

using namespace std;

#define MAXN 100010

int n,ans;

struct node

{

	int x,id;

}a[MAXN];

bool cmp(node A,node B)

{

	return A.x<B.x;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

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

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

		ans+=((a[i].id&1)!=(i&1));

	printf("%d\n",ans/2);

}
// Slower C++ solution:
#include "iostream"

#include "climits"

#include "list"

#include "queue"

#include "stack"

#include "set"

#include "functional"

#include "algorithm"

#include "math.h"

#include "utility"

#include "string"

#include "map"

#include "unordered_map"

#include "iomanip"

#include "random"



using namespace std;

const long long int MOD = 1000000007;



long long int power(long long int x, long long int n, long long int M) {

	long long int tmp = 1;



	if (n > 0) {

		tmp = power(x, n / 2, M);

		if (n % 2 == 0) tmp = (tmp*tmp) % M;

		else tmp = (((tmp*tmp) % M)*x) % M;

	}

	return tmp;

}



long long int N, M, K, Q, W, H, L, R;

long long int ans;





int main() {

	ios::sync_with_stdio(false);

	cin >> N;

	map<int, int>m;

	int num[100001] = {};

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

		cin >> num[i];

		m[num[i]] = i;

	}

	sort(num, num + N);

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

		ans += abs(i - m[num[i]]) % 2;

	}

	cout << ans / 2 << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3894405148065148x):
#include "iostream"

#include "climits"

#include "list"

#include "queue"

#include "stack"

#include "set"

#include "functional"

#include "algorithm"

#include "string"

#include "map"

#include "unordered_map"

#include "unordered_set"

#include "iomanip"

#include "cmath"

#include "random"

#include "bitset"

#include "cstdio"

#include "numeric"



using namespace std;



const int MOD = 1000000007;

//const int MOD = 998244353;



long long int N, M, K, H, W, L, R;

//int N, M, K, H, W, L, R;



int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);



	cin >> N;

	vector<int>v(N);

	for (auto &i : v)cin >> i;

	auto w = v;

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

	map<int, int>m;

	for (int i = 0; i < N; i++)m[v[i]] = i;

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

		if (m[w[i]] % 2 != i % 2)M++;

	}

	cout << M / 2 << endl;

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

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<queue>

#include<vector>

#include <bitset>

#include<math.h>

using namespace std;

#define INF 10000000

#define MOD 1000000007

typedef long long ll;

typedef pair<ll,int> P;





int main(){

    int N,S[110000];

    P A[110000];

    cin>>N;

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

        cin>>A[i].first;

        A[i].second=i+1;

    } 

    sort(A,A+N);

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

        S[A[i].second]=i+1;

    }

    int count=0;

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

        if(S[i]%2!=i%2) count++;

    }

    cout<<count/2<<endl;





}


// Faster C++ solution for the same problem (measured speedup: 2.797037221677944x):
/*

貪欲

後ろから見る

DP

順位表をチェック

二分探索

不変なもの・偶奇に注目



*/

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<queue>

#include<vector>

#include <bitset>

#include <cmath>

#include <limits>

#include <iostream>

#include <map>

#include<tuple>

#include<set>

using namespace std;

#define INF 1100000000000000000

#define MAX 100000

#define MOD 1000000007

typedef long long ll;

typedef pair<ll,int> P;

//typedef pair< pair<int,int>,pair<int,int> > p;

#define int ll

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/

#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

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

template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}

template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}

//__builtin_popcount(S);

//C.erase(unique(C.begin(),C.end()),C.end());



signed main(){

    int N;

    cin>>N;

    vector<P> V(N);

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

        cin>>V[i].first;

        V[i].second=i;

    }

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



    int count=0;

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

        if(V[i].second%2!=i%2) count++;

    }

    cout<<count/2<<endl;

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

#define ll long long



using namespace std;



int n;

int x;

int a[100005];

map<int,int> mp;

int ans;



int main()

{

          cin>>n;

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

          {

                    cin>>a[i];

                    mp[a[i]]=i;

          }

          sort(a,a+n);

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

                    if(i%2!=mp[a[i]]%2)

                              ans++;

          cout<<(ans+1)/2;

}


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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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



using namespace std;



typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<vi> vvi;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int n, x;

    cin>>n;

    map<int, int> idex;

    vi numbers;

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

        cin>>x;

        idex[x] = i;

        numbers.push_back(x);

    }

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

    int cntp = 0, cnti = 0;

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

        x = numbers[i];

        int d = abs(idex[x]-i);

        if(d%2) { cntp += (!(idex[x]%2)); cnti += (idex[x]%2); }

    }

    cout<<max(cntp,cnti)<<endl;

    return 0;

}


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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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



using namespace std;



int a[100002];

map <int,int> m;



int main()

{   

    int cant,minim=0;

    cin>>cant;

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

    {

        cin >> a[i];

        m[a[i]]=i;

    }

    sort(a,a+cant);

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

    {

        if(abs(m[a[i]]-i)%2)

        minim++;

    }

    cout<< minim/2 <<endl;

	//system("pause");

	return 0;

}


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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



#define $ system("pause")

#define MOD ll(1e9 + 7)

#define MAXN 100010

#define inf (ll)1e18



template<typename T> inline T smin(T &a, const T &b) { return a > b ? a = b : a; }

template<typename T> inline T smax(T &a, const T &b) { return a < b ? a = b : a; }

inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }

ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }

ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }



int n, arr[MAXN];

map<int, int> mp;



int main() {

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

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

		cin >> arr[i];

		mp[arr[i]] = i;

	}

	int answer = 0;

	sort(arr, arr + n);

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

		if ((i ^ mp[arr[i]]) & 1)

			answer++;

	cout << (answer >> 1) << '\n';

	//$;

	return 0;

}

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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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

using namespace std;

const int MAXn = 1e5 + 10;

int n, ar[MAXn], cnt;

pair<int ,int> p[MAXn];

int main() {

	cin >> n;

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

		cin >> p[i].first;

		p[i].second = i;

	}

	sort(p, p + n);

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

		if (p[i].second % 2 != i % 2)

			cnt++;

	cout << cnt/2;

}

		

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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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



using namespace std;



const int MAXN = 1e5 + 5;



pair <int, int> a[MAXN];



int b[MAXN];



int main() {

	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

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

		cin >> a[i].first;

		a[i].second = i;

	}		

	sort(a, a + n);

	int ans = 0;

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

		if ((a[i].second % 2) != (i % 2))

			ans++;

	cout << ans / 2 << endl;

	return 0;

}

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

#include<algorithm>

using namespace std;



const int MAXN=3e5+5;



int n;

pair<int,int> a[MAXN];



int main(){



    scanf("%d",&n);

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

        scanf("%d",&a[i].first),a[i].second=i;

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

    int cnt=0;

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

        if((a[i].second&1)!=(i&1))

            cnt++;

    printf("%d",cnt/2);



    fclose(stdin);

    fclose(stdout);

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

#define ll long long



using namespace std;



int n;

int x;

int a[100005];

map<int,int> mp;

int ans;



int main()

{

          cin>>n;

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

          {

                    cin>>a[i];

                    mp[a[i]]=i;

          }

          sort(a,a+n);

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

                    if(i%2!=mp[a[i]]%2)

                              ans++;

          cout<<(ans+1)/2;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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



using namespace std;



typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<vi> vvi;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int n, x;

    cin>>n;

    map<int, int> idex;

    vi numbers;

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

        cin>>x;

        idex[x] = i;

        numbers.push_back(x);

    }

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

    int cntp = 0, cnti = 0;

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

        x = numbers[i];

        int d = abs(idex[x]-i);

        if(d%2) { cntp += (!(idex[x]%2)); cnti += (idex[x]%2); }

    }

    cout<<max(cntp,cnti)<<endl;

    return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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



using namespace std;



int a[100002];

map <int,int> m;



int main()

{   

    int cant,minim=0;

    cin>>cant;

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

    {

        cin >> a[i];

        m[a[i]]=i;

    }

    sort(a,a+cant);

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

    {

        if(abs(m[a[i]]-i)%2)

        minim++;

    }

    cout<< minim/2 <<endl;

	//system("pause");

	return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



#define $ system("pause")

#define MOD ll(1e9 + 7)

#define MAXN 100010

#define inf (ll)1e18



template<typename T> inline T smin(T &a, const T &b) { return a > b ? a = b : a; }

template<typename T> inline T smax(T &a, const T &b) { return a < b ? a = b : a; }

inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }

ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }

ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }



int n, arr[MAXN];

map<int, int> mp;



int main() {

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

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

		cin >> arr[i];

		mp[arr[i]] = i;

	}

	int answer = 0;

	sort(arr, arr + n);

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

		if ((i ^ mp[arr[i]]) & 1)

			answer++;

	cout << (answer >> 1) << '\n';

	//$;

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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

using namespace std;

const int MAXn = 1e5 + 10;

int n, ar[MAXn], cnt;

pair<int ,int> p[MAXn];

int main() {

	cin >> n;

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

		cin >> p[i].first;

		p[i].second = i;

	}

	sort(p, p + n);

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

		if (p[i].second % 2 != i % 2)

			cnt++;

	cout << cnt/2;

}

		

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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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



using namespace std;



const int MAXN = 1e5 + 5;



pair <int, int> a[MAXN];



int b[MAXN];



int main() {

	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

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

		cin >> a[i].first;

		a[i].second = i;

	}		

	sort(a, a + n);

	int ans = 0;

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

		if ((a[i].second % 2) != (i % 2))

			ans++;

	cout << ans / 2 << endl;

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100005

int n;

struct node{

	int v,p;

}a[MAXN];

bool cmp(node x,node y)

{

	return x.v<y.v;

}

int main()

{

	int ans=0;

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i].v);

		a[i].p=i;

	}

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

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

		if((a[i].p+i)%2) ans++;

	printf("%d\n",ans/2);

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

#include <bits/stdc++.h>



using namespace std;



int main()

{

    int len, aux, cant = 0;

    cin>>len;

    vector<int> nums;

    nums.assign(len,0);

    map<int,int> dict;

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

    {

        cin>>aux;

        dict.insert(pair<int,int>(aux,i));

        nums[i] = aux;

    }

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

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

    {

        if(dict[nums[i]]%2 != i%2)

            cant++;

    }

    cout<<cant/2<<endl;

    return 0;

}


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

#include <cstdio>

 

#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)

 

using namespace std;

 

const int MAXN = 3e5 + 10;

 

int N;

pair <int, int> a[MAXN];

 

int main()

{

	//REDIRECT("sort");

 

	int cnt = 0;

	scanf("%d", &N);

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

		scanf("%d", &a[i].first), a[i].second = i;

	sort(&a[1], &a[N + 1]);

 

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

		if((a[i].second % 2) != (i % 2))

			cnt++;

 

	printf("%d\n", cnt / 2);

 

	CLOSEALL();

 

	return 0;

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



using namespace std;



int main()

{

    vector<pair<int,int> >ar;

    int N,puntero=0,temp,sol=0;



    cin>>N;



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

    {

        cin>>temp;

        ar.push_back(pair<int,int>(temp,i));

    }

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



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

    {

      if(ar[i].second%2!=i%2)

        sol+=1;

    }





    cout <<  sol/2<< endl;

    return 0;

}


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

#include <cstdio>

 

#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)

 

using namespace std;

 

const int MAXN = 3e5 + 10;

 

int N;

pair <int, int> a[MAXN];

 

int main()

{

	//REDIRECT("sort");

 

	int cnt = 0;

	scanf("%d", &N);

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

		scanf("%d", &a[i].first), a[i].second = i;

	sort(&a[1], &a[N + 1]);

 

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

		if((a[i].second % 2) != (i % 2))

			cnt++;

 

	printf("%d\n", cnt / 2);

 

	CLOSEALL();

 

	return 0;

}