33755번 - 물류 작업 최적화 서브태스크

문제

진흥이가 운영하는 물류 창고에서는 시각 1ドル$부터 $N$까지의 시간 동안 물류가 들어오거나 나갑니다. 특정 시각 $i$에서 순수 물류량은 들어온 물류량에서 나간 물류량을 뺀 값으로 정의되며, $A_i$로 표현됩니다. 이때 $A_i$의 절댓값은 1000ドル$ 이하입니다.

창고에서는 특정 시각에 업무를 처리하기 위해 아르바이트를 고용하려고 합니다. 아르바이트생이 일하는 동안 최대한 많은 물류를 처리할 수 있도록, 해당 시각 $t$을 포함하는 연속된 시간 구간 $[l,r]$을 적절히 선택하여 그 구간 내에서 처리하는 총 물류량 $A_{l} + A_{l+1} + \dots + A_{r}$을 최대로 만들려고 합니다. 이때, 선택된 구간에서 총 물류량이 음수일 수도 있음에 유의하세요.

아르바이트를 효율적으로 고용하기 위해, 각 시각 $t = 1, 2, \dots, N$에 대해, 그 시각을 포함하는 구간 중 총 물류량이 최대가 되는 값을 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 총 시간을 나타내는 정수 $N$이 주어집니다.

두 번째 줄에 각 시각에 해당되는 순수 물류량을 의미하는 정수 $A_{1}, A_{2}, \dots, A_{N}$이 공백으로 구분되어 주어집니다.

출력

시각 $t = 1, 2, \dots , N$에 대해 각각, 해당 시각을 포함하는 구간 중 총 물류량이 최대가 되는 값을 공백으로 구분하여 출력하세요.

제한

• 1ドル \le N \le 300\ 000$
• 모든 $i$에 대해, $-1000 \le A_{i} \le 1000$

서브태스크

힌트