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

long long paletta_sort(int N, int V[]) {
    vector<pair<int, int>> movements(N);
    for (int i{ }; i < N; ++i) movements[i] = { V[i], i };
    sort(movements.begin(), movements.end());

    long long tot{ }; // For each num, the num of smaller nums on the right (only odds for odds and only evens for evens)
    set<int> founds_odd; // Contains in order all the ones that have already been found
    set<int> founds_even;
    for (int i{ }; i < N; ++i) {
        int diff{ movements[i].first - movements[i].second };
        if (abs(diff) % 2 != 0) return -1; // For when it's unsortable

        auto& founds = (V[i] % 2 == 1 ? founds_odd : founds_even);
        founds.insert(V[i]);
        int smallers{ };
        auto upper_bound{ founds.lower_bound(V[i]) };
        //upper_bound++;
        for (auto j{ founds.begin() }; j != upper_bound; ++j) smallers++;
        cerr << smallers << "\n";
        tot += V[i] / 2 - smallers;
    }
    return tot;
}