4155: Mister B and PR Shifts
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：2
通过：2
题目描述
B. Mister B and PR Shifts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Some time ago Mister B detected a strange signal from the space, which he started to study.
After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that's why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.
Let's define the deviation of a permutation p as
.
Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.
Let's denote id k (0≤k<n) of a cyclic shift of permutation p as the number of right shifts needed to reach this shift, for example:
After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that's why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.
Let's define the deviation of a permutation p as
.Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.
Let's denote id k (0≤k<n) of a cyclic shift of permutation p as the number of right shifts needed to reach this shift, for example:
- k=0: shift p1,p2,... pn,
- k=1: shift pn,p1,... pn-1,
- ...,
- k=n-1: shift p2,p3,... pn,p1.
Input
First line contains single integer n (2≤n≤106) − the length of the permutation.The second line contains n space-separated integers p1,p2,...,pn (1≤pi≤n)− the elements of the permutation. It is guaranteed that all elements are distinct.
Output
Print two integers: the minimum deviation of cyclic shifts of permutation p and the id of such shift. If there are multiple solutions, print any of them.
Examples
Input
3 1 2 3
Output
0 0
Input
3 2 3 1
Output
0 1
Input
3 3 2 1
Output
2 1
Note
In the first sample test the given permutation p is the identity permutation, that's why its deviation equals to 0, the shift id equals to 0 as well.In the second sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1,2,3) equals to 0, the deviation of the 2-nd cyclic shift (3,1,2) equals to 4, the optimal is the 1-st cyclic shift.
In the third sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1,3,2) equals to 2, the deviation of the 2-nd cyclic shift (2,1,3) also equals to 2, so the optimal are both 1-st and 2-nd cyclic shifts.
前段时间，B先生从太空中探测到一个奇怪的信号，他开始研究这个信号。
经过一些变换后，信号变成了长度为n的置换p或其循环移位。为了进一步的研究，B先生需要一些基础，这就是为什么他决定选择这种排列的循环移位，这种移位具有最小的可能偏差。
让我们将置换p的偏差定义为。
找到具有最小可能偏差的置换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）−置换的元素。保证所有元素都是不同的。
第二行包含n个空格分隔的整数p1，p2，。。。，pn（1≤pi≤n）−置换的元素。保证所有元素都是不同的。
输出格式
打印两个整数：置换p的循环移位的最小偏差和该移位的id。如果有多个解决方案，请打印其中任何一个。
输入样例 复制
3
1 2 3输出样例 复制
0 0数据范围与提示
在第一个样本测试中，给定的排列p是单位排列，这就是为什么它的偏差等于0，移位id也等于0。
在第二个样本测试中，p的偏差等于4，第1个循环移位的偏差（1，2，3）等于0，第2个循环移位（3，1，2）的偏差等于2，最佳的是第1个周期移位。
在第三个样本测试中，p的偏差等于4，第1个循环移位（1,3,2）的偏差等于2，第2个循环移位的偏差（2,1,3）也等于2，因此最佳的是第1个和第2个周期移位。
在第二个样本测试中，p的偏差等于4，第1个循环移位的偏差（1，2，3）等于0，第2个循环移位（3，1，2）的偏差等于2，最佳的是第1个周期移位。
在第三个样本测试中，p的偏差等于4，第1个循环移位（1,3,2）的偏差等于2，第2个循环移位的偏差（2,1,3）也等于2，因此最佳的是第1个和第2个周期移位。