← 返回题目列表

Codeforces · 819/B

B. B 先生和 PR 班次

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

不久前,B先生检测到了来自太空的奇怪信号,他开始对此进行研究。

经过一些变换,信号结果是长度为 n 的排列 p 或其循环移位。为了进一步调查,B先生需要一些依据,所以他决定选择这种排列的循环移位,这样偏差可能最小。

让我们将排列 p 的偏差定义为 $$\sum_{i=1}^{n}|p[i]-i|$$。

找到具有最小可能偏差的排列 p 的循环移位。如果有多个解决方案,请打印其中任何一个。

让我们将排列 p 的循环移位的 id k (0 ≤ k < n) 表示为达到该移位所需的右移次数,例如:

- k = 0: 移位 p1, p2, ... pn,
- k = 1: 移位 pn, p1, ... pn - 1,
- ...,
- k = n - 1:移位 p2, p3, ... pn, p1。

输入

第一行包含单个整数 n (2 ≤ n ≤ 106) — 排列的长度。

第二行包含 n 个空格分隔的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) - 排列的元素。保证所有元素都是不同的。

输出

打印两个整数:排列 p 的循环移位的最小偏差和该移位的 id。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
1 2 3

输出 #1

0 0

输入 #2

3
2 3 1

输出 #2

0 1

输入 #3

3
3 2 1

输出 #3

2 1

注意

在第一个样本测试中,给定的排列 p 是恒等排列,这就是为什么它的偏差等于 0,移位 id 也等于 0。

第二个样本测试中p的偏差等于4,第1次循环移位(1,2,3)的偏差等于0,第2次循环移位(3,1,2)的偏差等于4,最优的是第1次循环移位。

在第三个样本测试中,p的偏差等于4,第1次循环移位(1,3,2)的偏差等于2,第2次循环移位(2,1,3)的偏差也等于2,因此最优的是第1次循环移位和第2次循环移位。