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