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

long long mergetsort(int left, int right, int N, vector<int>& V){
    if (right - left ==0) return 0;
    int mid = (left + right + 1) / 2;

    long long Ans = mergetsort(left, mid-1, N, V);
    Ans += mergetsort(mid, right, N, V);

    int ptleft = left;
    int ptright = mid;
    vector<int> NewP;

    while (ptleft < mid && ptright <= right)
    {
        if (V[ptleft] <= V[ptright]){ 
            NewP.push_back(V[ptleft]);
            ptleft ++;
        }else{
            NewP.push_back(V[ptright]);
            ptright ++;
            Ans += mid - ptleft;
        }
        /* code */
    }

    for (; ptleft < mid; ptleft ++) NewP.push_back(V[ptleft]);
    for (; ptright <= right; ptright ++) NewP.push_back(V[ptright]);

    for (int i = left; i<= right; i++) V[i] = NewP[i-left];
    return Ans;
}

long long paletta_sort(int N, int V[]) {
    if (N % 2) while (1)
    {
        /* code */
    }
     
    vector<int> Pari;
    vector<int> Disp;
    for (int i=0; i<N; i++) {
        if (i % 2) Disp.push_back(V[i]);
        else Pari.push_back(V[i]);
    }

    long long risp = mergetsort(0, Pari.size() - 1, Pari.size(), Pari);
    risp += mergetsort(0, Disp.size() - 1, Disp.size(), Disp);

    if (Disp.size() != Pari.size()){
        N ++;
        Disp.push_back(INT_MAX);
    }
    for (int i=0; i<N/2; i++) if (Pari[i] > Disp[i]) return -1;
    
    return risp;
}
/*
int main(){
    vector<int> P = {3,5,1};
    cout<<mergetsort(0, 2, 3, P)<<endl;
    for (auto x:P) cout<<x<<" ";

    return 0;
}*/