P5503 [JSOI2016] Lighthouse

Along the border of JSOI, there are $N$ consecutive mountain peaks. The height of the $i$-th peak is $h_i$. For simplicity, we assume these $N$ peaks are arranged along a straight line. If a lighthouse of height $p$ ($p \ge 0$) is built on the $i$-th peak, JYY finds that this lighthouse can illuminate the $j$-th peak if and only if the following inequality holds: $$h_j \le h_i + p - \sqrt {|i-j|}$$ The king of JSOI wants JYY to provide, for each peak, the minimum height required to build a lighthouse that can illuminate all other peaks. Can you help JYY?

The input contains one line with a positive integer $N$. In the next $N$ lines, the $i$-th line contains a positive integer $h_i$, representing the height of the $i$-th peak.

The $i$-th line contains a non-negative integer, representing the minimum height $p_i$ required to build a lighthouse on the $i$-th peak.

For $100\%$ of the data, $1 < N \le 10^5$, $0 < h_i \le 10^9$. Translated by ChatGPT 5