Permutation Separation
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 2200
Tags: data structures, divide and conquer

You are given a permutation $$$p_1, p_2, \dots , p_n$$$ (an array where each integer from $$$1$$$ to $$$n$$$ appears exactly once). The weight of the $$$i$$$-th element of this permutation is $$$a_i$$$.

At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements $$$p_1, p_2, \dots , p_k$$$, the second — $$$p_{k+1}, p_{k+2}, \dots , p_n$$$, where $$$1 \le k < n$$$.

After that, you may move elements between sets. The operation you are allowed to do is to choose some element of the first set and move it to the second set, or vice versa (move from the second set to the first). You have to pay $$$a_i$$$ dollars to move the element $$$p_i$$$.

Your goal is to make it so that each element of the first set is less than each element of the second set. Note that if one of the sets is empty, this condition is met.

For example, if $$$p = [3, 1, 2]$$$ and $$$a = [7, 1, 4]$$$, then the optimal strategy is: separate $$$p$$$ into two parts $$$[3, 1]$$$ and $$$[2]$$$ and then move the $$$2$$$-element into first set (it costs $$$4$$$). And if $$$p = [3, 5, 1, 6, 2, 4]$$$, $$$a = [9, 1, 9, 9, 1, 9]$$$, then the optimal strategy is: separate $$$p$$$ into two parts $$$[3, 5, 1]$$$ and $$$[6, 2, 4]$$$, and then move the $$$2$$$-element into first set (it costs $$$1$$$), and $$$5$$$-element into second set (it also costs $$$1$$$).

Calculate the minimum number of dollars you have to spend.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots , p_n$$$ ($$$1 \le p_i \le n$$$). It's guaranteed that this sequence contains each element from $$$1$$$ to $$$n$$$ exactly once.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output format:
Print one integer — the minimum number of dollars you have to spend.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
3 1 2
7 1 4

Example output:
4

Example input:
4
2 4 1 3
5 9 8 3

Example output:
3

Editorial:
"All elements in the left set smaller than all elements in the right set" means that there is such value $$$val$$$ that all elements from the first set less than $$$val$$$ and all elements from the second set are more or equal to $$$val$$$. So let's make a sweep line on $$$val$$$ from $$$1$$$ to $$$n + 1$$$ while trying to maintain all answers for each prefix $$$pos$$$.
Let's maintain for each $$$pos$$$ the total cost $$$t[pos]$$$ to make sets "good" if we split the permutation $$$p$$$ on sets $$$[p_1, \dots, p_{pos}]$$$ and $$$[p_{pos} + 1, \dots, p_n]$$$ in such way that after transformations all elements in the first set less than $$$val$$$. It's easy to see that the total cost is equal to sum of weights $$$a_i$$$ where $$$i \le pos$$$ and $$$p_i \ge val$$$ and $$$a_i$$$ where $$$i > pos$$$ and $$$p_i < val$$$.
So what will happen if we increase $$$val$$$ by $$$1$$$? Let's define the position of $$$p_k = val$$$ as $$$k$$$. For each $$$pos \ge k$$$ we don't need to move $$$p_k$$$ to the second set anymore, so we should make $$$t[pos] -= a_k$$$. On the other hand, for each $$$pos < k$$$ we need to move $$$p_k$$$ from the second set to the first one now, so we should make $$$t[pos] += a_k$$$.
The answer will be equal to the $$$\min\limits_{1 \le pos < n}(t[pos])$$$. It means that we should handle two operations: add some value on the segment and ask minimum on the segment. So we can store all $$$t[pos]$$$ in pretty standart Segment Tree with "add on segment" and "minimum on segment" while iterating over $$$val$$$. So the total complexity is $$$O(n \log{n})$$$.