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

#include <algorithm>

using namespace std;



int main()

{

    int N;

    pair<int, int> A[100000];

    cin >> N;

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

    {

        pair<int, int> temp;

        temp.second = i;

        cin >> temp.first;

        A[i] = temp;

    }

    sort(A, A + N);

    int result = 0;

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

        if(abs(A[i].second - i) % 2 != 0)

            result++;

    cout << result / 2 << endl;

    return 0;

}


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

using namespace std;



int main() {

    int n;

    cin >> n;



    vector< int >v(n);

    vector< int >w(n);

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

        cin >> v[i];

        w[i] = i;

    }



    sort(w.begin(), w.end(), [&](int i, int j) {

        return v[i] < v[j];

    });



    int ans = 0;

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

        ans += (i&1)^(w[i]&1);

    }



    cout << ans/2 << endl;



    return 0;

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

#include <algorithm>

using namespace std;



int main()

{

    int N;

    pair<int, int> A[100000];

    cin >> N;

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

    {

        pair<int, int> temp;

        temp.second = i;

        cin >> temp.first;

        A[i] = temp;

    }

    sort(A, A + N);

    int result = 0;

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

        if(abs(A[i].second - i) % 2 != 0)

            result++;

    cout << result / 2 << endl;

    return 0;

}


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

#define ll          long long int

#define uu          first

#define vv          second

#define pii         pair<int,int>

#define pll         pair<ll,ll>

#define INF         1e9

#define fastRead    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;



const int MAX = 1e6 + 6;



int n;



int main()

{

    fastRead;

    int n;

    cin>>n;

    

    vector<int>vec(n) , v1 , v2 , tmp;

    for(int i =0 ; i < n ; i++ ) cin>>vec[i];

    tmp = vec;

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

    

    map<int,int>mp;

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

        mp[tmp[i]] = 1;

    }

    int ans = 0;

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

        if(mp[vec[i]]) ans++;

    }

    

    cout<<ans<<'\n';

    return 0;

    

    

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

#include <algorithm>

using namespace std;



int main()

{

    int N;

    pair<int, int> A[100000];

    cin >> N;

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

    {

        pair<int, int> temp;

        temp.second = i;

        cin >> temp.first;

        A[i] = temp;

    }

    sort(A, A + N);

    int result = 0;

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

        if(abs(A[i].second - i) % 2 != 0)

            result++;

    cout << result / 2 << endl;

    return 0;

}


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

#include<vector>

#include<cstring>

#include<map>

#include<bitset>

#include<assert.h>

#include<algorithm>

#include<iomanip>

#include<cmath>

#include<set>

#include<queue>

#define long long long

using namespace std;

const int N=1e6,mod=1e9+7;

int aa[N+2],bb[N+2];

int main()

{

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

  int n;cin>>n;int ans=0;set<int>st;

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

  {

    cin>>aa[i];

    if(i%2)st.insert(aa[i]);

  }

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

  for(int i=1;i<=n;i+=2)if(st.find(aa[i])==st.end())ans++;

  cout<<ans<<endl;

  return 0;

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

#include <algorithm>

using namespace std;



int main()

{

    int N;

    pair<int, int> A[100000];

    cin >> N;

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

    {

        pair<int, int> temp;

        temp.second = i;

        cin >> temp.first;

        A[i] = temp;

    }

    sort(A, A + N);

    int result = 0;

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

        if(abs(A[i].second - i) % 2 != 0)

            result++;

    cout << result / 2 << endl;

    return 0;

}


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

using namespace std;

#define x first

#define y second



int n, a[100005], ans;

pair<int, int> pr[100005];

bool b[100005];



int main() {

	scanf("%d", &n);

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

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

		pr[i].x = a[i];

		pr[i].y = i;

	}

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

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

		b[pr[i].y] = true;

	}

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

		if ( !b[i] ) ans++;

	}

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

	return 0;

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

#include <algorithm>

using namespace std;



int main()

{

    int N;

    pair<int, int> A[100000];

    cin >> N;

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

    {

        pair<int, int> temp;

        temp.second = i;

        cin >> temp.first;

        A[i] = temp;

    }

    sort(A, A + N);

    int result = 0;

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

        if(abs(A[i].second - i) % 2 != 0)

            result++;

    cout << result / 2 << endl;

    return 0;

}


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

using namespace std;



int x,y,z,n,m;

char tmp;

pair<int,int> ar[100005];

string s1,s2;



int main() {

	cin >> x;

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

		cin >> ar[i].first;

		ar[i].second = i;		

	}

	stable_sort(ar,ar+x);

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

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

			n++;

		}

	}

	cout << n/2;

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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define MXN 100010



int n,

	a[MXN];



/*

[Discretization] by.YXH_XianYu

void Discretization(int a[], int n);

	a[] : Array that will be Modified

	n   : the Length of Array a

This function can discretize a[]. 

(It can't Remove duplicate elements)

 */

struct Sort{

		int va,no;

	}s[MXN];

bool sortComp(Sort a, Sort b){

	return a.va<b.va;

}

void Discretization(int a[], int n){

	

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

		s[i].va=a[i],

		s[i].no=i;

	std::sort(s+1,s+n+1,sortComp);

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

		a[s[i].no]=i;

	return;

}







int main(){

	

	scanf("%d",&n);

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

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

	Discretization(a,n);

	int ans=0;

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

		if( (a[i]-i)&1 )

			ans++;

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

	//system("pause");

	return 0;

}


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

#include <cstring>

#include <cctype>

#include <algorithm>

#include <map>

using namespace std;

const int N = 1e5+5;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

int n, ans;

pair<int, int> p[N];

int main()

{

    n = read(); 

    for(int i = 1; i <= n; ++i) p[i].first = read(), p[i].second = i&1;

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

    for(int i = 2; i <= n; i += 2) ans += p[i].second;

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

    return 0;

}
// Slower C++ solution:
/*

	Name: F-冒泡排序 

	Author: RoseKey

	Date: 14/02/19 16:49

	Description: 模拟+找规律 

*/



#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <cstdio>

#include <vector>

#include <bitset>

#include <cstring>

#include <utility>

#include <iostream>

#include <algorithm>

#define LL long long

#define Rg register

#define RI register int

#define RC register char

#define ed puts("") 

#define pair pair<LL,LL>

#define space putchar(' ')

using namespace std;

    

template <typename tp> inline void read(tp & x)

{	

    x=0;

    RI f=1;

    RC c=getchar();

    while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar(); }

    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} 

 	x*=f;

} 	

    

template <typename Tp> inline void print(Tp x)

{		

    if(x<0) x=-x,putchar('-');

    if(x>9) print(x/10);

    putchar(x%10+'0');

}



int n;

LL ans;

LL b[100005];

struct qwq

{

	int num;

	int val;

	bool flag;

}a[100005];



inline bool cmp(qwq x,qwq y)

{

	return x.val<y.val;

}

//qwq

int main()

{

	read(n);

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

		read(a[i].val),a[i].num=i;

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

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

	{

		int k=i;

		int kk=a[i].val;

		int h=i%2;

		int hh=a[i].num%2;

		if(h==hh) a[i].flag=1;

		if(a[i].flag) continue;

	}

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

	{

		if(a[i].flag) continue;

		ans++;

	}

	if(ans==0)

	{

		print(0);

		return 0;

	}

	print(ans/2);

	return 0;

}

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

#include <cstring>

#include <cctype>

#include <algorithm>

#include <map>

using namespace std;

const int N = 1e5+5;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

int n, ans;

pair<int, int> p[N];

int main()

{

    n = read(); 

    for(int i = 1; i <= n; ++i) p[i].first = read(), p[i].second = i&1;

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

    for(int i = 2; i <= n; i += 2) ans += p[i].second;

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

    return 0;

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

using namespace std;

int n, ans;

struct node {

	int val, st;

}a[100005];

bool cmp(node t, node b) {

	return t.val < b.val;

}

int main() {

	scanf ("%d", &n);

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

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

		a[i].st = i;

	}

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

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

		if ((a[i].st - i) % 2)

			ans++;

	}

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

	return 0;

}

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

#include <cstring>

#include <cctype>

#include <algorithm>

#include <map>

using namespace std;

const int N = 1e5+5;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

int n, ans;

pair<int, int> p[N];

int main()

{

    n = read(); 

    for(int i = 1; i <= n; ++i) p[i].first = read(), p[i].second = i&1;

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

    for(int i = 2; i <= n; i += 2) ans += p[i].second;

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

    return 0;

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

using namespace std;

#define N 100005

#define gc getchar

#define ll long long

#define lb(x) ((x)&(-(x)))

int n,ans;struct node {int id,v;}a[N];

int rd()

{

    bool fl=0;int res=0;char c=0;

    while(!isdigit(c)) fl|=c=='-',c=gc();

    while(isdigit(c)) res=(res<<1)+(res<<3)+(c&15),c=gc();

    return fl?-res:res;

}

bool cmp(node x,node y) {return x.v<y.v;}

int main()

{

    n=rd();for(int i=1;i<=n;++i) a[i].id=i,a[i].v=rd();sort(a+1,a+n+1,cmp);

    for(int i=1;i<=n;++i) if((i&1)!=(a[i].id&1)) ++ans;printf("%d\n",ans>>1);

}


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

#include <cstring>

#include <cctype>

#include <algorithm>

#include <map>

using namespace std;

const int N = 1e5+5;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

int n, ans;

pair<int, int> p[N];

int main()

{

    n = read(); 

    for(int i = 1; i <= n; ++i) p[i].first = read(), p[i].second = i&1;

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

    for(int i = 2; i <= n; i += 2) ans += p[i].second;

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

    return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#pragma comment(linker, "/stack:16777216")

#include <string>

#include <vector>

#include <map>

#include <list>

#include <iterator>

#include <set>

#include <queue>

#include <iostream>

#include <sstream>

#include <stack>

#include <deque>

#include <cmath>

#include <memory.h>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <algorithm>

#include <utility>

#include <time.h>

using namespace std;



#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)

#define REP(i, N) FOR(i, 0, N)

#define RREP(i, N) RFOR(i, N, 0)

#define FILL(A,value) memset(A,value,sizeof(A))



#define ALL(V) V.begin(), V.end()

#define SZ(V) (int)V.size()

#define PB push_back

#define MP make_pair

#define Pi 3.14159265358979



typedef long long Int;

typedef unsigned long long UINT;

typedef vector <int> VI;

typedef pair <int, int> PII;



const int INF = 1000000000;

const int MAX = 200000;

const int ADD = 500107;



int n;

int A[MAX];

VI B;





int main()

{

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

	

	cin >> n;

	FOR (i,0,n)

	{

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

	    B.PB(A[i]);

	}

	

	sort(ALL(B));

	int res = 0;

	

	FOR (i,0,n)

	{

	    int x = lower_bound(ALL(B), A[i]) - B.begin();

	    if ((x % 2) != (i % 2)) ++ res;

	}

    

    

    cout << res/2 << endl;

	   

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.255999016958593x):
#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);

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

#include <bits/stdc++.h>



using namespace std;



int main()

{

    int a,d,mp=0,mi=0;

    map<int,int> b;

    vector<int>c;



    cin>>a;

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

    {

        cin>>d;

        c.push_back(d);

        b[d]=i;

    }



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

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

    {

        d=b[c[i]];

        if((abs(d-i))%2!=0)

        {

            if(d%2==0)mp++;

            else mi++;

        }





    }



    cout<<max(mp,mi)<<"\n";



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.29547282493247x):
#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);

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

using namespace std;



#define endl '\n'



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);



	int n;

	cin >> n;



	set<int> I;

	vector<int> ord(n);

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

	{

		cin >> ord[i];

		if(i & 1)

			I.insert(ord[i]);

	}



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

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

		I.erase(ord[i]);



	cout << I.size() << endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.348044380436724x):
#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);

}
// 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.345682191532194x):
#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);

}
// 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.234258090056796x):
#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);

}
// 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.298966685325691x):
#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);

}
// 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.216648194507956x):
#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);

}
// 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.2176728330743165x):
#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);

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#pragma comment(linker, "/stack:16777216")

#include <string>

#include <vector>

#include <map>

#include <list>

#include <iterator>

#include <set>

#include <queue>

#include <iostream>

#include <sstream>

#include <stack>

#include <deque>

#include <cmath>

#include <memory.h>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <algorithm>

#include <utility>

#include <time.h>

using namespace std;



#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)

#define REP(i, N) FOR(i, 0, N)

#define RREP(i, N) RFOR(i, N, 0)

#define FILL(A,value) memset(A,value,sizeof(A))



#define ALL(V) V.begin(), V.end()

#define SZ(V) (int)V.size()

#define PB push_back

#define MP make_pair

#define Pi 3.14159265358979



typedef long long Int;

typedef unsigned long long UINT;

typedef vector <int> VI;

typedef pair <int, int> PII;



const int INF = 1000000000;

const int MAX = 200000;

const int ADD = 500107;



int n;

int A[MAX];

VI B;





int main()

{

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

	

	cin >> n;

	FOR (i,0,n)

	{

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

	    B.PB(A[i]);

	}

	

	sort(ALL(B));

	int res = 0;

	

	FOR (i,0,n)

	{

	    int x = lower_bound(ALL(B), A[i]) - B.begin();

	    if ((x % 2) != (i % 2)) ++ res;

	}

    

    

    cout << res/2 << endl;

	   

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.253112079380101x):
#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 <bits/stdc++.h>



using namespace std;



int main()

{

    int a,d,mp=0,mi=0;

    map<int,int> b;

    vector<int>c;



    cin>>a;

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

    {

        cin>>d;

        c.push_back(d);

        b[d]=i;

    }



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

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

    {

        d=b[c[i]];

        if((abs(d-i))%2!=0)

        {

            if(d%2==0)mp++;

            else mi++;

        }





    }



    cout<<max(mp,mi)<<"\n";



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.292564205763241x):
#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;



#define endl '\n'



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);



	int n;

	cin >> n;



	set<int> I;

	vector<int> ord(n);

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

	{

		cin >> ord[i];

		if(i & 1)

			I.insert(ord[i]);

	}



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

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

		I.erase(ord[i]);



	cout << I.size() << endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.3451068855392725x):
#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);

}