"Сур сур, бас дахин сур" — Энэ бол Валерагийн өдөр бүр хийх ёстой зүйл. Тэр математикийг гол чиглэлээ болгосон математикийн сургуульд сурдаг. Математикийн багш нь өөрийн мэргэжилдээ маш хайртай ба үүнийгээ өөрийн сурагчдад түгээхийг хүсдэг. Тийм ч учраас тэр сурагчиддаа хүнд ба их даалгавар өгдөг. Хэдийгээр Валера хамгийн шилдэг сурагчдын нэг ч гэсэн тэрбээр гэрийн даалгавраа сайн зохицуулж чадаагүй. Тийм учраас Валера танаас дараах даалгаврууд дээрээ тусламж хүсчээ.

$n$ ширхэг элемэнттэй тоон дараалал өгөгдсөн. Дарааллын префикс гэдэг нь дарааллын эхлэлээс сонгогдсон хэсэг юм (хоосон байж болно). Дарааллын саффикс гэдэг нь дарааллын төгсгөлөөс сонгогдсон хэсэг (хоосон байж болно). Дараалалд 2 үйлдлийг дэс дараатайгаар хийх боломжтой. Эхний үйлдэл нь ямар нэгэн префикс сонгож аваад бүх тоог нь $-1$-ээр үржүүлэх. Хоёр дахь үйлдэл нь ямар нэгэн саффикс сонгож аваад бүх тоог нь $-1$-ээр үржүүлэх. Сонгогдсон префикс болон саффикс нь огтлолцож болно. Өмнө дурдсан үйлдлүүдийг хийсний дараа үүсэх дарааллын боломжит хамгийн их нийлбэр хэд вэ?

Оролт

Эхний мөр дарааллын элемэнтийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 10^5$) тоог агуулна. Дараагийн мөрөнд дарааллыг илэрхийлэх $n$ ширхэг $a_i$ ($-10^4 ≤ a_i ≤ 10^4$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

Нэг мөрөнд бодлогын хариуг хэвлэ.