În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o masă sunt aliniate $N$ ingrediente numerotate de la $1$ la $N$, iar ingredientul $i$ are o valoare de „gust” $a{~i~}$.

Pentru orice subsecvenţă 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 să nu existe două poziţii adiacente alese. Gustul total acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~2~} < ... < i{~k~} ≤ r$ şi $i{~j~} + 1 < i{~j+1~}$ pentru orice $1 ≤ j < k$.
 
Definim <tex> f(a[l..r]) </tex> = gustul total maxim posibil pentru un astfel de subşir.

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 să nu existe două poziţii adiacente alese. Gustul total acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l &le; i{~1~} &lt; i{~2~} &lt; ... &lt; i{~k~} &le; r$ şi $i{~j~} + 1 &lt; i{~j+1~}$ pentru orice $1 &le; j &lt; k$. Definim <tex> f(a[l..r]) </tex> = gustul total maxim posibil pentru un astfel de subşir.

Jake vrea să ştie suma celor mai gustoase sandwichuri pe care le poate face, dacă ia în calcul toate subsecvenţele posibile ale mesei. Cu alte cuvinte, calculaţi:

|_. #  |_. Punctaj |_. Restricţii |
| 1 | 4 | $N ≤ 15$ |

| 2 | 11 | $N ≤ 500$ |
| 3 | 13 | $N ≤ 2000$ |
| 5 | 9 | $N ≤ 200 000$ şi $z = 2$|

| 2 | 16 | $N ≤ 500$ |
| 3 | 15 | $N ≤ 2000$ |
| 5 | 10 | $N ≤ 200 000$ şi $z = 2$|

| 5 | 41 | $N ≤ 200 000$ |

| 6 | 22 | $N ≤ 5 000 000$ |

| 6 | 14 | $N ≤ 5 000 000$ |

h2. Exemplu
table(example). |_. sandwich.in |_. sandwich.out |

| 4 3 1 6 5
| 50

| 4
5 1 1 5
| 20

|
h3. Explicaţie

$a = [5, 4, 1, 4]$
 
$f(a[1..1]) = 5$
$f(a[1..2]) = 5$
$f(a[1..3]) = 6$
$f(a[1..4]) = 9$
$f(a[2..2]) = 4$
$f(a[2..3]) = 4$
$f(a[2..4]) = 8$
$f(a[3..3]) = 1$
$f(a[3..4]) = 4$
$f(a[4..4]) = 4$
 
$S = 50$

...

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