#include <bits/stdc++.h>
#include "grader.cpp"

using namespace std;

typedef int Item;

int scambi=0;

void merge(Item a[], int left, int center, int right) {
	Item* aux = new int[right + 1];
	int i,j;
	for (i = center+1; i > left; i--) 
		aux[i-1] = a[i-1];
	for (j = right; j > center; j--) 
		aux[j] = a[j];
	j++;	
	for (int k = left; k <= right; k++)
		if (i>center || (j<=right && aux[j] < aux[i])) {
			scambi = scambi + j - k;
			a[k] = aux[j++];
		}
		else
			a[k] = aux[i++];
        delete [] aux;   
}

void mergesort(Item a[], int left, int right) {
	if (left<right) {
		int center = (left+right)/2;
		mergesort(a, left, center);
		mergesort(a, center+1, right);
		merge(a, left, center, right);
	}
}

long long paletta_sort(int N, int V[]) {
	for (int i=0; i<N; i++)
		if (V[i]%2!=i%2){
			return -1;
		}
	int Np = N/2;
	int Nd = N/2;
	if (N%2!=0)
		Np++;	
	int* dis = new int[Nd];
	int* pari = new int[Np];
	for (int i=0; i<N; i++){
		if (i%2==0){
			pari[i/2] = V[i];

		}
		else{
			dis[i/2] = V[i];
		}
	}		
	mergesort(pari, 0, Np-1);
	mergesort(dis, 0, Nd-1);	
    return scambi;
}