stablegradients/pie-gem5-pairs huggingface dataset:
// 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.295787681610178x):
#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;

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

#define For(i,n) for(int i =0; i<n;i++)

#define ll long long

using namespace std;



int main(){

    #ifdef magUNbos

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

    freopen("out","w",stdout);

    #endif // magUNbos

    int n;

    cin>>n;

    ll a[n];

    map <ll, ll> m;

    For(i,n){

        cin>>a[i];

        m[a[i]]=i;

    }

    sort(a,a+n);

    ll ans = 0;

    For(i,n){

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

            ans++;

           // cerr<<i<<" : "<<m[a[i]]<<endl;

        }

    }

    cout<<ans/2<<endl;









}


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

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

#include <iostream>

#include <map>

using namespace std;



int main() {

	int n; cin >> n;

	int arr[n];

	map<int, int> index;

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

		cin >> arr[i];

		index[arr[i]] = i;

	}

	sort(arr, arr+n);



	int ans = 0;

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

		ans += (i%2 != index[arr[i]]%2);

	}

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

}


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

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

#include<iostream>

#include<algorithm>

using namespace std;

int n,o;

pair<int,bool> a[100005];

int main()

{

	scanf("%d",&n);

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

	{

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

		if (i%2==0) a[i].second=true;

	}

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

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

	{

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

		++o;

	}

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

}

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

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

using namespace std;

#define FOR(i, s, e) for(int i = (s); i < (e); i++)

#define FOE(i, s, e) for(int i = (s); i <= (e); i++)

#define FOD(i, s, e) for(int i = (s); i >= (e); i--)

#define ll long long



int A[100005], B[100005], n;



map<int, int> M;



int main ()

{

	scanf("%d", &n);

	FOR(i, 0, n) { scanf("%d", &A[i]); B[i] = A[i]; }

	

	sort(B, B + n);

	

	FOR(i, 0, n) M.insert(make_pair(A[i], i % 2));

	

	int ans = 0;

	FOR(i, 0, n)

	{

		if (i % 2 != M.find(B[i]) -> second) ans++;

	}

	

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

	return 0;

}

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

}
// Slower C++ solution:
#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;

    

}


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

}
// Slower C++ solution:
#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;

}




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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;

}

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

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

}
// Slower C++ solution:
#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;

}


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

}
// Slower C++ solution:
#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;

}


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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;   

}


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

}
// 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.839258418180064x):
#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define RG register

using namespace std;

const int N=1e5+10;

int n,a[N],b[N],ans;

inline int read(){

	char ch=getchar(); int x=0, f=1;

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

	while(ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

	return x*f;}

inline int abss(int x){return x>0 ? x : -x;}

int fnd(int x)

{

	int l=1, r=n;

	while(l<=r)

	{

		int mid=l+(r-l)/2;

		if(a[mid]==x) return mid;

		if(a[mid]<x) l=mid+1;

		else r=mid-1;

	}

}

int main()

{

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

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

	n=read();

	for(int i=1;i<=n;i++) a[i]=b[i]=read();

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

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

	{

		int pos=fnd(b[i]);

		ans+=(abss(pos-i)&1);

	}

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

	//fclose(stdin); fclose(stdout);

	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.8153703346115904x):
#include<bits/stdc++.h>

using namespace std;

#define rg register

#define ll long long 

inline ll read()

{

    ll x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9')

    {

        if(c=='-')

        {

            f=-1;

        }

        c=getchar();

    }

    while(c<='9'&&c>='0')

    {

        x=(x<<1)+(x<<3)+(c^48);

        c=getchar();

    }

    return x*f;

}

int n;

struct node

{

    ll num,id;

    ll tot;

}s[100503];

inline bool cmp(node a,node b)

{

    return a.num<b.num;

}

ll ji,ou;

int main()

{

    n=read();

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

        s[i].num=read(),s[i].id=i;

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

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

        if(s[i].id%2==0)

            if(i%2==0)

                continue;

            else

                ou++;

        else 

            if(i%2!=0)

                continue;

            else

                ji++;

    ll h=min(ou,ji);

    cout<<h+abs(ou-ji);

;;;;;;;;;;

}
// 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.8190742888074043x):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define mp make_pair

#define CHECK(x) if(!(x)) return false;

#define CHECKRET(x, y) if(!(x)) return (y);

#define SKIP(x) if((x)) continue;

typedef pair<int, int> pii;



const int MAXN = 100010;

pii sorted[MAXN];



int fucked[2];



int main() {

  int N;

  scanf("%d", &N);

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

    sorted[i].second = i;

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

  }

  sort(sorted, sorted + N);

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

    SKIP(sorted[i].second % 2 == i % 2);

    ++fucked[i % 2];

  }

  printf("%d\n", max(fucked[0], fucked[1]));

  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.7734555287405251x):
#include <bits/stdc++.h>



using namespace std;



typedef pair<int,int> pii;



#define F first

#define S second



int main()

{

	ios_base::sync_with_stdio(false); cin.tie(nullptr);



	int n;

	while(cin >> n)

	{

		vector<pii> v(n);

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

		{

			cin >> v[i].F;

			v[i].S = i;

		}

		int cnt = 0;

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

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

		{

			int diff = abs(i-v[i].S);

			if(diff&1)

				cnt++;

		}

		assert(cnt%2 == 0);

		cout << cnt/2 << endl;

	}



	return 0;

}