Largest Square in Skyscraper Outline

A city has a row of skyscrapers. Building i has height cityLine[i], every building has width 1, and there are no gaps between adjacent buildings. Find the area of the largest square that fits completely inside the outline of this row of buildings.

输入格式

The first line contains n. The second line contains n integers cityLine[0..n-1], separated by whitespace. 1≤n≤3×10^6, 1≤cityLine[i]≤10^8.

输出格式

Output one integer: the area of the largest square. The answer may exceed the 32-bit integer range.

样例 1

输入：

5
3 1 3 2 1

输出：

4

样例 2

输入：

3
4 3 4

输出：

9

样例 3

输入：

7
1 5 5 5 5 5 1

输出：

25

样例说明

Example 1: in [3,1,3,2,1], buildings 3 and 4 have heights 3 and 2, so a square of side 2 fits, with area 4. Example 2: in [4,3,4], all three buildings are at least 3 tall, so a square of side 3 fits, with area 9. Example 3: the middle five buildings have height 5, so a square of side 5 fits, with area 25.