C. Таамгаар үүссэн гайхамшигт нийлбэр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

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

Оролт

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

Гаралт

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

Орчуулсан: Хонгор

Жишээ тэстүүд

Оролт
3
-1 -2 -3
Гаралт
6
Оролт
5
-4 2 0 5 0
Гаралт
11
Оролт
5
-1 10 -5 10 -2
Гаралт
18
Сэтгэгдлүүдийг ачааллаж байна...