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

Petya 是一位初学编程的同学。他已经掌握了 C++ 语言的基础知识，并开始学习算法。他遇到的第一个算法是插入排序。Petya 已经写好了实现该算法的代码，并能将给定的长度为 $n$ 的以零下标开始的整数数组 $a$ 按非递减顺序排序。 ```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]); // 交换数组 a[j] 和 a[j - 1] j = j - 1; } } ``` Petya 仅用此算法来排序由 $0$ 到 $n-1$ 的数字组成的排列。他已经选定了想要排序的排列，但在此之前，他决定先交换其中的两个元素。 Petya 希望能选出一对元素，使得经过这次交换后，运行排序算法时调用 swap 的次数最少。 请你帮助 Petya，计算有多少符合条件的交换对，使 swap 函数被调用的次数达到最小；并输出最小的 swap 调用次数以及符合条件的交换对的数量。 保证一定存在一种交换方法能减少 swap 调用次数。

第一行输入一个整数 $n$（$2 \leq n \leq 5000$），表示排列的长度。 第二行输入 $n$ 个不同的整数，范围从 $0$ 到 $n-1$，表示一个排列。

输出两个整数：交换后调用 swap 函数的最小次数，以及能达到该次数的交换对 $(i,j)$ 的数量。

在第一个样例中，符合条件的对有 $(0,3)$ 和 $(0,4)$。 在第二个样例中，符合条件的对有 $(0,4)$、$(1,4)$、$(2,4)$ 和 $(3,4)$。 由 ChatGPT 5 翻译并由人工修缮。