시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB81413449.275%

문제

레프는 너비가 1이고, 높이가 h1, ⋯, hNN개의 막대기들이 많이 있다. 레프는 이 막대기들을 사용해서 학생들에게 히스토그램에 완전히 포함되는 직사각형 중 넓이가 가장 큰 것을 구하는 문제를 내려고 한다.

N명의 학생들에게는 서로 다른 문제를 내야 하는데, 히스토그램을 만들 막대기 종류가 부족했던 레프는 다음과 같이 너비가 (N − 1)인 히스토그램을 N개 만들기로 했다.

  • i번째 막대기를 제거하고, 높이가 h1, ⋯, hi − 1, hi + 1, ⋯, hN인 (N − 1)개의 막대기들을 순서대로 이어붙여 히스토그램 Hi를 만든다.

Hi에서의 직사각형 넓이의 최댓값을 Si라고 하자. S1, ⋯, SN을 구하는 프로그램을 작성하여, 레프가 편하게 채점할 수 있도록 도와주자!

입력

첫째 줄에 양의 정수 N이 주어진다. (2 ≤ N ≤ 500 000)

둘째 줄에 N개의 정수 h1, ⋯, hN이 공백으로 구분되어 주어진다. (1 ≤ hi ≤ 109)

출력

첫째 줄에 N개의 정수 S1, ⋯, SN을 공백으로 구분하여 출력한다.

예제 입력 1

6
1 4 3 6 2 5

예제 출력 1

10 8 8 8 12 9