#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll ans = 0;

void mergesort(vector<int>& v, int l, int r){ //[l,r)
    if(r-l == 1) return;
    int m = (l+r)/2;
    mergesort(v, l, m);
    mergesort(v, m, r);
    int i = 0, j = 0;
    vector<int> fake(r-l);
    while(i+j<r-l){
        if(i >= m-l){
            fake[i+j] = v[r+j];
            j++;
            continue;
        }
        if(j >= r-m){
            fake[i+j] = v[l+i];
            i++;
            continue;
        }
        if(v[i+l]<=v[j+m]){//= non serve davvero
            fake[i+j] = v[i+l];
            i++;
        }
        else{
            ans+=(m-l-i);
            fake[i+j] = v[m+j];
            j++;
        }
    }
    for(int i1=l; i1<r; i1++){
        v[i1] = fake[i1-l];
    }
}

long long paletta_sort(int N, int V[]) {
    vector<int> even((N+1)/2);
    vector<int> odd(N/2);
    for(int i = 0; i<N; i++){
        if((i%2) != (V[i]%2))return -1;
        even[i/2] = V[i];
    }
    mergesort(even, 0, (N+1)/2);
    mergesort(odd, 0, N/2);
    return ans;
}