407872: GYM102911 H Heavy Sort

Cindy has started exercising regularly and doing physical conditioning. Inspired by her favorite anime series, she decided to clean up a beach full of trash that people had been treating as a dumping site for their junk. It simultaneously functions as strength training, and a way for her to do some good for society!

There are $$$N$$$ pieces of junk in a single line. From left to right, the $$$i$$$th piece of junk has a height of $$$H_i$$$ and a weight of $$$W_i$$$; it is guaranteed that the heights of each object are distinct. Cindy wishes to sort the junk in increasing order of height. The only operation that Cindy can do is to pick up two adjacent objects and swap their positions in the line. Since the objects can be heavy, the total energy that Cindy expends is the product of the weights of the two objects. Formally, Cindy can swap the positions of the $$$i$$$th and $$$(i+1)$$$th objects, and doing so costs $$$W_i \times W_{i+1}$$$ units of energy.

What is the minimum amount of energy that Cindy needs to expend in order to sort the junk in ascending order of height?

The first line of input contains a single integer $$$N$$$, the number of pieces of junk.

The second line of input contains $$$N$$$ space-separated integers $$$H_1, H_2, \dots, H_N$$$, where $$$H_i$$$ is the height of the $$$i$$$th piece of junk.

The third line of input contains $$$N$$$ space-separated integers $$$W_1, W_2, \dots, W_N$$$, where $$$W_i$$$ is the weight of the $$$i$$$th piece of junk.

Output a single integer, the minimum amount of energy that Cindy needs to expend to sort the junk in increasing order of height.

It is recommended that Python users submit to PyPy for this problem.

$$$1 \leq N \leq 2\cdot 10^5$$$

$$$1 \leq H_i \leq 10^9$$$

$$$1 \leq W_i \leq 10^4$$$

It is guaranteed that $$$H_i \neq H_j$$$ for $$$i \neq j$$$.

Subtask 1 (35 points):

$$$N \leq 8$$$

Subtask 2 (15 points):

$$$N \leq 100$$$

Subtask 3 (20 points):

$$$N \leq 1000$$$

Subtask 4 (15 points):

All pieces of junk will have the same weight.

Subtask 5 (15 points):

No further constraints.

3
3 1 2
4 5 6

44

8
118 999 881 99 911 97 25 3
1 2 3 4 5 6 7 8

501

For the first sample test case, Cindy first swaps the objects of height $$$3$$$ and $$$1$$$, spending $$$4 \times 5 = 20$$$ energy. Then, she swaps the objects of height $$$3$$$ and $$$2$$$, spending $$$4 \times 6 = 24$$$ energy. The junk is now fully sorted in increasing order of height, and Cindy spent a total of $$$20+24 = 44$$$ energy.