Largest Square in Skyscraper Outline

A row of adjacent skyscrapers each has width 1, with heights given by the array cityLine. Find the area of the largest square that lies entirely within the outline of the buildings.

输入格式

The first line contains n (1≤n≤200000), and the second line contains n non-negative integers h_i (0≤h_i≤10^9). These input ranges are site supplements; the original problem listed no constraints.

输出格式

Output the maximum area of a square that fits.

样例 1

输入：

5
1 2 3 2 1

输出：

4

样例 2

输入：

3
4 3 4

输出：

9

样例 3

输入：

5
0 0 5 5 5

输出：

9