27072번 - Maxtrix

길이가 $N$인 두 정수 배열 $A, B$가 주어진다. 이때 $N \times N$ 크기의 행렬 $C$가 다음과 같이 정의된다.

$$C_{ij} = A_i + B_j - ij$$

$1$ 이상 $N$ 이하의 모든 정수 $k$에 대해 각각 $\max_{1 \le i \le k \le j \le N} C_{ij}$를 계산하라.

첫 번째 줄에 두 배열의 길이를 나타내는 정수 $N$이 주어진다.

두 번째 줄에는 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에는 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

$N$개의 줄에 걸쳐 답을 출력한다.

• $1 \le N \le 250\,000$
• $A, B$의 모든 원소의 절댓값은 $10^{18}$ 이하.