emax

Zăhărel a devenit pasionat de expresii aritmetice. A scris un şir de $N$ numere întregi pe o foaie de hârtie şi se întreabă care este expresia de valoare maximă pe care o poate forma cu aceste numere. El va construi o expresie respectând următoarele restricţii:

1. Ordinea în care apar numerele în şir este aceeaşi cu ordinea în care vor apărea în expresie.
2. Se pot folosi paranteze rotunde şi operatorii +, -, * care vor reprezenta operaţiile de adunare, scădere şi înmulţire. Se consideră că + şi - au aceeaşi prioritate, iar * are cea mai mare prioritate.
3. Operatorii trebuie inseraţi înaintea oricărui element din şir (mai putin înaintea primului element unde, după necesităţi, poate fi introdus doar operatorul -), dar nu este permisă inserarea a doi operatori înaintea aceluiaşi element.
4. Parantezele pot fi aplicate oriunde, respectând condiţia ca expresia rezultată să fie corectă din punct de vedere matematic.

Cerinţă

Scrieţi un program pentru Zăhărel care să determine valoarea maximă a unei expresii pe care o poate construi cu cele $N$ numere din şir.

Date de intrare

Fişierul de intrare emax.in conţine pe prima linie numărul natural $N$. Pe cea de a doua linie se află $N$ numere întregi separate prin câte un spaţiu reprezentând valorile din şir.

Date de ieșire

Fişierul de ieşire emax.out va conţine un singur număr întreg reprezentând valoarea maximă a unei expresii care se poate construi cu cele $N$ numere din şir, modulo $666 \ 013$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• Valorile din şir sunt numere întregi din intervalul $[-100,100]$

Exemplu

emax.in

4
-1 1 -9 6

emax.out

108

Explicație

$(-1-1) \cdot (-9) \cdot 6 = 108$