/*
Author : ayuxh
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
// Fenwick Tree (BIT) for Inversion Counting
struct FenwickTree {
int size;
vector<int> tree;
FenwickTree(int n) : size(n), tree(n + 1, 0) {}
void add(int idx, int delta) {
for (; idx <= size; idx += idx & -idx) tree[idx] += delta;
}
int query(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx) sum += tree[idx];
return sum;
}
};
void Solve() {
int n;
if (!(cin >> n)) return;
// deadlines[d] stores list of task IDs that have deadline d
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);
}
priority_queue<int> pq; // Max-heap: Stores task IDs available to be placed
vector<int> result_permutation(n + 1);
// Fill positions from N down to 1
for (int pos = n; pos >= 1; --pos) {
// Add tasks that become available at this deadline
// (i.e., tasks with deadline exactly 'pos' can certainly be placed at 'pos' or earlier)
// Wait, logic check: A task with deadline D can be placed at any pos <= D.
// So at pos=N, we can use tasks with deadline N.
// At pos=N-1, we can use tasks with deadline N-1 AND unused tasks from deadline N.
for (int task_id : tasks_by_deadline[pos]) {
pq.push(task_id);
}
if (pq.empty()) {
cout << "-1\n";
return;
}
// Greedy choice: Pick the largest available task ID
int task_to_place = pq.top();
pq.pop();
// We place this task at the current position 'pos'
result_permutation[pos] = task_to_place;
}
// Now calculate minimum swaps to transform 1..N to result_permutation.
// This is equivalent to counting inversions, or more directly:
// The cost is the sum of distances of moves.
// Actually, since we know the target positions, we can use a standard inversion count.
// The problem asks for swaps to transform (1..N) -> result_permutation.
// Let's re-verify sample 1:
// N=4, D=[4, 4, 3, 2]. Tasks: 1(d=4), 2(d=4), 3(d=3), 4(d=2).
// Pos 4: Pool has {1, 2}. Pick 2. Perm[4] = 2.
// Pos 3: Pool has {1} + {3}. Pick 3. Perm[3] = 3.
// Pos 2: Pool has {1} + {4}. Pick 4. Perm[2] = 4.
// Pos 1: Pool has {1}. Pick 1. Perm[1] = 1.
// Result Perm: [1, 4, 3, 2].
// Swaps 1,2,3,4 -> 1,4,3,2.
// Inversions in [1, 4, 3, 2]:
// (4, 3), (4, 2), (3, 2). Total 3. Correct.
// Inversion Count using BIT
// Iterate through the permutation, for each element x, how many elements > x appeared before it?
// OR: for each element x, how many elements < x appear AFTER it?
// Standard approach:
FenwickTree ft(n);
int inversions = 0;
// Note: The result_permutation is 1-indexed from the logic above.
for (int i = 1; i <= n; ++i) {
int val = result_permutation[i];
// Count elements greater than 'val' already processed (appearing to the left)
// Actually standard way: Count elements > val already seen.
// Query(n) - Query(val) gives count of numbers > val currently in tree.
inversions += (i - 1) - ft.query(val);
ft.add(val, 1);
}
cout << inversions << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Solve();
return 0;
}
