Lu Ban was an ancient Chinese carpenter, engineer, and inventor. Once, the King invite Lu Ban to create a rectangular chess board from a precious marble.

The face of the marble can be described as a polygon joined by continuous small rectangular marbles.

Two continuous small marbles have a common border. They can have di?erent heights but all have the same width which is equal to one unit. In the following ?gure, the marble includes the rectangles with heights in a row from left to right 2, 1, 4, 5, 1, 3, 3 and the width is all 1.

Your task is to help Lu Ban the maximum area rectangle inside the marble. In the ?gure above, the answer is the cross-hatching rectangle.

Input

The input ?le contains one or more test cases. Each test case describes one polygon in one line. The line starts with a positive integer n \((n \le 10^6)\) which is the number of small rectangles joining to be the polygon. The next n integers in the line \((H_1, H_2, ... H_n)\) where \((0 \le H_i \le 10^8)\) describes the heights of the small rectangles from left to right respectively. The ?le ends with the single 0.

Output

Each line contains the answer of the corresponding test case which is the area of your found rectangle.

Examples

Input

7 
2 1 4 5 1 3 3
4
1000 1000 1000 1000
0

Output

8
4000

Explain

• Test case 1: the maximum area rectangle is 8 = 4 * 2 because 4 is minimum in range [3, 4]