不久前,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次循环移位。