Careful Deletion

You are given a permutation $P$ of length $N$ and two arrays $L$ and $R$. The permutation contains each integer from $1$ to $N$ exactly once.

Initially, the sequence contains $P_1,P_2,\cdots,P_N$ in this order. You want to delete every element.

In one operation, choose either the minimum or the maximum value currently present in the sequence. You may delete the chosen value only if it is at the front or the back of the sequence.

• If the chosen value $x$ is at the front, you may delete it at a cost of $L_x$.
• If the chosen value $x$ is at the back, you may delete it at a cost of $R_x$.

When only one element remains, it is both the front and the back. You may choose either method to delete it. The relative order of the remaining elements does not change.

Find the minimum total cost to delete every element. If this is impossible, print -1.

The input is given from standard input in the following format:

$N$ $P_1\ P_2\ \cdots\ P_N$

Print the minimum total cost to delete all elements. If this is impossible, print -1.

• $1 \leq N \leq 200\,000$.
• $1 \leq P_i \leq N$ ().