히스토그램과 파란 직사각형

길이가 $n$인 정수 배열 $a$를 생각하자. 모든 $a_i$는 양의 정수이다. 이런 배열은 히스토그램으로 나타낼 수 있다. 히스토그램을 그리려면 $i$를 0부터 $n-1$까지 바꿔 가며, 꼭짓점이 $(i,0)$, $(i,a_i)$, $(i+1,a_i)$, $(i+1,0)$인 파란색 직사각형을 각각 그린다.

꼭짓점이 모두 정수 점이고 변이 좌표축과 평행한 직사각형의 내부 점이 모두 파란색이면, 그 직사각형은 히스토그램에 덮여 있다고 한다.

1 이상 $n$ 이하의 각 $j$에 대해, 주어진 히스토그램의 처음 $j$개 열이 덮는 직사각형 넓이의 최댓값을 구하라.

첫 줄에 정수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어진다. 이는 배열 $a$의 길이이다. 둘째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 $a_i$이다 ($1 \le a_i \le 10^7$).

$n$개의 정수를 한 줄에 하나씩 출력한다. $i$번째 정수는 주어진 히스토그램의 처음 $i$개 열이 덮는 직사각형 넓이의 최댓값이다.