Mister B and PR Shifts
题意翻译
- 定义一个全排列$p_i$的偏移值为$\sum_{i=1}^n|p_i-i|$
- 给你一个全排列,你可以从后面拿$k\in[0,n-1]$个数放在前面,使得该全排列的偏移值最小,输出这个偏移值和k,如果有多个k任意输出一个
- $n\leq 10^6$
题目描述
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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF819B/47275887a8ad3386063ea864423569d3d609b7f9.png).
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 $ p_{1},p_{2},...\ p_{n} $ ,
- $ k=1 $ : shift $ p_{n},p_{1},...\ p_{n-1} $ ,
- ...,
- $ k=n-1 $ : shift $ p_{2},p_{3},...\ p_{n},p_{1} $ .
输入输出格式
输入格式
First line contains single integer $ n $ ( $ 2<=n<=10^{6} $ ) — the length of the permutation.
The second line contains $ n $ space-separated integers $ p_{1},p_{2},...,p_{n} $ ( $ 1<=p_{i}<=n $ ) — the elements of the permutation. It is guaranteed that all elements are distinct.
输出格式
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.
输入输出样例
输入样例 #1
3
1 2 3
输出样例 #1
0 0
输入样例 #2
3
2 3 1
输出样例 #2
0 1
输入样例 #3
3
3 2 1
输出样例 #3
2 1
说明
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.