시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 9 5 5 55.556%

문제

Svakom cijelom broju j između 1 i n pridružen je broj hj. Te brojeve ćemo prikazivati histogramom. Histogram crtamo tako da za svaki broj j nacrtamo stupac širine 1 i visine hj te sve takve stupce uredno posložimo na x-os slijeva nadesno počevši od ishodišta.

Primjeri histograma koji odgovaraju probnim primjerima.

Milan ima jedan takav histogram i na njega želi zalijepiti poster pravokutnog oblika na kojemu je prikazan njegov najveći heroj – gospodin Malnar.

Za pravokutnik kažemo da je pravilno pozicioniran unutar histograma ako mu vrhovi imaju cjelobrojne koordinate, stranice su mu paralelne s koordinatnim osima te je unutrašnjost tog pravokutnika u potpunosti prekrivena histogramom.

Odredite za svaki broj j između 1 i n iznos najveće površine pravokutnika koji se može pravilno pozicionirati unutar prvih j stupaca histograma.

입력

U prvom je retku prirodni broj n (1 ≤ n ≤ 2 · 105), broj stupaca u histogramu.

U sljedećem se retku nalazi n prirodnih brojeva h1, h2, . . . , hn (1 ≤ hi ≤ 107), visine stupaca u histogramu.

출력

U jedini redak ispišite n brojeva, j-ti od tih brojeva predstavlja iznos najveće površine pravokutnika koji se može pravilno pozicionirati unutar prvih j stupaca histograma.

예제 입력 1

3
2 3 7

예제 출력 1

2 4 7

예제 입력 2

5
3 4 2 7 6

예제 출력 2

3 6 6 8 12