Po, a five-year-old kid loves to play with rectangles. He has n of rectangular boxes. He arranges these rectangular boxes in a two-dimensional landscape. The height of each rectangular box is denoted by hi ,i∈[1,N].
If you join K boxes, they will form a solid rectangle of area = K×min(hi,hi+1,…,hi+k−1)
Given n number of boxes. Your aim is to find greatest solid area formed by consecutive rectangular boxes.
Input::: The first line contains N, the number of rectangular boxes altogether. The second line contains N space-separated integers, each representing the height of a box.
Output::: One integer representing the maximum area of rectangle formed.
Constraints::: 1≤N≤10^5, 1≤hi≤10^6.
From the image given below, the largest area is possible is possible if we choose the boxes at positions 2,3,4 and 5. Hence, the area is 4min(2,3,2,4) = 42 = 8
