#include<vector>
#include<iostream>

using namespace std;

long long ribaltamenti = 0;

vector<int> merge_sort(vector<int>& vet, int l, int r) {

  if(l==r) {
    return {vet[l]};
  }
  
  int mid = (l+r)/2;
  vector<int> a = merge_sort(vet, l, mid);
  vector<int> b = merge_sort(vet, mid+1, r);

  vector<int> ans;
  int L=0, R=0;
  while(L<a.size() && R<b.size()) {
    if(a[L]<=b[R]) {
      ans.push_back(a[L]);
      L++;
    } else {
      ans.push_back(b[R]);
      ribaltamenti+=a.size()-L;
      R++;
    }
  }
  while(L<a.size()) {
    ans.push_back(a[L]);
    L++;
  }
  while(R<b.size()) {
    ans.push_back(b[R]);
    R++;
  }

  return ans;
  
}


long long paletta_sort(int N, int V[]) {

    vector<int> odd;
    vector<int> even;
    for(int i=0; i<N; i++) {
      if(i%2==0)
        even.push_back(V[i]);
      else
        odd.push_back(V[i]);
    }

    
    even = merge_sort(even, 0, even.size()-1);
    odd = merge_sort(odd, 0, odd.size()-1);

    V[0] = even[0];
    for(int i=0; i<N; i+=2) {
      V[i] = even[i/2];
      V[i+1] = odd[i/2];
      if((V[i-1]>V[i] && i-1>=0) || V[i]>V[i+1]) {
        return -1;
      }
    }
    
    return ribaltamenti;
}