Y is alone too and has a permutation \(p_1, p_2, ..., p_n\) of numbers from \(1\) to \(n\).
Y thinks that a permutation \(p_1, p_2, ..., p_n\) beautifulness is defined as value of \(\sum |p_i - i|, 1 \leq i \leq n\).
Y can swap two elements of the permutation at most once, what is the maximum beautifulness that Y can get?
Input
First line contains only \(n\).
Second line contains the permutation \(p_1, p_2, ..., p_n\) separated by space.
\(1 \leq n \leq 10^5\)
\(1 \leq p_i \leq n\), all \(p_i\) are distinct.
Output
The only line of output contains an integer, maximum beautifulness that Y can get.
5 1 4 2 3 5
12
Y can swap \(1\)th and \(5\)th element and the permutation becomes \(5, 4, 2, 3, 1\) with beautifulness \(|5 - 1| + |4 - 2| + |2 - 3| + |3 - 4| + |5 - 1| = 12\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor