John's house has bizarre fencing. There are N fences. Though the contiguous fences have the constant width of 1 unit but their height varies. Height of these fences is represented by array H = [h1, h2... hN].
John loves his fences but has to finally bow down to his wife's repeated requests of replacing them with the regular fences. Before taking them down, John wants to keep some part of the fences as souvenir. He decides to carve out the largest rectangular area possible where the largest rectangle can be made of a number of contiguous fence. Note that sides of the rectangle should be parallel to X and Y axis.
Let's say there are 6 fences, and their height is, H = [2, 5, 7, 4, 1, 8]. Then they can be represented as