Insertion Sort

题意翻译

给出一个长度为$N$的无序序列，序列为$0$到$N-1$的排列，现在需要你用冒泡排序来将序列排成从小到大有序的序列 你可以执行一次交换两个元素$i,j(i\neq j,1\le i\leq n)$，使得执行冒泡排序时，交换相邻元素的次数最少 要你求出交换相邻元素的最少次数和满足交换相邻元素的次数最少的方案数

题目描述

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)<br></br>{<br></br> int j = i; <br></br> while (j > 0 && a[j] < a[j - 1])<br></br> {<br></br> swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]<br></br> j = j - 1;<br></br> }<br></br>}<br></br>`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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

5
4 0 3 1 2

输出样例 #1

3 2

输入样例 #2

5
1 2 3 4 0

输出样例 #2

3 4

说明

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

题意翻译

给出一个长度为$N$的无序序列，序列为$0$到$N-1$的排列，现在需要你用冒泡排序来将序列排成从小到大有序的序列 你可以执行一次交换两个元素$i,j(i\neq j,1\le i\leq n)$，使得执行冒泡排序时，交换相邻元素的次数最少 要你求出交换相邻元素的最少次数和满足交换相邻元素的次数最少的方案数