CSES - Lauta-aita
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Lauta-aita muodostuu nn laudasta. Jokaisen laudan leveys on 1, mutta korkeudet vaihtelevat.

Haluat kiinnittää aitaan suorakulmion muotoisen mainoksen, jonka pinta-alan tulisi olla mahdollisimman suuri. Mainos ei saa mennä missään kohtaa aidan ulkopuolelle.

Kuinka suuren mainoksen voit kiinnittää?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: lautojen määrä.

Seuraavalla rivillä on nn kokonaislukua k1,k2,,knk_1,k_2,\ldots,k_n: kunkin laudan korkeus.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mainoksen pinta-ala.

Rajat

  • 1n1051 \le n \le 10^5
  • 1ki1091 \le k_i \le 10^9

Esimerkki

Syöte:

8
4 1 5 3 3 2 4 1

Tuloste:

10