Maximum Rectangle from Grid Paper

Given a piece of grid paper with one intact edge and an irregular, partially damaged remainder, the task is to cut out the largest possible rectangular piece.

The grid paper is composed of cells of side length \(1\). One edge of the paper is completely intact and its length is \(N\) (\(1 \leq N \leq 1\,000\,000\)). For each of the \(N\) columns, you are provided with the height of the remaining part of the grid (\(1 \leq \text{height} \leq 10\,000\)).

Your task is to compute the area of the largest rectangle that can be cut from this grid paper.

This problem is equivalent to finding the largest rectangle area in a histogram where each column's height is given.

inputFormat

The first line contains an integer \(N\), representing the number of columns and the length of the intact edge.

The second line contains \(N\) space-separated integers, where each integer represents the height of the leftover grid paper in that column.

outputFormat

Output a single integer representing the maximum area of the rectangle that can be cut out.

sample

1
5

5