Swapping numbers
Problem
You are given a permutation \(p_1, p_2, ..., p_n\) of numbers from \(1\) to \(n\).
A permutation \(p_1, p_2, ..., p_n\), beauty, is defined as the minimum number of adjacent swaps required to sort the permutation.
If it is allowed to swap two elements of the permutation (not necessarily adjacent) at most once, then what is the minimum beauty that you can get?
Input format
- The first line contains \(n\).
- The second line contains the space-separated permutation \(p_1, p_2, ..., p_n\).
Output format
Print an integer denoting the minimum ugliness that we can get.
Constraints
\(1 \leq n \leq 7000\)
\(1 \leq p_i \leq n\), all \(p_i\) are distinct
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
After swapping \(p_2\) and \(p_4\), the permutation becomes: \(1, 3, 2, 4, 5\).
And it can be sorted by just swapping \(p_2\) and \(p_3\). so its ugliness is \(1\).
