#D5587. Derangement
Derangement
Derangement
G --Derangement / Derangement
Story
Person D is doing research on permutations. At one point, D found a permutation class called "Derangement". "It's cool to have a perfect permutation !!! And it starts with D !!!", the person of D who had a crush on Chunibyo decided to rewrite all the permutations given to him.
Problem
Given a permutation of length n, p = (p_1 p_2 ... p_n). The operation of swapping the i-th element and the j-th element requires the cost of (p_i + p_j) \ times | i-j |. At this time, find the minimum cost required to make p into a perfect permutation using only the above swap operation.
However, the fact that the permutation q is a perfect permutation means that q_i \ neq i holds for 1 \ leq i \ leq n. For example, (5 3 1 2 4) is a perfect permutation, but (3 2 5 4 1) is not a perfect permutation because the fourth number is 4.
Input
The input consists of the following format.
n p_1 p_2 ... p_n
The first row consists of one integer representing the length n of the permutation. The second line consists of n integers, and the i-th integer represents the i-th element of the permutation p. Each is separated by a single blank character.
Constraints:
- 2 \ leq n \ leq 100
- 1 \ leq p_i \ leq n, i \ neq j ⇔ p_i \ neq p_j
Output
Print the minimum cost to sort p into a complete permutation on one line. Be sure to start a new line at the end of the line.
Sample Input 1
Five 1 2 3 5 4
Sample Output 1
7
After swapping 1 and 2, swapping 1 and 3 yields (2 3 1 5 4), which is a complete permutation.
Sample Input 2
Five 5 3 1 2 4
Sample Output 2
0
It is a perfect permutation from the beginning.
Sample Input 3
Ten 1 3 4 5 6 2 7 8 9 10
Sample Output 3
38
Example
Input
5 1 2 3 5 4
Output
7
inputFormat
Input
The input consists of the following format.
n p_1 p_2 ... p_n
The first row consists of one integer representing the length n of the permutation. The second line consists of n integers, and the i-th integer represents the i-th element of the permutation p. Each is separated by a single blank character.
Constraints:
- 2 \ leq n \ leq 100
- 1 \ leq p_i \ leq n, i \ neq j ⇔ p_i \ neq p_j
outputFormat
Output
Print the minimum cost to sort p into a complete permutation on one line. Be sure to start a new line at the end of the line.
Sample Input 1
Five 1 2 3 5 4
Sample Output 1
7
After swapping 1 and 2, swapping 1 and 3 yields (2 3 1 5 4), which is a complete permutation.
Sample Input 2
Five 5 3 1 2 4
Sample Output 2
0
It is a perfect permutation from the beginning.
Sample Input 3
Ten 1 3 4 5 6 2 7 8 9 10
Sample Output 3
38
Example
Input
5 1 2 3 5 4
Output
7
样例
5
1 2 3 5 47