D. 3 хүнээс 2-т нь үйлчлэх

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

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

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

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

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

Кассчин (өөрөөр хэлбэл үйлчлүүлэгчтэй тооцоо хийгч) хүртэл $n$ ширхэг хүн оочирлосон байна гэж үзье. Уг оочирт зогсох хүн болгон нь эерэг бүхэл тоо $a_{i}$-аар тодорхойлогдох бөгөөд энэ нь тухайн хүний кассчин дээр очоод үйлчлүүлэх хугацааг илэрхийлэх юм. Жинхэнэ кассчин нь юугаараа онцгой вэ гэвэл тэрээр нэгэн зэрэг 2 үйлчлүүлэгчид үйлчилж чадах ажээ. Тэгсэн хэдий ч хэрэв 2 үйлчлүүлэгч нь $a_{i}$ болон $a_{j}$ гэсэн хугацаануудад үйлчлүүлэх хэрэгтэй байвал эдгээр үйлчлүүлэгч нарт үйлчлэх хугацаа нь $max(a_{i}, a_{j})$-тай тэнцүү байх юм. Үйлчлүүлэгч нарт үйлчилнэ гэдэг нь тасралтгүй үргэлжлэх үйл явц гэдгийг анхаарна уу. Түүнчлэн хэрэв 2 хүн нэгэн зэрэг кассчин дээр үйлчлүүлэхээр ирвэл тэд нэгэн зэрэг үйлчлүүлж эхлэх бөгөөд нэгэн зэрэг үйлчлүүлж дуусна (тэдгээр үйлчлүүлэгчдийн аль нэг нь хүлээх хэрэг гарах боломжтой юм).

Хэрэв уг оочирт нэгээс олон тооны хүн хүлээн зогсож байвал Вася өөрийн алгоритмаа ухаалгаар ашиглах ба ингэхдээ оочирын хамгийн урд зогсож буй 3-н хүний аль нэг 2 хүнд нь нэгэн зэрэг үйлчлэх юм. Хэрэв оочирт зөвхөн $i$ дугаартай нэг үйлчлүүлэгч зогсож байвал тэрээр шууд кассчин дээр очих бөгөөд $a_{i}$ хугацаанд үйлчлүүлнэ. Үйлчлүүлэгч нарт үйлчлэх нийт үе шатны (өөрөөр хэлбэл үйлчлүүлэгчид үйлчлэх тоо) тоо нь үргэлж $⌈n / 2⌉$-той тэнцүү байна.

Вася уг арга нь бидний үзэн яддаг оочирлох үйл явдлыг хөнгөвчилнө хэмээн бодож байгаа юм. Тиймээс Вася таныг уг алгоритмыг ашиглан бүх үйлчлүүлэгч нарт үйлчилж дуусах хүртэлх хамгийн бага хугацааг тодорхойлох программ бичиж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд уг оочирт байх хүмүүсийг тоог илэрхийлэх $n$ ($1 ≤ n ≤ 1000$) тоо өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{6}$)-ууд өгөгдөнө. Хүмүүс нь кассчин дээр байгаа хүнээс эхлэн оочирын төгсгөл хүртэл дугаарлагдсан байна.

Гаралт

Эхний мөрөнд бүх $n$ ширхэг хүнд үйлчлэх хамгийн бага хугацааг хэвлэнэ. Дараа нь $⌈n / 2⌉$ мөрөнд үйлчлүүлэгчдийн үйлчлүүлэх дарааллыг хэвлэнэ үү. Мөр болгон нь (сүүлийн мөр нь магадгүй нэг тоо агуулж болно) зайгаар тусгаарлагдсан заавал 2 ширхэг тоог агуулах ба эдгээр нь тухай үе шатанд үйлчлүүлэх үйлчлүүлэгчдийн дугааруудыг илэрхийлнэ. Хэрэв $n$ нь сондгой тоо байвал эдгээр мөрүүдийн хамгийн сүүлийн мөрөнд нэг тоо хэвлэх бөгөөд энэ оочирын хамгийн сүүлд үйлчлүүлэх үйлчлүүлэгчийн дугаарыг илэрхийлэх юм. Үйлчлүүлэгчид нь $1$-ээс эхлэн дугаарлагдсан байна гэж үзнэ үү.

Орчуулсан: Баатархүү

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

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