== include(page="template/taskheader" task_id="sandwich") ==

În Ţinutul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o potecă sunt aliniate n ingrediente numerotate de la 1 la n, iar ingredientul i are o valoare de „gust” a[i]. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

În Ţinutul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o potecă sunt aliniate $n$ ingrediente numerotate de la $1$ la $n$, iar ingredientul $i$ are o valoare de „gust” $a[i]$. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

Pentru orice segment continuu de ingrediente a[l], a[l+1], ..., a[r], Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât nici două poziţii alese să nu fie adiacente. Suma gustului acelui subşir este:
a[i1] + a[i2] + ... + a[ik], cu l ≤ i1 < i2 < ... < ik ≤ r şi i_j + 1 < i_{j+1}

Pentru orice segment continuu de ingrediente $a[l], a[l+1], ..., a[r]$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât nici două poziţii alese să nu fie adiacente. Suma gustului acelui subşir este:
$a[i1] + a[i2] + ... + a[ik],  cu  l ≤ i1 < i2 < ... < ik ≤ r  şi  i_j + 1 < i_{j+1}$

Definim f(a[l..r]) = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).

Definim $f(a[l..r])$ = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).

Jake vrea să ştie câtă magie totală poate aduna, dacă ia în calcul toate segmentele posibile ale potecii. Cu alte cuvinte, calculaţi:

S = ∑ f(a[l..r])

$S$ = ∑ $f(a[l..r])$

h2. Date de intrare