Largest Rectangle from Vertical Sticks

Given a set of vertical sticks represented by pairs of integers \(x_i\) and \(h_i\), where \(x_i\) is the x-coordinate and \(h_i\) is the height of a stick, determine the area of the largest rectangle that can be formed by any contiguous subset of these sticks.

The area of a rectangle formed by a group of contiguous sticks is computed as:

\(\text{Area} = h_{\min} \times k\)

where \(h_{\min}\) is the minimum height among the selected sticks and \(k\) is the number of sticks in the group.

For example, given the heights derived from the pairs [1, 2, 2, 1, 3, 5, 4, 6, 5, 2], the maximum area that can be achieved is 10.

inputFormat

A single line containing pairs of integers separated by spaces. Each pair represents the x-coordinate and the height of a stick respectively. The input format is: x1 h1 x2 h2 ... xn hn.

outputFormat

An integer representing the maximum rectangular area that can be formed from a contiguous subset of the given sticks.## sample

1 2 2 1 3 5 4 6 5 2

10