Олонлог Эгзэ сургуулийн нэг ангийн сурагчид нэг эгнээнд суужээ.
Сурагч бүр тодорхой өндөртэй.

Багш нь дараах сонирхолтой даалгаврыг өглөө:

• Эгнэн суурсан ангийн сурагчдыг дараалсан хэсгүүдэд (subarray) хувааж үз.

Хэсэг бүрийн хувьд:

• тухайн хэсэг дэх хамгийн намхан сурагчийг олно
• Эдгээр бүх хэсгүүдийн "хамгийн намхан сурагчдын" өндрийн нийлбэрийг ол.

Оролт:

• Эхний мөрөнд бүхэл тоо n — сурагчдын тоо
• Дараагийн мөрөнд n ширхэг бүхэл тоо h[i] — сурагч бүрийн өндөр

Гаралт:

• Нэг бүхэл тоо хэвлэнэ
• Бүх боломжит дараалсан хэсгүүдийн хамгийн намхан сурагчдын өндрийн нийлбэр

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

• 1 ≤ n ≤ 2 × 10^5
• 1 ≤ h[i] ≤ 10^9

Дэд бодлого

Жишээ:

Оролт-1

4
3 1 2 4

Гаралт-1

17

Тайлбар-1

Боломжит бүх сурагчдын хэсгүүд:

• [3] → хамгийн намхан = 3
• [3,1] → 1
• [3,1,2] → 1
• [3,1,2,4] → 1
• [1] → 1
• [1,2] → 1
• [1,2,4] → 1
• [2] → 2
• [2,4] → 2
• [4] → 4

? Нийлбэр = 17

Оролт-2

3
5 5 5

Гаралт-2

30

Тайлбар-2

Бүх сурагч ижил өндөртэй тул бүх хэсэгт minimum = 5

Нийт хэсгийн тоо:

3 × (3 + 1) / 2 = 6

? Нийлбэр = 5 × 6 = 30