시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.7 초 128 MB2695210024718939.437%

문제

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

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 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+XHVjY2FiIFx1ZDU4OVx1YzVkMFx1YjI5NCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMwMFx1Yjg1YyBcdWNlNzhcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTiBcdWQ1ODlcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFx1YjYxMFx1YjI5NCAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAyMFx1YzViNVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXJnZXN0IFJlY3RhbmdsZSBpbiBhIEhpc3RvZ3JhbSIsImRlc2NyaXB0aW9uIjoiPHA+QSBoaXN0b2dyYW0gaXMgYSBwb2x5Z29uIGNvbXBvc2VkIG9mIGEgc2VxdWVuY2Ugb2YgcmVjdGFuZ2xlcyBhbGlnbmVkIGF0IGEgY29tbW9uIGJhc2UgbGluZS4gVGhlIHJlY3RhbmdsZXMgaGF2ZSBlcXVhbCB3aWR0aHMgYnV0IG1heSBoYXZlIGRpZmZlcmVudCBoZWlnaHRzLiBGb3IgZXhhbXBsZSwgdGhlIGZpZ3VyZSBvbiB0aGUgbGVmdCBzaG93cyB0aGUgaGlzdG9ncmFtIHRoYXQgY29uc2lzdHMgb2YgcmVjdGFuZ2xlcyB3aXRoIHRoZSBoZWlnaHRzIDIsIDEsIDQsIDUsIDEsIDMsIDMsIG1lYXN1cmVkIGluIHVuaXRzIHdoZXJlIDEgaXMgdGhlIHdpZHRoIG9mIHRoZSByZWN0YW5nbGVzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hpc3RvZ3JhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VXN1YWxseSwgaGlzdG9ncmFtcyBhcmUgdXNlZCB0byByZXByZXNlbnQgZGlzY3JldGUgZGlzdHJpYnV0aW9ucywgZS5nLiwgdGhlIGZyZXF1ZW5jaWVzIG9mIGNoYXJhY3RlcnMgaW4gdGV4dHMuIE5vdGUgdGhhdCB0aGUgb3JkZXIgb2YgdGhlIHJlY3RhbmdsZXMsIGkuZS4sIHRoZWlyIGhlaWdodHMsIGlzIGltcG9ydGFudC4gQ2FsY3VsYXRlIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBpbiBhIGhpc3RvZ3JhbSB0aGF0IGlzIGFsaWduZWQgYXQgdGhlIGNvbW1vbiBiYXNlIGxpbmUsIHRvby4gVGhlIGZpZ3VyZSBvbiB0aGUgcmlnaHQgc2hvd3MgdGhlIGxhcmdlc3QgYWxpZ25lZCByZWN0YW5nbGUgZm9yIHRoZSBkZXBpY3RlZCBoaXN0b2dyYW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBkZXNjcmliZXMgYSBoaXN0b2dyYW0gYW5kIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgbiwgZGVub3RpbmcgdGhlIG51bWJlciBvZiByZWN0YW5nbGVzIGl0IGlzIGNvbXBvc2VkIG9mLiBZb3UgbWF5IGFzc3VtZSB0aGF0IDEmbHQ7PW4mbHQ7PTEwMDAwMC4gVGhlbiBmb2xsb3cgbiBpbnRlZ2VycyBoPHN1Yj4xPFwvc3ViPiwuLi4saDxzdWI+bjxcL3N1Yj4sIHdoZXJlIDAmbHQ7PWg8c3ViPmk8XC9zdWI+Jmx0Oz0xMDAwMDAwMDAwLiBUaGVzZSBudW1iZXJzIGRlbm90ZSB0aGUgaGVpZ2h0cyBvZiB0aGUgcmVjdGFuZ2xlcyBvZiB0aGUgaGlzdG9ncmFtIGluIGxlZnQtdG8tcmlnaHQgb3JkZXIuIFRoZSB3aWR0aCBvZiBlYWNoIHJlY3RhbmdsZSBpcyAxLiBBIHplcm8gZm9sbG93cyB0aGUgaW5wdXQgZm9yIHRoZSBsYXN0IHRlc3QgY2FzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3QgcmVjdGFuZ2xlIGluIHRoZSBzcGVjaWZpZWQgaGlzdG9ncmFtLiBSZW1lbWJlciB0aGF0IHRoaXMgcmVjdGFuZ2xlIG11c3QgYmUgYWxpZ25lZCBhdCB0aGUgY29tbW9uIGJhc2UgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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