#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// Fenwick Tree (BIT) for counting inversions efficiently
// Handles point updates and prefix sum queries
struct FenwickTree {
int size;
vector<int> tree;
FenwickTree(int n) : size(n), tree(n + 1, 0) {}
void add(int index, int value) {
while (index <= size) {
tree[index] += value;
index += index & (-index);
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & (-index);
}
return sum;
}
};
void solve() {
int N;
if (!(cin >> N)) return;
// We need to group tasks by their deadline.
// tasks_by_deadline[t] stores all tasks with deadline exactly t.
vector<vector<int>> tasks_by_deadline(N + 1);
for (int i = 1; i <= N; i++) {
int d;
cin >> d;
tasks_by_deadline[d].push_back(i);
}
// Max-heap to store available tasks (prioritizing largest original index)
priority_queue<int> pq;
// This will store our final constructed schedule
// result_schedule[i] = the task done at time i+1 (0-indexed logic)
vector<int> result_schedule(N);
// Iterate backwards from time t = N down to 1
for (int t = N; t >= 1; t--) {
// Add all tasks that have a deadline exactly at t to the pool
for (int task_id : tasks_by_deadline[t]) {
pq.push(task_id);
}
if (pq.empty()) {
// No task available that can be done at time t or later
cout << "-1" << endl;
return;
}
// Greedy choice: Pick the task with the LARGEST index
result_schedule[t - 1] = pq.top();
pq.pop();
}
// Step 2: Count inversions in result_schedule using Fenwick Tree
long long inversions = 0;
FenwickTree bit(N);
// Standard inversion counting:
// Iterate through the array, for each element x:
// Inversions += (elements seen so far that are greater than x)
// This equals: (total elements seen) - (elements seen <= x)
for (int i = 0; i < N; i++) {
int current_val = result_schedule[i];
// Count how many numbers already processed are larger than current_val
int count_smaller = bit.query(current_val);
int count_total_seen = i; // we have processed i elements so far
inversions += (count_total_seen - count_smaller);
// Add current value to BIT
bit.add(current_val, 1);
}
cout << inversions << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
