← 返回题目列表

Codeforces · 362/C

C. 插入排序

中文机器翻译题面 查看原题

Petya 是一名初级程序员。他已经掌握了 C++ 语言的基础知识,并开始学习算法。他遇到的第一个算法是插入排序。 Petya 已经编写了实现该算法的代码,并以非递减顺序对给定的大小为 n 的整数零索引数组 a 进行排序。

Petya 仅使用此算法对从 0 到 n - 1 的数字排列数组进行排序。他已经选择了他想要排序的排列,但他首先决定交换其中的两个元素。 Petya 希望以这样的方式选择这些元素,即排序执行交换函数的次数最少。帮助 Petya 找出他可以进行交换并满足此要求的方法数。

确保始终可以交换输入排列的两个元素,从而减少交换函数调用的次数。

输入

第一行包含一个整数 n (2 ≤ n ≤ 5000) — 排列的长度。第二行包含 n 个从 0 到 n-1 的不同整数(包括 0 和 n - 1)——实际排列。

输出

打印两个整数:交换函数执行的最小次数以及将输入排列中索引 i 和 j 的元素交换导致执行次数最少的对 (i, j) 的数量。

示例

输入 #1

5
4 0 3 1 2

输出 #1

3 2

输入 #2

5
1 2 3 4 0

输出 #2

3 4

注意

在第一个示例中,适当的对是 (0, 3) 和 (0, 4)。

在第二个示例中,适当的对是 (0, 4)、(1, 4)、(2, 4) 和 (3, 4)。