Байшингууд тойрог хэлбэртэй байрласан.

Эхний ба сүүлийн байшин хөрш гэж тооцогдоно.

Хөрш байшинг зэрэг сонгохгүйгээр хамгийн их мөнгө ол.

Оролт:

Эхний мөр: Байшингийн тоо n

Хоёрдахь мөрөнд a[i] (байшин бүрд байрлах мөнгөний хэмжээ) болох тоонууд хоосон зайгаар тусгаарлан өгөгдөнө.

Гаралт:

Гаралтын файлд авч болох хамгийн их мөнгөн дүн

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

• \(1 ≤ n ≤ 10^5\)
• \(0 ≤ a[i] ≤ 10^4\)

Дэд бодлого

Жишээ:

Оролт-1

3
2 3 2

Гаралт-1

3

Оролт-2

4
1 2 3 1

Гаралт-2

4