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

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

• i번째 막대기를 제거하고, 높이가 h₁, ⋯, h_{i − 1}, h_{i + 1}, ⋯, h_N인 (N − 1)개의 막대기들을 순서대로 이어붙여 히스토그램 H_i를 만든다.

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

입력 형식

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

둘째 줄에 N개의 정수 h₁, ⋯, h_N이 공백으로 구분되어 주어진다. (1 ≤ h_i ≤ 10⁹)

출력 형식

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

예제 입력

6
1 4 3 6 2 5

예제 출력

10 8 8 8 12 9