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

#include <iostream>

#include <cstring>

#include <vector>

#include <cstdio>

#include <stack>

#include <queue>

#include <cmath>

#include <map>

#include <set>

#define F first

#define S second

#define PII pair<int, int>

typedef long long LL;





using namespace std;



const int N = 1e5 + 10;

const LL INF = 1e16;

vector<LL> v;

LL n, a[N], r[N], ans;

map<int, bool> mp;



int main() {

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

  cin >> n;

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

    cin >> a[i];

    if (i % 2)

      mp[a[i]] = true;

    r[i] = a[i];

  }

  sort(r, r + n);

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

    if (i % 2 && !mp[r[i]])

      ans++;

  }

  cout << ans;

  return 0;

}


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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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



using namespace std;



const int N = 1e5 + 100;



typedef pair<int,int> pii;



pii a[N];

int n, cnt;



int main(){

	cin >> n;

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

		int x;

		cin >> x;

		a[i] = pii(x, i);

	}

	sort(a, a + n);

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

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

			cnt++; 	

	}

	return cout << cnt / 2, 0;

}


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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

inline void _read(int &x)

{

	x = 0;

	char t = getchar();

	while (!isdigit(t)) t = getchar();

	while (isdigit(t))

	{

		x = x * 10 + t - '0';

		t = getchar();

	}

}

 

const int MAXN = 1e5 + 10;

int n, ans;

pair <int, int> in[MAXN];

 

int main()

{

	_read(n);

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

	{

		_read(in[i].first);

		in[i].second = i;

	}

	sort(in, in + n);

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

	{

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

			ans++;

	}

	printf("%d", ans);

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<cstring>

#include<algorithm>

#include<set>

#define SF scanf

#define PF printf

#define MAXN 300010

#define INF 0x3FFFFFFF

using namespace std;

typedef long long ll;

int n,x,ans,suma,sumb;

set<int> a,b;

int main(){

	SF("%d",&n);

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

		SF("%d",&x);

		if(i%2==1)

			a.insert(x);

		else

			b.insert(x);

	}

	a.insert(INF);

	b.insert(INF);

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

		if(i%2==1){

			if(*a.begin()>*b.begin()){

				suma++;

				int x=*b.begin();

				b.erase(x);	

			}

			else{

				int x=*a.begin();

				a.erase(x);	

			}

		}

		else{

			if(*a.begin()<*b.begin()){

				sumb++;

				int x=*a.begin();

				a.erase(x);	

			}

			else{

				int x=*b.begin();

				b.erase(x);	

			}

		}

	}

	PF("%d",max(suma,sumb));

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<cstring>

#include<algorithm>

using namespace std;

struct node

{

    int x=0,p=0;

};

bool cmp(node a,node b)

{

   return   a.x<b.x;

}

int main()

{   node a[100005];

    node b[100005];

    int l=1,n,i;

    scanf("%d",&n);

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

    {

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

        a[i].p=i;

    }

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

    int ans=0;

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

    {

        if(abs(a[i].p-i)%2!=0)

        {

            ans++;

        }

    }

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

    return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,ans;

struct A{

	int id,val;

}a[100000+10];

bool cmp(A a,A b){

	return a.val<b.val;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i].val),a[i].id=i;

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

//	for(int i=1;i<=n;i++)a[i].id=i;

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

		if(abs(i-a[i].id)&1)ans++;

	}

	ans/=2;

	cout<<ans<<endl;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

struct node{

	int v,id;

} a[100010];

bool cmp(node t,node b)

{

	return t.v<b.v;

}

int main()

{

	int n,ans=0;

	cin>>n;

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

	{

		cin>>a[i].v;

		a[i].id=i;

	}

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

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

	{

		int del=abs(a[i].id-i);

		if(del&1) ans++;

	}

	cout<<ans/2;

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include <cstdio>

#include <algorithm>

using namespace std;

int a[100005];

int b[50010];

int main()

{

	int n;

	int num=0,sum=0;

	int ans=0;

	scanf("%d",&n);

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

	{

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

		if(i%2==1) b[++sum]=a[i];

	}

	sort(b+1,b+sum+1);

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

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

	{

		if(a[i]==b[num+1])

		{

			num++;

			if(i%2!=1)

				ans++;

			if(num==sum)

				break;

		}

	}

	printf("%d",ans);

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

struct node{

	int zhi;

	int xu;

}a[100001];

bool comp(node x,node y)

{

	return x.zhi<y.zhi;

}

int main()

{

	int n;

	cin>>n;

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

	{

		cin>>a[i].zhi;

		a[i].xu=i;

	}

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

	int sum=0;

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

	{

		

		if(i%2!=a[i].xu%2)sum++;

	}

	cout<<sum/2;

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<iostream>

#include<algorithm>

using namespace std;

struct Node{

	int value;

	int devid;

	int index;

} arr[100050];

bool comp1(const Node &A,const Node &B)

{

	return A.value<B.value;

}

bool comp2(const Node &A,const Node &B)

{

	return A.index < B.index;

}

int main()

{

	int N;

	scanf("%d",&N);

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

	{

		scanf("%d",&arr[i].value);

		arr[i].index=i;

	}

	sort(arr+1,arr+N+1,comp1);

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

	{

		arr[i].devid=i;

	}

	sort(arr+1,arr+N+1,comp2);

	int B[100050];

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

	{

		B[i]=arr[i].devid;

	}

	int cnt=0;

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

	{

		if(B[i]%2!=i%2)

		{

			cnt++;

		}

	}

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

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",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.181776250991594x):
#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int n,sum=0;

struct Sort{

	int num;

	int index;

	int sindex;

}a[100010];

bool cmp(Sort c,Sort d)

{

	return c.num<d.num;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {cin>>a[i].num;a[i].index=i;}

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

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

	{

		a[i].sindex=i;

	}

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

	{

		if(abs(a[i].sindex-a[i].index)%2==1) sum++;

	}

	sum/=2;

	printf("%d",sum);

	return 0;

}

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

#include<algorithm>

using namespace std;

const int maxn = 100000;

int num[maxn + 10];

int ji[maxn + 10];

int ou[maxn + 10];

int n;

int main()

{

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

	//freopen("f.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		if(i & 1)

		{

			ji[(i + 1) / 2] = num[i];

		}

		else

		{

			ou[i / 2] = num[i];

		}

	}

	sort(ji + 1,ji + 1 + (n + 1) / 2);

	sort(ou + 1,ou + 1 + n / 2);

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

	int ans = 0;

	if(n & 1)

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < (n + 1) / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < (n + 1) / 2)

				++p;

		}

	}

	else

	{

		int p = 1;

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

		{

			while(num[i] > ji[p] && p < n  / 2)

				++p;

			if(num[i] != ji[p])

				++ans;

			while(ji[p] < num[i] && p < n  / 2)

				++p;

		}

	}

	printf("%d",ans);

	return 0;

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

using namespace std;



bool even(int a, int b) {

    return (a%2 == 0) && (b%2 == 0);

}



bool odd(int a, int b) {

    return (a%2 != 0) && (b%2 != 0);

}



int main() {



    int n, k, cont = 0;

    cin >> n;



    vector<int> arr(n);

    map<int, int> idx;



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

        cin >> k;

        idx[k] = i;

        arr[i] = k;

    }



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

    /*for(int i=0; i<n; i++)cout << arr[i] << ' ';

    cout << endl;*/



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



        if(even(i, idx[arr[i]]) || odd(i, idx[arr[i]])) {

            //cont++;

            //cout << "here\n";

        } else {

            cont++;

        }





    }



    cout << (int)cont/2 << '\n';

    return 0;

}




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

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

int  a,b,c,d,i,j,k,x,y,z,ans,gay;

int f[100005],h[10010][1005][2],g[10010];

int main(){

	gay=0;

	ans=0;

	scanf("%d",&a);

	for (i=1;i<=a;i++) 	{

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

		c=f[i]%10007;

		g[c]++;

		h[c][g[c]][0]=f[i];

		h[c][g[c]][1]=i;

	}

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

	for (i=1;i<=a;i++){

		c=f[i]%10007;

		//printf("D%d\n",g[c]);

		for (j=1;j<=g[c];j++){

			if (h[c][j][0]==f[i]){

				//printf("E%d %d\n",h[c][j][0],h[c][j][1]);

				if (abs((h[c][j][1]-i)%2)==1) ans++;

				break;

			}

		}

	}

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

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



#define PB          push_back

#define PF          push_front

#define MP          make_pair

#define FI          first

#define SE          second

#define SIZE( A )   int( ( A ).size( ) )

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

#define ALLR( A )   ( A ).rbegin( ), ( A ).rend( )



using namespace std;



typedef long long           ll;

typedef unsigned long long  ull;

typedef long double         lf;

typedef pair< int, int >    pii;

typedef pair< ll, ll >      pll;

typedef vector< bool >      vb;

typedef vector< lf >        vd;

typedef vector< ll >        vll;

typedef vector< int >       vi;

typedef vector< pii >       vpii;



const int MAXN = int( 2e5 );

const int MOD  = int( 360 );

const int oo   = INT_MAX;



int n;

int arr[ MAXN ], cp[ MAXN ];

int tp[ MAXN ];



int main( ) {



  #ifdef LOCAL

    freopen( "input", "r", stdin );

    //freopen( "output", "w", stdout );

  #else

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

    //freopen( "attack.out", "w", stdout );

    ios_base::sync_with_stdio( 0 );

    cin.tie( 0 );

  #endif



  while( cin >> n ) {

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

      cin >> arr[ i ];

    }

    memcpy( cp, arr, sizeof( int )*n );

    sort( cp, cp+n );

    int ans = 0;

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

      int pos = lower_bound( cp, cp+n, arr[ i ] )-cp;

      if( pos%2 != i%2 ) {

        ++ans;

      }

    }

    cout << ans/2 << '\n';

  }



  return 0;

}


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

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

int  a,b,c,d,i,j,k,x,y,z,ans,gay;

int f[100005],h[10010][1005][2],g[10010];

int main(){

	gay=0;

	ans=0;

	scanf("%d",&a);

	for (i=1;i<=a;i++) 	{

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

		c=f[i]%10007;

		g[c]++;

		h[c][g[c]][0]=f[i];

		h[c][g[c]][1]=i;

	}

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

	for (i=1;i<=a;i++){

		c=f[i]%10007;

		//printf("D%d\n",g[c]);

		for (j=1;j<=g[c];j++){

			if (h[c][j][0]==f[i]){

				//printf("E%d %d\n",h[c][j][0],h[c][j][1]);

				if (abs((h[c][j][1]-i)%2)==1) ans++;

				break;

			}

		}

	}

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

}