히스토그램에서 가장 큰 직사각형

히스토그램은 밑변이 한 직선 위에 나란히 놓인 여러 개의 직사각형으로 이루어진 도형이다. 각 직사각형의 너비는 모두 $1$로 같지만 높이는 서로 다를 수 있다. 예를 들어 높이가 각각 $2, 1, 4, 5, 1, 3, 3$인 직사각형 $7$개를 왼쪽부터 나란히 붙이면 하나의 히스토그램이 된다.

주어진 히스토그램 안에 완전히 들어가는 직사각형 중에서 넓이가 가장 큰 것의 넓이를 구하는 프로그램을 작성하시오. 이때 찾는 직사각형은 연속한 몇 개의 막대에 걸쳐 있으며, 그 높이는 걸쳐 있는 막대들의 높이 중 가장 작은 값과 같다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 주어지며, 먼저 직사각형의 개수 $n$이 주어진다. ($1 \le n \le 100{,}000$) 이어서 히스토그램을 이루는 직사각형의 높이 $h_1, h_2, \ldots, h_n$이 왼쪽부터 오른쪽 순서로 주어진다. ($0 \le h_i \le 1{,}000{,}000{,}000$) 모든 직사각형의 너비는 $1$이다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 히스토그램에서 넓이가 가장 큰 직사각형의 넓이를 한 줄에 하나씩 출력한다.