B. Антикубизмын пальто

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

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

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

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

Кубизм бол дүрслэх урлагийн нэг чиглэл ба хавтан дээр эзэлхүүн бүхий дүрс байгуулдаг урсгал юм. Ингэж байгуулахдаа урагш төвийсөн мэт харагдах гурван хэмжээст геометрийн дүрсүүдийг ашигладаг.

Таны хөрөг зургийг нь авч үзэх алдартай барималч Кикассо кубизмыг үзэн яддаг. Харин түүнд түүний гайхамшигт барималуудыг ашиглан гурван хэмжээст обьектуудыг хоёр хэмжээст обьектуудруу хөрвүүлэх санаа гүн сэтгэгдэл төрүүлсэн. Ингээд түүний шинэ төсөл энэ санаатай холбогдсон. Кикассо антикубизмын үзэн ядагчдад зориулж пальто хийхийг хүсч байна. Үүнийг хийхийн тулд тэр барималынхаа геометрийн хар зураг буюу гүдгэр олон өнцөгт бүтээхийг хүсч байна.

Кикассо үүндээ зориулж хэд хэдэн бэлдэц буюу бүхэл тоон урттай саваанууд бэлдсэн. Одоо тэр саваануудаа нэгтгэхийг хүсч байна. $i$-р саваа бол $l_{i}$ урттай хэсэг.

Уран барималч тэг биш талбайтай гүдгэр олон өнцөгт хийхээр төлөвлөсөн. Ингэхдээ бүх саваанууд энэ гүдгэр олон өнцөгтийн талууд байна. Саваа бүр өөрийн бүтэн уртаараа ашиглагдах ёстой. Саваануудыг тасдах, хугалах, тахийлгах хориотой. Гэсэн ч хоёр тал хоорондоо дэлгэмэл өнцөг үүсгэж болно.

Кикассо түүний сонгосон урттай саваанууд дуусвал тэг биш талбайтай гүдгэр олон өнцөгт үүсгэх боломжгүй гэдгийг мэднэ. Кикассо хэрэглэгдээгүй саваануудыг орхихыг хүсэхгүй байгаа ба уран барималч түүний асуудал шийдэгдэхүйц болгож бүхэл тоон урттай бэлдэц саваа хийхээр шийдсэн. Мэдээж тэр үүнийгээ боломжит хамгийн богино байлгахыг хүсч байна учир нь материалууд маш үнэтэй ба хэрэггүй зүйлд мөнгөө үрэх нь зохисгүй хэрэг билээ.

Уран барималчид туслана уу!

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($3 ≤ n ≤ 10^{5}$) байх ба бэлдэц саваануудын тоо байна.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $l_{i}$ ($1 ≤ l_{i} ≤ 10^{9}$) байх ба Кикассод байгаа саваануудын урт байна. Кикассод байгаа саваануудаар $n$ оройтой тэг биш талбайтай олон өнцөгт үүсгэх боломжгүй байна.

Гаралт

Нэг ширхэг бүхэл тоон утга хэвлэх ба савааны хамгийн бага урт байна. Энэ савааг нэмснээр бүх саваагаар $(n + 1)$ оройтой, тэг биш талбайтай гүдгэр олон өнцөгт үүсгэх боломжтой болох юм.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3
1 2 1
Гаралт
1
Оролт
5
20 4 3 2 1
Гаралт
11

Тэмдэглэл

Эхний жишээн дээр ${1, 1, 1, 2}$ уртуудтай бүрдлээр ${1 + 1 = 2, 2, 1}$ талуудтай гурвалжин бүтээж болно.

Хоёр дахь жишээ дээр та ${20, 11, 4 + 3 + 2 + 1 = 10}$ уртуудтай гурвалжин үүсгэж болно.

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