Minimum Adjacent Swaps to Meet Deadlines

You are given N tasks numbered from 1 to N. The i-th task has a deadline \(d_i\) and must be completed by time \(d_i\). Completing any task takes exactly 1 unit of time. Initially, the tasks are scheduled in the order \(1,2,3,\ldots,N\). However, this order may not allow you to complete every task before its deadline.

You are allowed to swap adjacent tasks. Each such swap counts as 1 move. Your goal is to determine the minimum number of adjacent swaps required to obtain an ordering in which every task is completed on time. In other words, if the new order is \(Q\), then for every position \(j\) (1-indexed) we must have:

[ d_{Q[j]} \ge j ]

If no valid ordering exists, output -1.

Note: If the original (identity) ordering already satisfies \(d_i \ge i\) for all \(i\), then no swaps are needed.

inputFormat

The first line contains a single integer N (the number of tasks).

The second line contains N space‐separated integers \(d_1,d_2,\ldots,d_N\), where \(d_i\) is the deadline of the \(i\)-th task.

outputFormat

Output a single integer that represents the minimum number of adjacent swaps required to obtain an ordering in which every task meets its deadline. If there is no valid ordering, output -1.

sample

3
2 3 3

0