You are given a permutation of integers from 1 to n.
You have to remove exactly two elements from this permutation so that the number of inversions is minimum
The number of inversions is equal to the number of pairs (i, j) such that i < j and a[i] > a[j]
Output the minimum inversion count after removing exactly two elements from this permutation
Note : The order of the remaining elements is preserved. For example : If the original permutation is 7 5 1 3 4 2 6 , after removing 1 and 2 , the new sequence is 7 5 3 4 6.
Input format
The first line contains a single integer n (3 ≤ n ≤ 1000000) — the length of the permutation.
The second line contains n distinct integers from 1 to n — elements of the permutation.
Output format
Print the minimum inversion count after exactly removing two elements from this permutation
Constraints
3≤n≤106
You can obtain the minimum inversion count by removing the elements 4 and 3.
The new sequence would be 1 2 5. The number of inversions in this sequence is 0
Therefore print 0 as the answer.
