폭이 1인 빌딩 N개가 붙어 서 있고 높이가 제각각이에요. 빌딩들에 걸쳐 붙일 수 있는 직사각형 간판의 최대 넓이를 구하세요. 간판은 빌딩보다 높이 나올 수 없어요.
힌트: 빌딩을 하나씩 보면서, 스택으로 '아직 끝나지 않은 직사각형'들을 관리해 보세요.
입력
첫째 줄에 빌딩 수 N이 주어져요. (1 ≤ N ≤ 5,000) 둘째 줄에 N개의 높이가 공백으로 구분되어 주어져요. (1 ≤ 높이 ≤ 100,000)
출력
간판의 최대 넓이를 출력해요.