23673번 - Interesting Drug 다국어

문제

During Younghun's trip to IOI in Japan, he was nervous with the upcoming competition. So, he went out for nearby playground to relax himself. In the playground, there was $N$ drugs lying in a straight line. The drugs are numbered from 1ドル$ to $N$ from left to right, and their locations are distinct. Younghun was curious about the drug, and swallowed one of them.

After then, due to the effect of drug, Younghun started to dance unconsciously. Younghun was unable to control himself from dancing, but was only able to control the direction he was moving (left or right in the straight line). When Younghun is moving, he automatically swallows any drug in his way. After swallowing the drug, the drug disappears from the playground.

In the end, Younghun swallowed all $N$ drugs, and found his consciousness. He was not shocked about what he've done (just like all great K-pop stars, dancing is his life), but was worried about the potential health risks of drugs. Let $P = \{P_1, P_2, \cdots, P_n\}$ be the sequence of drugs in order of Younghun's consumption. After some research, Younghun realized that he receives $D_i$ damage if $P_{C_i} = i$.

Write a program which calculates the maximum possible damage dealt by starting at drug $i$. In other words, for each 1ドル \leq i \leq N,ドル you should calculate the maximum possible damage among all possible sequence of consumption with $P_1 = i$.

입력

The first line of the input contains a single integer $N,ドル denoting the number of drugs. (2ドル \leq N \leq 300,000円$)

The next line contains $N$ space-separated integer $C_1, C_2, \cdots, C_N,ドル which is the sequence $C$ as explained above. (1ドル \leq C_i \leq N$)

The last line contains $N$ space-separated integer $D_1, D_2, \cdots, D_N,ドル which is the possible damage dealt by drug $i$. (1ドル \leq D_i \leq 10^9$)

출력

You should print a single line containing $N$ space-separated integer: The $i$-th number should be the maxmum possibly damage dealt by starting at drug $i$.

제한

노트

If $i = 1,ドル Younghun can only move right. This gives $P = \{1, 2, 3, 4, 5\},ドル which deals damage 1ドル + 4 = 5$.

If $i = 2,ドル Younghun can move left, right, right, right. This gives $P = \{2, 1, 3, 4, 5\},ドル which deals damage 1ドル$.

If $i = 3,ドル Younghun can move right, right, left, left. This gives $P = \{3, 4, 5, 2, 1\},ドル which deals damage 10ドル$.

If $i = 4,ドル Younghun can move left, right, left, left. This gives $P = \{4, 3, 5, 2, 1\},ドル which deals damage 2ドル + 10 = 12$.

If $i = 5,ドル Younghun can only move left. This gives $P = \{5, 4, 3, 2, 1\},ドル which deals damage 1ドル$.