시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4166 1352 949 36.542%

문제

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

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 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
W3sicHJvYmxlbV9pZCI6IjE3MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YWMwMD8gXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViOWM5XHViMzAwXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBoZWlnaHQ9XCIxNjhcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC8yMDEwMDZcL2hpc3QuUE5HXCIgd2lkdGg9XCIyMzFcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWFjMDRcdWFjYTlcdWM3NDAgXHVjNzdjXHVjODE1XHVkNTU4XHVhY2UwLCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzcwNCBcdWFkZjhcdWI5YmNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWFjMDFcdWFjMDEgMiAxIDQgNSAxIDMgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc3NFx1YWMwMCBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NTggXHViZTU3XHVhZTA4IFx1Y2U1YyBcdWJkODBcdWJkODRcdWM3NzQgXHVhZGY4IFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjMTFcdWJjYzBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWM1NDRcdWI3YWJcdWJjYzBcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHVhYzhjIFx1YWRmOFx1YjgyNFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTY2XCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvMjAxMDA2XC9oaXN0by5QTkdcIiB3aWR0aD1cIjIzNlwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1ZDU4OVx1YzVkMFx1YjI5NCBOICgxICZsZTsgTiAmbGU7Jm5ic3A7MTAwLDAwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NTggXHVhYzAwXHViODVjIFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOIFx1ZDU4OVx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDIwXHVjNWI1XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTcyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikxhcmdlc3QgUmVjdGFuZ2xlIGluIGEgSGlzdG9ncmFtIiwiZGVzY3JpcHRpb24iOiI8cD5BIGhpc3RvZ3JhbSBpcyBhIHBvbHlnb24gY29tcG9zZWQgb2YgYSBzZXF1ZW5jZSBvZiByZWN0YW5nbGVzIGFsaWduZWQgYXQgYSBjb21tb24gYmFzZSBsaW5lLiBUaGUgcmVjdGFuZ2xlcyBoYXZlIGVxdWFsIHdpZHRocyBidXQgbWF5IGhhdmUgZGlmZmVyZW50IGhlaWdodHMuIEZvciBleGFtcGxlLCB0aGUgZmlndXJlIG9uIHRoZSBsZWZ0IHNob3dzIHRoZSBoaXN0b2dyYW0gdGhhdCBjb25zaXN0cyBvZiByZWN0YW5nbGVzIHdpdGggdGhlIGhlaWdodHMgMiwgMSwgNCwgNSwgMSwgMywgMywgbWVhc3VyZWQgaW4gdW5pdHMgd2hlcmUgMSBpcyB0aGUgd2lkdGggb2YgdGhlIHJlY3RhbmdsZXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaGlzdG9ncmFtLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1OXB4OyB3aWR0aDo1MDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Vc3VhbGx5LCBoaXN0b2dyYW1zIGFyZSB1c2VkIHRvIHJlcHJlc2VudCBkaXNjcmV0ZSBkaXN0cmlidXRpb25zLCBlLmcuLCB0aGUgZnJlcXVlbmNpZXMgb2YgY2hhcmFjdGVycyBpbiB0ZXh0cy4gTm90ZSB0aGF0IHRoZSBvcmRlciBvZiB0aGUgcmVjdGFuZ2xlcywgaS5lLiwgdGhlaXIgaGVpZ2h0cywgaXMgaW1wb3J0YW50LiBDYWxjdWxhdGUgdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3QgcmVjdGFuZ2xlIGluIGEgaGlzdG9ncmFtIHRoYXQgaXMgYWxpZ25lZCBhdCB0aGUgY29tbW9uIGJhc2UgbGluZSwgdG9vLiBUaGUgZmlndXJlIG9uIHRoZSByaWdodCBzaG93cyB0aGUgbGFyZ2VzdCBhbGlnbmVkIHJlY3RhbmdsZSBmb3IgdGhlIGRlcGljdGVkIGhpc3RvZ3JhbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGRlc2NyaWJlcyBhIGhpc3RvZ3JhbSBhbmQgc3RhcnRzIHdpdGggYW4gaW50ZWdlciBuLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMgaXQgaXMgY29tcG9zZWQgb2YuIFlvdSBtYXkgYXNzdW1lIHRoYXQgMSZsdDs9biZsdDs9MTAwMDAwLiBUaGVuIGZvbGxvdyBuIGludGVnZXJzIGg8c3ViPjE8XC9zdWI+LC4uLixoPHN1Yj5uPFwvc3ViPiwgd2hlcmUgMCZsdDs9aDxzdWI+aTxcL3N1Yj4mbHQ7PTEwMDAwMDAwMDAuIFRoZXNlIG51bWJlcnMgZGVub3RlIHRoZSBoZWlnaHRzIG9mIHRoZSByZWN0YW5nbGVzIG9mIHRoZSBoaXN0b2dyYW0gaW4gbGVmdC10by1yaWdodCBvcmRlci4gVGhlIHdpZHRoIG9mIGVhY2ggcmVjdGFuZ2xlIGlzIDEuIEEgemVybyBmb2xsb3dzIHRoZSBpbnB1dCBmb3IgdGhlIGxhc3QgdGVzdCBjYXNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgb24gYSBzaW5nbGUgbGluZSB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByZWN0YW5nbGUgaW4gdGhlIHNwZWNpZmllZCBoaXN0b2dyYW0uIFJlbWVtYmVyIHRoYXQgdGhpcyByZWN0YW5nbGUgbXVzdCBiZSBhbGlnbmVkIGF0IHRoZSBjb21tb24gYmFzZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==