問題文

N 個の箱が並べられており、左から i 番目の箱には番号 i がつけられています。 また、 1 から N の番号がついた N 個の荷物があり、 荷物 i (1 \le i \le N) の重さは W_i で箱 A_i の中に入っています。

あなたの目標は、各箱にちょうど 1 つの荷物が入っている状態にすることです。 そのために、以下の操作を繰り返し行うことができます。

• 荷物を一つ選び、隣接する箱へ移動させる。 移動させる荷物の重さが w のとき、w のコストがかかる。

目標を達成するために必要な操作回数の最小値と、操作回数を最小としたうえでかかるコストの総和の最小値を求めてください。

制約

• 1\leq N \leq 10^4
• 1 \leq A_i \leq N (1\leq i\leq N)
• 1 \leq W_i \leq 10^9 (1\leq i\leq N)
• 入力はすべて整数

部分点

追加の制約 N \le 500 を満たすデータセットに正解した場合は 1 点が与えられる。

入力例1

3
2 2 2
1 2 3

出力例1

2 3

以下の 2 回の操作で、コストの総和 3 で目標を達成することができます。

• 荷物 1 を箱 2 から箱 1 に移動させる。コストは 1 かかる。
• 荷物 2 を箱 2 から箱 3 に移動させる。コストは 2 かかる。

1 回以下の操作で目標は達成できないので、最小の操作回数は 2 です。 また、コストの総和を 2 以下にすることはできないので、最小のコストは 3 となります。

入力例2

5
1 2 3 4 5
10 10 10 10 10

出力例2

0 0

初めから目標を達成している場合もあります。

入力例3

5
2 2 3 3 5
33 40 2 12 16

出力例3

2 35