D. Цэцэрлэг

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

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

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

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

Цэцэрлэгийн хүүхдүүдийг бүлгүүдэд хувааж байна. Багш хүүхдүүдийг нэг мөрөнд байрлуулсан ба хүүхэд бүрт түүний сэтгэл татам утга хамааралтай. Хүүхэд бүр заавал нэг бүлэгт байх ба бүлэг бүр мөрийн дараалсан хүүхдүүдийн хоосон биш хэсэг байх ёстой. Бүлгийн эвтэй байдал нь бүлгийн хоёр хүүхдийн сэтгэл татам байдлын хамгийн их зөрүү юм (хэрвээ бүлэг нэг хүүхэдтэй бол түүний эвтэй байдал нь тэг байна).

Бүлгүүдийн нийт эвтэй байдал нь хамгийн их байхаар багш хүүхдүүдийг ямар нэг тооны бүлгүүдэд хуваахыг хүссэн. Энэ утгыг олоход түүнд тусал.

Оролт

Эхний мөр нь мөрөн дэх хүүхдүүдийн тоо болох $n$ ($1 ≤ n ≤ 10^{6}$) б тоог агуулна.

Хоёр дахь мөр нь $n$ ширхэг $a_{i}$ бүхэл тоонуудыг агуулна. Энэ нь $i$-р хүүхдийн сэтгэл татам байдал ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$).

Гаралт

Бүх бүлгүүдийн боломжит хамгийн их эвтэй байдлыг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
5
1 2 3 1 2
Гаралт
3
Оролт
3
3 3 3
Гаралт
0

Тэмдэглэл

Эхний жишээний хуваалтын боломжит хувилбаруудаас нэг нь дараах болно: эхний гурван хүүхэдтэй бүлгийн найрсаг байдал нь 2, ба үлдсэн хоёр хүүхэдтэй бүлгийн найрсаг байдал нь 1 байна.

Хоёр дахь жишээнд яаж ч хуваасан ижил үд дүнд хүрэх ба бүлэг бүрийн найрсаг байдал нь 0 байна.

Сэтгэгдлүүдийг ачааллаж байна...