CF362C Insertion Sort

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 翻译并由人工修缮。