CF362C.Insertion Sort

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.

佩佳是一名初学编程者。他已掌握了 C++ 语言的基础知识，开始学习算法。他遇到的第一个算法是插入排序。佩佳已经编写了实现该算法的代码，用于将给定的大小为 $n$ 的零索引整数数组 $a$ 按非递减顺序排序。

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]); // 交换元素 a[j] 和 a[j - 1]  
 j = j - 1;  
 }  
}  

佩佳仅将该算法用于排序那些由 $0$ 到 $n-1$ 的整数构成的排列（即每个数恰好出现一次）。他已选定一个待排序的排列，但决定先交换其中某两个元素。佩佳希望以某种方式选择这两个元素进行交换，使得排序过程中调用 swap 函数的总次数最小化。请你帮助佩佳求出：有多少种不同的交换方式（即选择哪两个位置进行交换），能够满足上述最小化要求。

题目保证：总存在一种方式，通过交换输入排列中的两个元素，使得排序过程中 swap 函数的调用次数减少。

The first line contains a single integer n (2 ≤ n ≤ 5000) — the length of the permutation. The second line contains n different integers from 0 to n - 1, inclusive — the actual permutation.

第一行包含一个整数 $n$（$2 \leq n \leq 5000$）—— 排列的长度。
第二行包含 $n$ 个互不相同的整数，取值范围为 $0$ 到 $n-1$（含端点）—— 实际的排列。

Print two integers: the minimum number of times the swap function is executed and the number of such pairs (i, j) that swapping the elements of the input permutation with indexes i and j leads to the minimum number of the executions.

输出两个整数：交换函数执行的最少次数，以及满足“交换输入排列中下标为 $i$ 和 $j$ 的元素后，能使交换函数执行次数达到最少”的下标对 $(i,\,j)$ 的个数。

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).

在第一个样例中，合适的数对为 $(0,\,3)$ 和 $(0,\,4)$。

在第二个样例中，合适的数对为 $(0,\,4)$、$(1,\,4)$、$(2,\,4)$ 和 $(3,\,4)$。