Problem:


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


Sample input:
5
1 2 3 5 4


Sample output:
7

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class MinCostFlow:
    """ 最小費用流(ダイクストラ版)：O(F*E*logV) """

    INF = 10 ** 18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        from heapq import heappush, heappop

        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0] * N
        prv_v = [0] * N
        prv_e = [0] * N

        while f:
            dist = [INF] * N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return INF

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

N = INT()
A = LIST()

mcf = MinCostFlow(N*2+2)
s = N * 2
t = N * 2 + 1
for i, a in enumerate(A):
    mcf.add_edge(s, i, 1, 0)
    mcf.add_edge(N+i, t, 1, 0)
    for j in range(N):
        # 完全順列なので、A[i] == i のペアには辺を張れない
        if a == j+1:
            continue
        cost = a * abs(i - j)
        mcf.add_edge(i, N+j, 1, cost)

res = mcf.flow(s, t, N)
print(res)