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

Poveste si cerinta...

Zaharel a devenit pasionat de expresii aritmetice. A scris un sir de $N$ numere intregi pe o foaie de hartie si se intreaba care este expresia de valoare maxima pe care o poate forma cu aceste numere. El va construi o expresie respectand urmatoarele restrictii:
 
# Ordinea in care apar numerele in sir este aceeasi cu ordinea in care vor aparea in expresie.
# Se pot folosi paranteze rotunde si operatorii $+$, $-$, $*$ care vor reprezenta operatiile de adunare, scadere si inmultire. Se considera ca $+$ si $-$ au aceeasi prioritate, iar $*$ are cea mai mare prioritate.
# Operatorii trebuie inserati inaintea oricarui element din sir (mai putin inaintea primului element unde, dupa necesitati, poate fi introdus doar operatorul $-$), dar nu este permisa inserarea a doi operatori inaintea aceluiasi element.
# Parantezele pot fi aplicate oriunde, respectand conditia ca expresia rezultata sa fie corecta din punct de vedere matematic.
 
h2. Cerinta
 
Scrieti un program pentru Zaharel care sa determine valoarea maxima a unei expresii pe care o poate construi cu cele $N$ numere din sir.

h2. Date de intrare

...

Fisierul de intrare $emax.in$ contine pe prima linie numarul natural $N$. Pe cea de a doua linie se afla $N$ numere intregi separate prin cate un spatiu reprezentand valorile din sir.

h2. Date de iesire

...

Fisierul de iesire $emax.out$ va contine un singur numar intreg reprezentand valoarea maxima a unei expresii care se poate construi cu cele $N$ numere din sir, modulo $666013$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* Valorile din sir sunt numere intregi din intervalul $[-100, 100]$

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 4
 -1 1 -9 6 | 108 |

h3. Explicatie

...

$(-1 - 1) * (-9) * 6 = 108$

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