304296: CF819B. Mister B and PR Shifts

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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&lt;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.

Input

题意翻译

- 定义一个全排列$p_i$的偏移值为$\sum_{i=1}^n|p_i-i|$ - 给你一个全排列,你可以从后面拿$k\in[0,n-1]$个数放在前面,使得该全排列的偏移值最小,输出这个偏移值和k,如果有多个k任意输出一个 - $n\leq 10^6$

加入题单

上一题 下一题 算法标签: