34341번 - 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의 최대 가치를 뜻한다.

제한

힌트