English · Original
Chinese · Translation
Formal · Original
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:
* _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.
## Input
First line contains single integer _n_ (2 ≤ _n_ ≤ 106) — 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.
## 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.
[samples]
## 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.
某段时间，Mister B 从太空中探测到一个奇怪的信号，并开始研究它。
经过一些变换后，该信号变为一个长度为 $n$ 的排列 $p$ 或其循环移位。为了进一步研究，Mister B 需要一个基准，因此他决定选择该排列的循环移位中偏差最小的一个。
定义排列 $p$ 的偏差为 $\sum_{i=1}^{n} |p_i - i|$。
请找出偏差最小的循环移位。如果有多个解，输出任意一个即可。
记循环移位的编号 $k$（$0 \leq k < n$）为达到该移位所需的右移次数，例如：
第一行包含一个整数 $n$（$2 \leq n \leq 10^6$）——排列的长度。
第二行包含 $n$ 个空格分隔的整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$）——排列的元素。保证所有元素互不相同。
请输出两个整数：排列 $p$ 的循环移位中的最小偏差，以及该移位的编号。如果有多个解，输出任意一个即可。
在第一个样例中，给定的排列 $p$ 是恒等排列，因此其偏差为 $0$，移位编号也为 $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$ 个循环移位都是最优的。
## Input
第一行包含一个整数 $n$（$2 \leq n \leq 10^6$）——排列的长度。第二行包含 $n$ 个空格分隔的整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$）——排列的元素。保证所有元素互不相同。
## Output
请输出两个整数：排列 $p$ 的循环移位中的最小偏差，以及该移位的编号。如果有多个解，输出任意一个即可。
[samples]
## Note
在第一个样例中，给定的排列 $p$ 是恒等排列，因此其偏差为 $0$，移位编号也为 $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$ 个循环移位都是最优的。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 10^6 $.
Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $.
For $ k \in \{0, 1, \dots, n-1\} $, define the $ k $-th cyclic shift of $ P $ as:
$$
P_k = (p_{k+1}, p_{k+2}, \dots, p_n, p_1, \dots, p_k)
$$
where indices are taken modulo $ n $, with 1-based indexing.
Define the deviation of a permutation $ Q = (q_1, q_2, \dots, q_n) $ as:
$$
\text{dev}(Q) = \sum_{i=1}^n |q_i - i|
$$
**Constraints**
1. $ 2 \leq n \leq 10^6 $
2. $ P $ is a permutation of $ \{1, 2, \dots, n\} $
**Objective**
Find $ k^* \in \{0, 1, \dots, n-1\} $ such that:
$$
\text{dev}(P_{k^*}) = \min_{k \in \{0, 1, \dots, n-1\}} \text{dev}(P_k)
$$
Output $ \text{dev}(P_{k^*}) $ and $ k^* $. If multiple $ k^* $ achieve the minimum, output any.
API Response (JSON)
{
"problem": {
"name": "B. Mister B and PR Shifts",
"description": {
"content": "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. ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF819B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Some time ago Mister B detected a strange signal from the space, which he started to study.\n\nAfter some transformation the signal turned out to be a permutation _p_ of length _n_ or its cyclic shift. ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "某段时间，Mister B 从太空中探测到一个奇怪的信号，并开始研究它。\n\n经过一些变换后，该信号变为一个长度为 $n$ 的排列 $p$ 或其循环移位。为了进一步研究，Mister B 需要一个基准，因此他决定选择该排列的循环移位中偏差最小的一个。\n\n定义排列 $p$ 的偏差为 $\\sum_{i=1}^{n} |p_i - i|$。\n\n请找出偏差最小的循环移位。如果有多个解，输出任意一个即可。\n\n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^6 $. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $. \n\nFor $ k \\in \\{0, 1, \\dots, n-1\\} $, define t...",
"is_translate": false,
"language": "Formal"
}
]
}