시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6552 1604 1057 25.317%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1000000000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 큰 직사각형의 넓이를 출력한다.

예제 입력 1

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1

8
4000
W3sicHJvYmxlbV9pZCI6IjY1NDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNWVjXHViN2VjIFx1YWMxY1x1YWMwMCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWQ2MTVcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YjEwOFx1YmU0NFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YjE5Mlx1Yzc3NFx1YWMwMCAyLCAxLCA0LCA1LCAxLCAzLCAzXHVjNzc0XHVhY2UwIFx1YjEwOFx1YmU0NFx1YWMwMCAxXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hpc3RvZ3JhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwLDAwMCkgXHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBoPHN1Yj4xPFwvc3ViPiwgLi4uLCBoPHN1Yj5uPFwvc3ViPiAoMCAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDAwMDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzQwIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YmE3MCwgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjEwOFx1YmU0NFx1YjI5NCAxXHVjNzc0XHVhY2UwLCBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTQ5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFyZ2VzdCBSZWN0YW5nbGUgaW4gYSBIaXN0b2dyYW0iLCJkZXNjcmlwdGlvbiI6IjxwPkEgaGlzdG9ncmFtIGlzIGEgcG9seWdvbiBjb21wb3NlZCBvZiBhIHNlcXVlbmNlIG9mIHJlY3RhbmdsZXMgYWxpZ25lZCBhdCBhIGNvbW1vbiBiYXNlIGxpbmUuIFRoZSByZWN0YW5nbGVzIGhhdmUgZXF1YWwgd2lkdGhzIGJ1dCBtYXkgaGF2ZSBkaWZmZXJlbnQgaGVpZ2h0cy4gRm9yIGV4YW1wbGUsIHRoZSBmaWd1cmUgb24gdGhlIGxlZnQgc2hvd3MgdGhlIGhpc3RvZ3JhbSB0aGF0IGNvbnNpc3RzIG9mIHJlY3RhbmdsZXMgd2l0aCB0aGUgaGVpZ2h0cyAyLCAxLCA0LCA1LCAxLCAzLCAzLCBtZWFzdXJlZCBpbiB1bml0cyB3aGVyZSAxIGlzIHRoZSB3aWR0aCBvZiB0aGUgcmVjdGFuZ2xlczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oaXN0b2dyYW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjUwNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlVzdWFsbHksIGhpc3RvZ3JhbXMgYXJlIHVzZWQgdG8gcmVwcmVzZW50IGRpc2NyZXRlIGRpc3RyaWJ1dGlvbnMsIGUuZy4sIHRoZSBmcmVxdWVuY2llcyBvZiBjaGFyYWN0ZXJzIGluIHRleHRzLiBOb3RlIHRoYXQgdGhlIG9yZGVyIG9mIHRoZSByZWN0YW5nbGVzLCBpLmUuLCB0aGVpciBoZWlnaHRzLCBpcyBpbXBvcnRhbnQuIENhbGN1bGF0ZSB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByZWN0YW5nbGUgaW4gYSBoaXN0b2dyYW0gdGhhdCBpcyBhbGlnbmVkIGF0IHRoZSBjb21tb24gYmFzZSBsaW5lLCB0b28uIFRoZSBmaWd1cmUgb24gdGhlIHJpZ2h0IHNob3dzIHRoZSBsYXJnZXN0IGFsaWduZWQgcmVjdGFuZ2xlIGZvciB0aGUgZGVwaWN0ZWQgaGlzdG9ncmFtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgZGVzY3JpYmVzIGEgaGlzdG9ncmFtIGFuZCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4sIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcyBpdCBpcyBjb21wb3NlZCBvZi4gWW91IG1heSBhc3N1bWUgdGhhdCAxJmx0Oz1uJmx0Oz0xMDAwMDAuIFRoZW4gZm9sbG93IG4gaW50ZWdlcnMgaDxzdWI+MTxcL3N1Yj4sLi4uLGg8c3ViPm48XC9zdWI+LCB3aGVyZSAwJmx0Oz1oPHN1Yj5pPFwvc3ViPiZsdDs9MTAwMDAwMDAwMC4gVGhlc2UgbnVtYmVycyBkZW5vdGUgdGhlIGhlaWdodHMgb2YgdGhlIHJlY3RhbmdsZXMgb2YgdGhlIGhpc3RvZ3JhbSBpbiBsZWZ0LXRvLXJpZ2h0IG9yZGVyLiBUaGUgd2lkdGggb2YgZWFjaCByZWN0YW5nbGUgaXMgMS4gQSB6ZXJvIGZvbGxvd3MgdGhlIGlucHV0IGZvciB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBpbiB0aGUgc3BlY2lmaWVkIGhpc3RvZ3JhbS4gUmVtZW1iZXIgdGhhdCB0aGlzIHJlY3RhbmdsZSBtdXN0IGJlIGFsaWduZWQgYXQgdGhlIGNvbW1vbiBiYXNlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: kth004