Бэрландын Их Сургууль $256$ жилийн ойгоо тэмдэглэхээр зэхэж байна. Дэд захирал их сургуулийн хотхоныг чимэглэхээр шийдэж, хотхоны төв хэсэгт $n$ ширхэг мөсөн хөшөөг босгожээ. Хөшөөнүүд нь бие биенээсээ ижил хэмжээтэй байхаар тойрог хэлбэрээр байрласан бөгөөд эдгээр нь нийлээд $n$ өнцөгт үүсгэж байв. Мөн хөшөөнүүдийг цагийн зүүний дагуу $1$-ээс $n$ хүртэл дугаарлажээ.

Хөшөө болгоныг сэтгэл татам байдлаар нь үнэлсэн бөгөөд хөшөө тус бүр $t_{i}$ үнэлгээ авчээ. $t_{i}$ нь эерэг, сөрөг, эсвэл $0$ байх боломжтой.

Их сургуулийн захирал чимэглэлтийг шалгахаар ирээд "Хараахан төгс болоогүй байна. Зарим хөшөөг хайлуулах хэрэгтэй" гэжээ. Дараах дүрмээр хөшөөг хайлуулна:

• Үлдэж буй хөшөө зөв олон өнцөгт үүсгэх ($3$-аас $n$ хүртэл олон өнцөгт байх боломжтой).
• Үлдсэн хөшөөний үнэлгээнүүдийн $t_{i}$ нийлбэр хамгийн их байх.

Дэд захиралд энэ даалгаварыг биелүүлэхэд туслана уу. Нэг ч хөшөөг хайлуулахгүй байж болно. Хөшөө байрнаасаа хөдлөхгүй.

Оролт

Эхний мөрөнд анхны хөшөөнүүдийн тоо бүхэл тоо $n$ ($3 ≤ n ≤ 20000$). Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($-1000 ≤ t_{i} ≤ 1000$) хоосон зайгаар тусгаарлагдан өгөгдөнө. Үүнд $t_{i}$ нь $i$ дэхь хөшөөний үнэлгээ.

Гаралт

Гарч болох хамгийн их үнэлгээний нийлбэрийг хэвлэнэ.

Эхний жишээн дээр хоёр дахь хөшөө болгоныг үлдээж бусдыг нь хайлуулна. Өөрөөр хэлвэл $2$, $4$, $5$, $3$ гэсэн үнэлгээтэй хөшөөнүүдийг үлдээнэ.