문제

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

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

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

입력

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

두 번째 줄에 각 시각에 해당되는 순수 물류량을 의미하는 정수 이 공백으로 구분되어 주어집니다.

출력

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

제한

• 모든 에 대해,

서브태스크