Prefix Reverse

問題文

正整数 $N$ と長さ $N$ の順列 $P$ と正整数列 $A$ が与えられる。はじめ、列 $Q$ を $Q = P$ とする。

$k = 1, 2, \cdots, N$ の順に、以下の操作を行う。

• $Q_i = k$ となるような $i$ を求める。
• $Q_1, Q_i$ の両方が $Q_1, Q_2, \dots, Q_i$ の最小値または最大値であるならば、 $Q_1, Q_2, \dots, Q_i$ を $Q_i, Q_{i-1}, \dots, Q_1$ に同時に置き換えてスコア $A_i$ を得るか、何もしないかを選ぶ。そうでない場合は何もしない。

すべての操作の後に $Q = P$ となるように操作を行ったとき、得たスコアの総和としてあり得る最大値を求めよ。

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le P \le N$ $(1 \le i \le N)$
• $P_i \neq P_j$ $(i \neq j)$
• $1 \le A_i \le 10^9$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル 1

入力

3
3 1 2
1 4 100

出力

8

次のように操作すると、最後に $Q = P$ となり、得たスコアの総和は $8$ となる。

• $k = 1$ のとき、 $i = 2$ である。 $Q_1 = 3, Q_2 = 1$ はそれぞれ $Q_1, Q_2$ の最大値、最小値なので、反転して $Q = (1, 3, 2)$ とする。スコア $A_2 = 4$ を得る。
• $k = 2$ のとき、 $i = 3$ である。 $Q_1, Q_2, Q_3$ の最大値 $3$ は $Q_1 = 1, Q_3 = 2$ のどちらでもないので、何もしない。
• $k = 3$ のとき、 $i = 2$ である。 $Q_1 = 1, Q_2 = 3$ はそれぞれ $Q_1, Q_2$ の最小値、最大値なので、反転して $Q = (3, 1, 2)$ とする。スコア $A_2 = 4$ を得る。

サンプル 2

入力

4
2 1 4 3
7 3 9 9

出力

7

$k = 1, 2$ のときに $Q_1, Q_2$ を反転させると、得たスコアの総和は $6$ となる。

一方、 $k = 1$ のときに何もしなければ、 $k = 2$ のときに $i = 1$ となる。このとき $Q_1$ だけを反転させることができ、 $Q$ は変化せずにスコア $A_1 = 7$ を得られる。

サンプル 3

入力

8
6 4 5 2 3 1 8 7
1000000000 2 3 999999999 5 314159265 1000000000 1000000000

出力

1999999998