LIS 하나 빼기

길이 $N$인 정수 배열 $A=\[A\_1, A\_2, \cdots, A\_N]$이 주어진다. 배열의 각 원소 $A\_i$에는 가중치 $V\_i$가 대응된다. 이 때 모든 원소 $A\_i$는 서로 다른 정수이다.

이때, 배열 $A$의 부분 증가 수열 중 길이가 최대인 수열을 LIS라 하자. 부분 증가 수열이란, 배열에서 $0$개 이상의 원소를 제거하여 얻을 수 있는 증가 수열을 의미한다.

또한, 어떤 부분 수열을 구성하는 원소들의 가중치 합을 그 부분 수열의 가치라 정의한다.

각 $1 \leq i \leq N$에 대해, $A$에서 원소 $A\_i$를 제거한 배열 $A\_1, \cdots, A\_{i-1}, A\_{i+1}, \cdots, A\_N$ 에서 얻을 수 있는 LIS의 최대 가치를 구하여라.

첫째 줄에 $N$이 주어진다. ($2 \leq N \leq 300\ 000$)

둘째 줄에 $N$개의 양의 정수 $A\_1, A\_2,\cdots, A\_N$이 공백으로 구분되어 주어진다. $i\ne j$일 때 $A\_i\ne A\_j$를 만족한다. ($1 \leq A\_i \leq {10}^9$)

셋째 줄에 $N$개의 양의 정수 $V\_1, V\_2,\cdots, V\_N$이 공백으로 구분되어 주어진다. ($1 \leq V\_i \leq {10}^9$)

첫째 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 수는 $A$에서 원소 $A\_i$를 제거했을 때 얻을 수 있는 LIS의 최대 가치를 뜻한다.