Kevin has quite the reputation around ACPC: he is wholesome and brings happiness everywhere. Currently, he is building a rectangular water trough for cute stray animals in need.

He has a row of ~N~ wooden planks standing upright on a 2D plane. The ~i~-th plank from the left is located at ~x=i~ and has a height of ~A_i~.

Kevin may choose two planks ~i~ and ~j~, where ~i<j~, to form the walls of a trough. Normally, its capacity would be ~\min(A_i,A_j)\times(j-i)~. However, Kevin considers a trough wholesome only if neither wall extends above the water level. Therefore, the two chosen planks must have the same height: ~A_i=A_j~.

For a valid pair of planks, the capacity is ~A_i\times(j-i)~. Planks between the two chosen walls do not affect the capacity.

Find the maximum capacity of a wholesome trough Kevin can build. If no pair of planks has the same height, output ~-1~.

Input

The first line contains an integer ~N~ (~2 \leq N \leq 2\times10^5~), the number of wooden planks.

The second line contains ~N~ integers ~A_1,A_2,\dots,A_N~ (~1 \leq A_i \leq 10^9~), the heights of the planks from left to right.

Output

Output the maximum capacity of a wholesome trough. If no wholesome trough can be formed, output ~-1~.

Examples

Input 1

5
3 1 4 3 4

Output 1

9

Kevin has two options for forming a wholesome trough:

1. Choose planks ~1~ and ~4~, which both have height ~3~. The capacity is ~3\times(4-1)=9~.
2. Choose planks ~3~ and ~5~, which both have height ~4~. The capacity is ~4\times(5-3)=8~.

Therefore, the maximum capacity is ~9~.

Input 2

4
1 2 3 4

Output 2

-1

All planks have different heights, so Kevin cannot build a wholesome trough.

Input 3

7
5 5 1 5 2 5 1

Output 3

25

Choosing the first and sixth planks produces a trough with capacity ~5\times(6-1)=25~.