C. Илья ба саваанууд

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

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

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

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

Тэмцээний дараах орой Ильяд маш уйтгартай байлаа. Тэр өөрт нь $n$ ширхэг саваануудын олонлог болон багаж хэрэгсэл байгааг саналаа. Саваа бүр $l_{i}$ урттай байна.

Илья эдгээр саваануудаар нийт талбай нь хамгийн их байх тэгш өнцөгт хийхээр шийджээ. Саваа бүр хамгийн ихдээ нэг тэгш өнцөгт хийхэд л ашиглагдах бөгөөд ашиглагдахгүй байж ч болох юм. Савааг дундуур нь нугалж болохгүй гэдгийг санаарай.

Хэрвээ дараах шинж чанарыг хангадаг бол $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$ урттай саваануудаар тэгш өнцөгт хийж болно:

  • $a_{1} ≤ a_{2} ≤ a_{3} ≤ a_{4}$
  • $a_{1} = a_{2}$
  • $a_{3} = a_{4}$

Жишээлбэл $3, 3, 3, 3$ мөн $2, 2, 4, 4$ урттай саваануудаар тэгш өнцөгт хийж болно. Харин $5, 5, 5, 7$ урттай саваануудаар тэгш өнцөгт хийж болохгүй.

Мөн Ильяд саваануудын уртыг багасгадаг багаж байгаа. Саваанууд тусгай материалаар хийгдсэн тул саваа бүрийн уртыг хамгийн ихдээ нэгээр л багасгаж чадна. Жишээлбэл $5$ урттай савааг энэ хэвээр нь үлдээж болно эсвэл савааны уртыг $4$ болгож өөрчилнө.

Байгаа саваануудаар тэгш өнцөгт хийх боломжтой бол Илья тэгш өнцөгтийн хамгийн их нийт талбайн хэмжээг мэдэхийг хүссэн. Та асуултанд хариулж чадах уу?

Оролт

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

Оролтын хоёр дахь мөрөнд $n$ ширхэг $l_{i}$ ($2 ≤ l_{i} ≤ 10^{6}$) эерэг бүхэл тоонууд байна. Эдгээр нь саваа тус бүрийн урт юм.

Гаралт

Сөрөг биш бүхэл тоо агуулсан нэг мөр хэвлэх ёстой. Энэ нь Илья байгаа саваануудаараа хийж болох тэгш өнцөгтийн хамгийн их нийт талбай юм.

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

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

Оролт
4
2 4 4 2
Гаралт
8
Оролт
4
2 2 3 5
Гаралт
0
Оролт
4
100003 100004 100005 100006
Гаралт
10000800015
Сэтгэгдлүүдийг ачааллаж байна...