시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7373 2606 1770 38.689%

문제

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

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

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

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

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

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

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE3MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YWMwMD8gXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViOWM5XHViMzAwXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBoZWlnaHQ9XCIxNjhcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC8yMDEwMDZcL2hpc3QuUE5HXCIgd2lkdGg9XCIyMzFcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWFjMDRcdWFjYTlcdWM3NDAgXHVjNzdjXHVjODE1XHVkNTU4XHVhY2UwLCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzcwNCBcdWFkZjhcdWI5YmNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWFjMDFcdWFjMDEgMiAxIDQgNSAxIDMgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc3NFx1YWMwMCBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NTggXHViZTU3XHVhZTA4IFx1Y2U1YyBcdWJkODBcdWJkODRcdWM3NzQgXHVhZGY4IFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjMTFcdWJjYzBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWM1NDRcdWI3YWJcdWJjYzBcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHVhYzhjIFx1YWRmOFx1YjgyNFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTY2XCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvMjAxMDA2XC9oaXN0by5QTkdcIiB3aWR0aD1cIjIzNlwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1ZDU4OVx1YzVkMFx1YjI5NCBOICgxICZsZTsgTiAmbGU7Jm5ic3A7MTAwLDAwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NTggXHVhYzAwXHViODVjIFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOIFx1ZDU4OVx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0Jm5ic3A7MSwwMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMjBcdWM1YjVcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFyZ2VzdCBSZWN0YW5nbGUgaW4gYSBIaXN0b2dyYW0iLCJkZXNjcmlwdGlvbiI6IjxwPkEgaGlzdG9ncmFtIGlzIGEgcG9seWdvbiBjb21wb3NlZCBvZiBhIHNlcXVlbmNlIG9mIHJlY3RhbmdsZXMgYWxpZ25lZCBhdCBhIGNvbW1vbiBiYXNlIGxpbmUuIFRoZSByZWN0YW5nbGVzIGhhdmUgZXF1YWwgd2lkdGhzIGJ1dCBtYXkgaGF2ZSBkaWZmZXJlbnQgaGVpZ2h0cy4gRm9yIGV4YW1wbGUsIHRoZSBmaWd1cmUgb24gdGhlIGxlZnQgc2hvd3MgdGhlIGhpc3RvZ3JhbSB0aGF0IGNvbnNpc3RzIG9mIHJlY3RhbmdsZXMgd2l0aCB0aGUgaGVpZ2h0cyAyLCAxLCA0LCA1LCAxLCAzLCAzLCBtZWFzdXJlZCBpbiB1bml0cyB3aGVyZSAxIGlzIHRoZSB3aWR0aCBvZiB0aGUgcmVjdGFuZ2xlczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oaXN0b2dyYW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjUwNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlVzdWFsbHksIGhpc3RvZ3JhbXMgYXJlIHVzZWQgdG8gcmVwcmVzZW50IGRpc2NyZXRlIGRpc3RyaWJ1dGlvbnMsIGUuZy4sIHRoZSBmcmVxdWVuY2llcyBvZiBjaGFyYWN0ZXJzIGluIHRleHRzLiBOb3RlIHRoYXQgdGhlIG9yZGVyIG9mIHRoZSByZWN0YW5nbGVzLCBpLmUuLCB0aGVpciBoZWlnaHRzLCBpcyBpbXBvcnRhbnQuIENhbGN1bGF0ZSB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByZWN0YW5nbGUgaW4gYSBoaXN0b2dyYW0gdGhhdCBpcyBhbGlnbmVkIGF0IHRoZSBjb21tb24gYmFzZSBsaW5lLCB0b28uIFRoZSBmaWd1cmUgb24gdGhlIHJpZ2h0IHNob3dzIHRoZSBsYXJnZXN0IGFsaWduZWQgcmVjdGFuZ2xlIGZvciB0aGUgZGVwaWN0ZWQgaGlzdG9ncmFtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgZGVzY3JpYmVzIGEgaGlzdG9ncmFtIGFuZCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4sIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcyBpdCBpcyBjb21wb3NlZCBvZi4gWW91IG1heSBhc3N1bWUgdGhhdCAxJmx0Oz1uJmx0Oz0xMDAwMDAuIFRoZW4gZm9sbG93IG4gaW50ZWdlcnMgaDxzdWI+MTxcL3N1Yj4sLi4uLGg8c3ViPm48XC9zdWI+LCB3aGVyZSAwJmx0Oz1oPHN1Yj5pPFwvc3ViPiZsdDs9MTAwMDAwMDAwMC4gVGhlc2UgbnVtYmVycyBkZW5vdGUgdGhlIGhlaWdodHMgb2YgdGhlIHJlY3RhbmdsZXMgb2YgdGhlIGhpc3RvZ3JhbSBpbiBsZWZ0LXRvLXJpZ2h0IG9yZGVyLiBUaGUgd2lkdGggb2YgZWFjaCByZWN0YW5nbGUgaXMgMS4gQSB6ZXJvIGZvbGxvd3MgdGhlIGlucHV0IGZvciB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBpbiB0aGUgc3BlY2lmaWVkIGhpc3RvZ3JhbS4gUmVtZW1iZXIgdGhhdCB0aGlzIHJlY3RhbmdsZSBtdXN0IGJlIGFsaWduZWQgYXQgdGhlIGNvbW1vbiBiYXNlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2003 H번

  • 문제를 번역한 사람: author5
  • 빠진 조건을 찾은 사람: sait2000