arany

Egy út mentén van N darab mágikus láda, melyek mindegyike bizonyos mennyiségű aranyat rejt: pontosan gk kilogramm arany van a k-adikban (k=1...N). Ha kivesszük az aranyat valamelyik ládából akkor a közvetlen szomszédos ládák elillannak… A ládák elég messze vannak egymástól, így egyszerre csak egyet tudunk kiüríteni. Maximálisan hány kilogramm aranyat (M) tudunk megszerezni?

Példa

N: 5
arany a ládákban: 3 7 5 4 2
az összes lehetőséget végigpróbálva, látható hogy M=11:

  láda sorszám        arany
     1,3,5            3+5+2
     1,4                3+4
     2,4                7+4 -> max 
     2,5                7+2

A bemenet specifikációja

N
g1 ... gN

Az első sor az 1 ≤ N ≤ 104 számot, a második a 1 ≤ gk ≤ 104 (k=1...N) mennyiségek szóközzel elválasztott listáját tartalmazza.

A kimenet specifikációja

M

Egyetlen sor a keresett M-el.

1. példa bemenet

1. 5
2. 3 7 5 4 2

1. példa kimenet

1. 11

2. példa bemenet

1. 7
2. 1 2 3 3 2 2 1

2. példa kimenet

1. 7