시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 128 MB 3301 772 (23%) 656
문제
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있다. 예를 들어, 아래에서 왼쪽 그림은 높이가 순서대로 $2, 1, 4, 5, 1, 3, 3$이고, 너비는 모두 $1$인 직사각형으로 이루어진 히스토그램이다. ![히스토그램](/download_file/62723647408dedb05ff8c94f10d197919a3f5cb230b2f27331978d41cb05b91a/%EA%B7%B8%EB%A6%BC1.png/?show=true) 너비가 1인 N개의 직사각형으로 이루어진 히스토그램이 주어진다. 이 때, 위에서 오른쪽 그림처럼 히스토그램 내에서 가장 큰 직사각형의 크기를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다. 각 테스트케이스의 첫 정수는 직사각형의 수 $N$을 의미한다$(1 \le N \le 100,000)$. 만약 $N=0$이면 입력의 끝을 의미한다. 같은 줄에 $N$개의 정수가 공백을 사이에 두고 주어진다. 이는 순서대로 직사각형 $N$개의 높이를 나타낸다. 주어지는 높이는 $1,000,000,000$ 보다 크지 않다.
출력
각 테스트케이스 마다 한 줄에 히스토그램 내에서 가장 큰 직사각형의 크기를 출력한다.
힌트
### 예제 입력 ``` 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 ``` ### 예제 출력 ``` 8 4000 ```