stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

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 ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

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



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

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;

const int MOD = 1000 * 1000 * 1000 + 7;



const int MAX = 111*1000;



PII A[MAX];



int main()

{

    int n;

    scanf("%d", &n);

    FOR(i, 0, n)

    {

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

        A[i].second = i;

    }

    sort(A, A + n);

    int ans = 0;

    FOR(i, 0, n)

    {

        if (!(i & 1) && (A[i].second & 1))

            ans++;

    }

    cout << ans << endl;

    

}


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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <bits/stdc++.h>

using namespace std;



class par

{

 public:

 int value;

 int pos;

};

bool comp(par a, par b)

{

if(a.value<b.value)return true;

return false;

};

int main()

{

    int n;

    cin>>n;

    vector<par>v (n);

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

        {

            int temp;

            cin>>temp;

            v[i].pos=i;

            v[i].value=temp;

        }

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

     int times=0;



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

     {

      {

          if(i%2!=v[i].pos%2)

            times++;

      }



     }

     cout<<times<<endl;

     

    return 0;

}




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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <bits/stdc++.h>

#define endl '\n'

#define MAXN 1000010

#define vi vector<int>

#define pii pair<int, int>

#define vii vector<pii>

using namespace std;



int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int n; cin >> n;

    vi num;

    vii ordered;

    int index = 0;

    int n1 = n;

    while (n1--){

        int x; cin >> x;

        num.push_back(x);

        ordered.emplace_back(x, index);

        index++;

    }

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

    int count = 0;

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

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

    }

    cout << (count >> 1) << endl;

    return 0;

}

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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <ext/algorithm>

#include <ext/numeric>

#define endl '\n'

using namespace std;

using namespace __gnu_cxx;



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0);



/**************************************************************/



	int N;

	cin >> N;

	pair<int,int> array[N];



	int count;

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

	{

		cin >> count;

		array[i] = {count,i};

	}



	sort(array, array+N);

	count = 0;

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

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

			count++;



	cout << (count >> 1) << endl;

}

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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

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



	vector<int> B = A;

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

	int odd = 0;

	for (int i = 0; i < A.size(); ++i) {

	  int j = lower_bound(B.begin(), B.end(), A[i]) - B.begin();

	  if ((i - j) % 2)

		++odd;

	}

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



  return 0;

}


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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

using namespace std;

const int maxn=100000;

struct _node{

	int A;

	int p;

	static bool cmp(_node &a,_node &b){

		return a.A<b.A;

	}

};

_node l[maxn+1];

int n;

int main(){

	scanf("%d",&n);

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

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

		l[i].p=i;

	}

	sort(l+1,l+1+n,_node::cmp);

	int cnt=0;

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

		cnt+=abs(l[i].p-i)%2;

	}

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

	return 0;

}


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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <iostream>

#include <vector>

#include <set>

using namespace std;



int n, tmp, ans;

vector<int> a;

set<int> s;



int main() {

	cin >> n;

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

		cin >> tmp;

		a.push_back(tmp);

		if (i % 2 == 0)

			s.insert(tmp);

	}

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

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

		if (s.find(a[i]) == s.end())

			ans++;

	cout << ans;

}

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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <algorithm>



using namespace std;

const int N = 1e6 + 10;

typedef pair <int, int> pii;



int n;

pii a[N];



int main() {

	cin >> n;

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

		cin >> a[i].first;

		a[i].second = i;

	}



	int ans = 0;

	sort (a, a + n);

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

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

			ans ++;



	cout << ans << endl;

}

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

#include<queue>

#include<algorithm>

#define MAXN 300006

using namespace std;

int n;

struct node

{

	int x,id;

}a[MAXN];

int ans;

bool cmp(node a,node b)

{

	return a.x<b.x;

}

int main()

{

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

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

	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++)

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

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

}

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

#include <algorithm>

#include <map>

using namespace std;

#define debug(x) std::cerr << #x << " = " << (x) << std::endl

typedef long long LL;

const int MAXN = 1e5+17;

int a[MAXN],b[MAXN];

map<int,int > mp;

int main(int argc ,char const *argv[])

{

    #ifdef noob

    freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);

    #endif      

    int n,ans=0;

    cin>>n;

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

    {

        cin>>a[i];

        b[i]=a[i];

    }

    sort(b, b+n);

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

    {

        mp[b[i]] = i+1;

    }

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

    {

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

    }

    cout<<ans/2+(ans&1)<<endl;

    return 0;   

}


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

#include<algorithm>

using namespace std;



const int N=100000;

struct node

{

	int num,id;

}a[N+5];

inline bool operator < (node a,node b)

{

	return a.num<b.num;

}

int n;

int ran[N+5];



int main()

{

	scanf("%d",&n);

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

	{

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

		a[i].id=i;

	}

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

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

		ran[a[i].id]=i;

	

	int ans=0;

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

		ans += !(ran[i]&1);

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

	return 0;

}

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

}


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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

	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;

}

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

}

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

}

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

}

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

}


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

}

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

}

// 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 <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;

}


// 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;



#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;

}

// 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 <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;

}


// 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):
//============================================================================

// 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;

}


// 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 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;

}


// 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: