CF362C Insertion Sort
Background
Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array $ a $ of size $ n $ in the non-decreasing order.
```cpp
for (int i = 1; i < n; i = i + 1)
{
int j = i;
while (j > 0 && a[j] < a[j - 1])
{
swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]
j = j - 1;
}
}
```
Petya uses this algorithm only for sorting of arrays that are permutations of numbers from $ 0 $ to $ n-1 $ . He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.
It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.
Description
Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array $ a $ of size $ n $ in the non-decreasing order.
`for (int i = 1; i < n; i = i + 1)
{
int j = i;
while (j > 0 && a[j] < a[j - 1])
{
swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]
j = j - 1;
}
}
`Petya uses this algorithm only for sorting of arrays that are permutations of numbers from $ 0 $ to $ n-1 $ . He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement. It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.
{
int j = i;
while (j > 0 && a[j] < a[j - 1])
{
swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]
j = j - 1;
}
}
`Petya uses this algorithm only for sorting of arrays that are permutations of numbers from $ 0 $ to $ n-1 $ . He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement. It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.
Input Format
N/A
Output Format
N/A
Explanation/Hint
In the first sample the appropriate pairs are $ (0,3) $ and $ (0,4) $ .
In the second sample the appropriate pairs are $ (0,4) $ , $ (1,4) $ , $ (2,4) $ and $ (3,4) $ .