Balloon Darts

A lonely coder named Byeongwoo was set up on a date by his friends, and the two went to an amusement park.

While chatting on a bench, Byeongwoo noticed a balloon dart game across the way. He wanted a high score to win a teddy bear, so he walked over to play. The park's game followed rules unlike any ordinary balloon dart game he knew.

1. The balloons are arranged in a single line, like a one-dimensional array.

2. There are as many darts as balloons. Byeongwoo is a dart master, so every dart he throws hits its balloon exactly and bursts it.

3. The score is the sum, over every segment, of (the sum of the balloon scores in the segment) times (the size of the segment). A segment is a contiguous subarray. More precisely, for an interval $[l, r]$ where all balloons in $[l, r]$ are still present, and balloon $l-1$ and balloon $r+1$ either do not exist or have been burst, the segment is the subarray $a_l, a_{l+1}, \cdots, a_r$ of the full array $a$. The score is given by the formula below.

$\sum\limits_{i=1}^{k} (seg_i \times size(seg_i))$

• $seg_i$ is the sum of the balloon scores in the $i$-th segment.
• $size(seg_i)$ is the size of the interval of the $i$-th segment.
• $k$ is the total number of segments.

4. The score starts at 0 and is recalculated each time a dart bursts a balloon. The final score is the highest score recorded. Before the first dart is thrown, no score has been calculated, so the score is 0.

The first line contains the number of balloons, an integer $N$ ($3 \le N \le 100\,000$).

The second line contains $N$ integers $B_1, B_2, \cdots, B_N$ ($-100\,000 \le B_i \le 100\,000$), the scores of the balloons.

The third line contains $N$ distinct integers $P_1, P_2, \cdots, P_N$ ($1 \le P_i \le N$), the order in which the balloons are burst.

Print the final score.