Ганаа, Галаа хоёр сургуулийнхаа оюутнуудын N багийг программчлалын тэмцээнд бэлтгэж байна. Тэд тус бүрдээ чухал алгоритмуудыг баг бүрд заах ёстой. Мэдээжээр тэд хоёулаа нэг багтай зэрэг ажиллах боломжгүй ба мөн тэдний хэн нь ч олон багтай нэгэн зэрэг ажиллах боломжгүй.

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

Оролт:

Оролтын эхний мөрөнд багийн тоо болох N бүхэл тоо байна. Дараагийн мөрөнд зайгаар тусгаарлагдсан N бүхэл тоо байх бөгөөд і дүгээр бүхэл тоо нь і дүгээр багийн алгоритмыг ойлгож бас хэрэгжүүлэхэд шаардагдах хугацааг илэрхийлнэ. Оролтын бүх өгөгдөл \([1, 10^{18} ]\) интервалд байх болно.

Гаралт:

Гаралтын ганц мөрөнд шийд болох утгыг бичсэн байна.

Хязгаарлалтууд:

• \(N<10^6\)
• Оролтын бүх өгөгдөл [\(1, 10^{18}\)] интервалд байх болно.

Дэд бодлого

Жишээ:

Оролт-1

3
2 2 2

Гаралт-1

6

Оролт-2

3
4 1 2

Гаралт-2

8

Оролт-3

4
1 3 2 1

Гаралт-3

7

Эхний жишээний тайлбар:

Баг бүрд алгоритмыг ойлгож хэрэгжүүлэхэд 2 нэгж хугацаа хэрэгтэй. Тиймээс боломжит хуваариудыг нэг нь Ганаа 1-р баг, 2-р баг, 3-р багуудад, Галаа 3-р баг, 1-р баг, 2-р багт тус тус хичээл орж болно.

Хоёр дахь жишээний тайлбар:

Оновчтой хуваарийн нэг нь Ганаа 2-р баг, 3-р баг, 1-р багт тус тус хичээлээ заах ба харин 3-р баг болон 1-р багийн хичээлийн хооронд 1 нэгж хугацааны завсарлага авна. Харин Галаа багуудад 1, 3 болон 2 гэсэн дарааллаар хичээлээ зааж болно.