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

아래 그림과 같이 누적 히스토그램이 하나 있다. 누적 히스토그램의 위 쪽에 있는 초록색 영역으로 만들 수 있는 가장 큰 직사각형의 넓이를 구하시오.

입력으로 초록 막대의 총 개수 N (N은 100,000 이하의 자연수)과 파란 막대의 길이, 초록 막대의 길이 정보가 주어진다. 각 길이는 1,000,000 이하의 자연수이며, 왼쪽 막대부터 순서대로 주어진다. (제한시간 1초)

* 영감을 받은 문제: https://www.acmicpc.net/problem/6549
* 회고: 어떻게든 원본 문제를 감주기 위해 스토리를 만들려고 했으나, 다 허접해서 그만두었음.