Reklama na płocie

Limit czasu: 1s | Limit pamięci: 64MB

Ogrodzenie składa się z $n$ pionowych desek. Szerokość każdej deski wynosi 1, a ich wysokość może się różnić. Chcesz przymocować do płotu prostokątną reklamę. Jaka jest maksymalna powierzchnia takiej reklamy?

Wejście

Pierwszy wiersz wejścia zawiera liczbę naturalną $n$, szerokość ogrodzenia. Drugi wiersz zawiera $n$ liczb całkowitych $h_i$, wysokości kolejnych desek ogrodzenia.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara jedną liczbę całkowitą, maksymalną powierzchnię reklamy.

Ograniczenia

• $1 \le n \le 2 \cdot 10^5$
• $1 \le h_i \le 10^9$

Przykłady

Wejście 1

8
4 1 5 3 3 2 4 1

Wyjście 1

10