Олонлог Эгзэ сургуулийн сурагчид барилгын блокуудаар туршилт хийж байна.

Тэд дараалан байрласан n ширхэг багана (column) барьжээ.
Багана бүрийн өргөн нь 1 нэгж, харин өндөр нь өөр өөр байна.

? Та эдгээр багануудыг ашиглан хамгийн их талбайтай тэгш өнцөгт үүсгэх ёстой.

• Тэгш өнцөгт нь дараалсан (contiguous) багануудыг хамарна
• Тэгш өнцөгтийн өндөр нь сонгосон баганууд дундах хамгийн намхан баганын өндөртэй тэнцүү байна

? Хамгийн их боломжит талбайг ол.

Оролт:

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

Гаралт:

• Нэг бүхэл тоо хэвлэнэ
• Хамгийн их боломжит тэгш өнцөгтийн талбай

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

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

Дэд бодлого

Жишээ:

Оролт-1

6
2 1 5 6 2 3

Гаралт-1

10

Тайлбар-1

• 5 ба 6 өндөртэй багануудыг сонговол:
  • өргөн = 2
  • өндөр = 5
    → талбай = 5 × 2 = 10

Оролт-2

5
1 2 3 4 5

Гаралт-2

9

Тайлбар-2

• 3, 4, 5 баганууд:
  • өндөр = 3
  • өргөн = 3
    → талбай = 9