시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3600 1151 811 35.617%

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 <= N <= 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE3MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YWMwMD8gXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViOWM5XHViMzAwXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjMxXCIgaGVpZ2h0PVwiMTY4XCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL2hpc3QuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWFjMDRcdWFjYTlcdWM3NDAgXHVjNzdjXHVjODE1XHVkNTU4XHVhY2UwLCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzcwNCBcdWFkZjhcdWI5YmNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWFjMDFcdWFjMDEgMiAxIDQgNSAxIDMgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWFjMDBcdWM3YTUgXHViMTEzXHVjNzc0XHVhYzAwIFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWJlNTdcdWFlMDggXHVjZTVjIFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWFkZjggXHVjNjA4XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmMxMVx1YmNjMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YzU0NFx1YjdhYlx1YmNjMFx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWFjOGMgXHVhZGY4XHViODI0XHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjM2XCIgaGVpZ2h0PVwiMTY2XCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL2hpc3RvLlBOR1wiIFwvPjxcL3A+XHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWQ1ODlcdWM1ZDBcdWIyOTQgTiAoMSAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMwMFx1Yjg1YyBcdWNlNzhcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTiBcdWQ1ODlcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDIwXHVjNWI1XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFyZ2VzdCBSZWN0YW5nbGUgaW4gYSBIaXN0b2dyYW0iLCJkZXNjcmlwdGlvbiI6IjxwPkEgaGlzdG9ncmFtIGlzIGEgcG9seWdvbiBjb21wb3NlZCBvZiBhIHNlcXVlbmNlIG9mIHJlY3RhbmdsZXMgYWxpZ25lZCBhdCBhIGNvbW1vbiBiYXNlIGxpbmUuIFRoZSByZWN0YW5nbGVzIGhhdmUgZXF1YWwgd2lkdGhzIGJ1dCBtYXkgaGF2ZSBkaWZmZXJlbnQgaGVpZ2h0cy4gRm9yIGV4YW1wbGUsIHRoZSBmaWd1cmUgb24gdGhlIGxlZnQgc2hvd3MgdGhlIGhpc3RvZ3JhbSB0aGF0IGNvbnNpc3RzIG9mIHJlY3RhbmdsZXMgd2l0aCB0aGUgaGVpZ2h0cyAyLCAxLCA0LCA1LCAxLCAzLCAzLCBtZWFzdXJlZCBpbiB1bml0cyB3aGVyZSAxIGlzIHRoZSB3aWR0aCBvZiB0aGUgcmVjdGFuZ2xlczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oaXN0b2dyYW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjUwNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlVzdWFsbHksIGhpc3RvZ3JhbXMgYXJlIHVzZWQgdG8gcmVwcmVzZW50IGRpc2NyZXRlIGRpc3RyaWJ1dGlvbnMsIGUuZy4sIHRoZSBmcmVxdWVuY2llcyBvZiBjaGFyYWN0ZXJzIGluIHRleHRzLiBOb3RlIHRoYXQgdGhlIG9yZGVyIG9mIHRoZSByZWN0YW5nbGVzLCBpLmUuLCB0aGVpciBoZWlnaHRzLCBpcyBpbXBvcnRhbnQuIENhbGN1bGF0ZSB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByZWN0YW5nbGUgaW4gYSBoaXN0b2dyYW0gdGhhdCBpcyBhbGlnbmVkIGF0IHRoZSBjb21tb24gYmFzZSBsaW5lLCB0b28uIFRoZSBmaWd1cmUgb24gdGhlIHJpZ2h0IHNob3dzIHRoZSBsYXJnZXN0IGFsaWduZWQgcmVjdGFuZ2xlIGZvciB0aGUgZGVwaWN0ZWQgaGlzdG9ncmFtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgZGVzY3JpYmVzIGEgaGlzdG9ncmFtIGFuZCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4sIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcyBpdCBpcyBjb21wb3NlZCBvZi4gWW91IG1heSBhc3N1bWUgdGhhdCAxJmx0Oz1uJmx0Oz0xMDAwMDAuIFRoZW4gZm9sbG93IG4gaW50ZWdlcnMgaDxzdWI+MTxcL3N1Yj4sLi4uLGg8c3ViPm48XC9zdWI+LCB3aGVyZSAwJmx0Oz1oPHN1Yj5pPFwvc3ViPiZsdDs9MTAwMDAwMDAwMC4gVGhlc2UgbnVtYmVycyBkZW5vdGUgdGhlIGhlaWdodHMgb2YgdGhlIHJlY3RhbmdsZXMgb2YgdGhlIGhpc3RvZ3JhbSBpbiBsZWZ0LXRvLXJpZ2h0IG9yZGVyLiBUaGUgd2lkdGggb2YgZWFjaCByZWN0YW5nbGUgaXMgMS4gQSB6ZXJvIGZvbGxvd3MgdGhlIGlucHV0IGZvciB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBpbiB0aGUgc3BlY2lmaWVkIGhpc3RvZ3JhbS4gUmVtZW1iZXIgdGhhdCB0aGlzIHJlY3RhbmdsZSBtdXN0IGJlIGFsaWduZWQgYXQgdGhlIGNvbW1vbiBiYXNlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d