최대공간

인접한 빌딩의 높이를 나타내는 다양한 양의 정수배열을 입력 받아 단 하나의 빌딩 또는 여러개의 인접 빌딩안에 만들 수 있는 가장 큰 사각형의 영역을 반환하는 함수를 작성하세요. 모든 빌딩의 너비는 1입니다.

예를 들어, 주어진 빌딩들이 [2, 1, 2]일 때, 만들 수 있는 가장 큰 사각형의 영역은 세개의 빌딩을 모두 사용한 3입니다. 세 빌딩들의 최소 높이는 1이므로 높이가 1이고 너비가 3(빌딩갯수)인 사각형을 만들 수 있습니다. 첫 번째 빌딩이나 마지막 빌딩만 사용하여 영역 2의 사각형을 만들 수도 있지만, 이는 분명히 가장 큰 사각형이 아닙니다. 마찬가지로 첫 번째 및 두 번째 빌딩 또는 두 번째 및 세 번째 빌딩을 사용하여 영역 2의 사각형을 만들 수 있습니다.

좀 더 명확히 하기 위해 생성된 사각형의 너비는 사각형을 만드는 데 사용되는 빌딩 갯수이며 높이는 사각형을 만드는 데 사용되는 가장 작은 빌딩의 높이입니다.

사각형을 만들 수 없는 경우 함수는 0을 반환해야 합니다.

예제 1

입력

buildings = [1, 3, 4, 3, 4, 1, 5, 3, 2]

출력

12

// 입력된 빌딩의 예