G - Derangement / 完全順列

Story

Dのひとは順列に関する研究をしている。あるときDのひとは、"完全順列 (Derangement)"という順列のクラスを見つけた。「完全な順列とかなんかかっこいい！！！しかもDからはじまる！！！」と廚二病をこじらせたDのひとは、与えられた順列をすべて完全順列に書き換えてしまおうと考えた。

Problem

長さnの順列p = (p_1 p_2 ... p_n)が与えられる。i番目の要素とj番目の要素を入れ替える操作には(p_i+p_j) \times |i-j|のコストを要する。このとき、上記の入れ替え操作のみを用いてpを完全順列にするために必要な最小のコストを求めよ。

ただし、順列qが完全順列であるとは、1 \leq i \leq nについて、q_i \neq iが成り立つことを言う。たとえば、(5 3 1 2 4)は完全順列であるが、(3 2 5 4 1)は4番目の数が4なので完全順列ではない。

Input

入力は以下の形式からなる。

n
p_1 p_2 ... p_n

1行目は順列の長さnを表す整数1つからなる。 2行目はn個の整数からなり、i番目の整数は順列pのi番目の要素を表す。それぞれは空白1文字で区切られている。

制約:

• 2 \leq n \leq 100
• 1 \leq p_i \leq n, i \neq j ⇔ p_i \neq p_j

Output

pを完全順列に並び替えるための最小コストを1行に出力せよ。行の最後では必ず改行を行うこと。

Sample Input 1

5
1 2 3 5 4

Sample Output 1

7

1と2を入れ替えた後、1と3を入れ替えると、(2 3 1 5 4)となり完全順列である。

Sample Input 2

5
5 3 1 2 4

Sample Output 2

0

始めから完全順列である。

Sample Input 3

10
1 3 4 5 6 2 7 8 9 10

Sample Output 3

38

---