Maximum Area Calculations

You are given a choice between two tasks. In Mode 1, you are provided with a histogram represented as an array of positive integers. Your goal is to determine the maximum rectangular area that can be obtained in the histogram. For a given rectangle, if the minimum height in the range is \(h\) and the width is \(w\), the area is computed as \( h \times w \).

In Mode 2, you are given a square grid of size \( n \times n \) consisting of characters '0' and '1'. The task is to find the largest rectangle containing only '1's and output its area. The area of a rectangle is calculated in a similar way: \( \text{area} = \text{height} \times \text{width} \).

Efficient approaches using stacks and dynamic programming are recommended for both tasks.

inputFormat

The input begins with a line containing a single integer to indicate the mode:

• 1: Histogram Mode
• 2: Rectangle Mode (binary grid)

If the mode is 1:

• The second line contains an integer \( n \) denoting the number of histogram bars.
• The third line contains \( n \) space-separated integers representing the heights of the histogram bars.

If the mode is 2:

• The second line contains an integer \( n \) representing the dimension of the square grid.
• This is followed by \( n \) lines, each containing \( n \) space-separated characters (either '0' or '1').

outputFormat

Output a single integer representing the maximum area as computed from the input data.

## sample

1
6
2 1 5 6 2 3

10