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 666013.
Restricţii
1 ≤ N ≤ 100 000
Valorile din şir sunt numere întregi din intervalul [-100,100]