stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#define maxn 300005

using namespace std;

int n,a[maxn],t[maxn],ans;

int main()

{

	scanf("%d",&n);

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

	{

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

		t[i]=a[i];

	}

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

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

	{

		int tmp=lower_bound(t+1,t+n+1,a[i])-t;

		if((tmp+i)%2) ans++;

	}

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#define maxn 300005

using namespace std;

int n,a[maxn],t[maxn],ans;

int main()

{

	scanf("%d",&n);

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

	{

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

		t[i]=a[i];

	}

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

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

	{

		int tmp=lower_bound(t+1,t+n+1,a[i])-t;

		if((tmp+i)%2) ans++;

	}

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;





}


// Optimized solution to the same problem (faster):
/*

貪欲

後ろから見る

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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

		

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#define endl '\n'

#include <algorithm>

using namespace std;





int main()

{

    int n,k;

    cin >> n;

    pair<int,int> a[n];

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

    {

        cin >> k;

        a[i] = {k,i};

    }

    sort(a,a+n);

    int c = 0;

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

    {

        int j = a[i].second;

        if(i%2 == 0 && j%2 != 0)

            c++;

        if(i%2 != 0 && j%2 == 0)

            c++;

    }

    cout << c/2 << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

using namespace __gnu_cxx;



int main(){

    int n;

    cin >> n;

    int arr[n];

    int ind = 0;

    while(ind < n)

        cin >> arr[ind++];

    int op1 = 0;

    vector<int> arr2;

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

        arr2.push_back(arr[i]);

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

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

        auto bs = lower_bound(arr2.begin(), arr2.end(), arr[i]);



        int x = (bs - arr2.begin());

        if (i % 2 != x % 2)

            op1++;

    }

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

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll M=1e5+100;

ll a[M] , b[M];

map<ll , bool> m;

int main()

{

    ll n , ans=0;

    cin>>n;

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

    {

        cin>>a[i];

        b[i]=a[i];

        if( i % 2 == 0)

        {

            m[a[i]]=true;

        }

    }

    sort( b , b+n );

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

    {

        if( i % 2 == 0 && m[b[i]] == false )

        {

            ans++;

        }

    }

    cout<<ans;

    return 0;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//In the name of God

#include<bits/stdc++.h>



using namespace std ;



const int N = (int)1e5 + 10 ;



int n ;

pair < int , int > a[N] ;



int32_t main() {

	cin >> n ;

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

		cin >> a[j].first ;

		a[j].second = j ; 

	}

	sort(a , a + n) ;

	int res = 0 ;

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

		(res += a[i].second % 2 != i % 2) ;

	cout << res << endl ; 

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define F first

#define S second

#define PB push_back

#define LB lower_bound

#define UB upper_bound

#define SP fixed << setprecision(10)

#define ER(x) cout << #x << " = " << x << endl;



using namespace std;



typedef long long ll;

typedef pair <int , int> pii;

typedef double DB;



const int N = 100100;

pii a[N];



int main(){



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

	

	int n , t(0);

	cin >> n;



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

		cin >> a[i].F;

		a[i].S = i;

	}

	

	sort(a , a+n);



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

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

			t++;

		}

	}



	cout << t/2 << endl;



	return 0;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 1e5 + 10;

int n, ans, u, d, ar[2][N], tmp[N];

map <int, bool> mp;



int main() {

	cin >> n;

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

		if (i & 1)

			cin >> ar[1][d], tmp[i] = ar[1][d++];

		else

			cin >> ar[0][u], tmp[i] = ar[0][u++];

	}

	sort(ar[0], ar[0] + u);

	sort(ar[1], ar[1] + d);

	sort(tmp, tmp + n);

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

		mp[tmp[i]] = (i & 1);

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

		if (i & 1) {

			if (mp[ar[1][i / 2]] != (i & 1))

				ans++;

		}

		else {

			if (mp[ar[0][i / 2]] != (i & 1))

				ans++;

		}

	}

	cout << (ans + 1) / 2;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem: