űrhajó

A vogon űrhajóknak különös sebességszabályozó rendszere van: rengeteg egyforma nyomógomb egy sorban, mindegyiken egy-egy számmal s1,...,sN. A működés a következő: először a kormányos törli a jelenlegi beállításokat (ekkor minden gomb KI állásba kerül), majd kiválasztja a nyomógombok egy folytonos sorozatát: si,si+1,...,sj, (i≤j) ezeket BE állásba állítja. Végső lépésként megnyomja a fő-gombot. Ezzel a (néha elég hosszadalmas) ceremóniával azt éri el, hogy az űrhajó felgyorsít vagy lelassít a

(j-i+1)*min({si,...,sj}) formulával adott sebességre. Feladatod: kiszámolni a hajó által elérhető maximális sebességet (M)!

Példa

    N: 4
    A gombokhoz tartozó sebességek sorban: 4,1,2,3
    Az osszes esetet végigpróbálva, látható hogy a maximális sebesség 4:

        i,j    v
        --------
        1,1 -> 4
        1,2 -> 2
        1,3 -> 3
        1,4 -> 4
        2,2 -> 1
        2,3 -> 2
        2,4 -> 3
        3,3 -> 2
        3,4 -> 4
        4,4 -> 3

A bemenet specifikációja

 
N
s1 ... sN

Az első sor a gombok 1 ≤ N ≤ 105 száma, A második sorban szóközzel elválasztva, az 1 ≤ sk ≤ 109 (k=1...N) számok vannak.

A kimenet specifikációja

M

Egy sor az elérhető maximális M sebességgel.

1. példa bemenet

1. 4
2. 4 1 2 3

letöltés szöveges állományként

1. példa kimenet

1. 4

letöltés szöveges állományként

2. példa bemenet

1. 4
2. 3 2 2 1

letöltés szöveges állományként

2. példa kimenet

1. 6

letöltés szöveges állományként