АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Бороо орох болгонд Фермер Жоны талбай үерт автдаг. Гэсэн хэдий ч, талбай төгс хэлбэртэй биш болохоор жигд бус хэлбэрээр усанд живээд,

усаар тусгаарлагдсан арлуудад хуваагддаг. ФЖ-ы талбай нь N ( 1 ≤ N ≤ 10^5 ) урттай 1 хэмжээст дүрсээр илэрхийлэгддэг.

i-р хэсгийн өндрийг H(i) гээд талбайн 2 талд хязгааргүй өндөртэй хашаагаар хүрээлсэн гэж үзэж болно.

Бороо орох бүрт, хамгийн намхан хэсгээс эхэлж живээд, тус тусдаа хэдэн “арал” үүсгэдэг.

Усны түвшин газрын түвшинтэй тэнцсэн л бол тэр хэсгийг живсэн гэж үзнэ.

Дээр үзүүлсэн жишээнд: зүүн гар талд, 2.5 нэгж устай үед 4 арал ( энэ жишээнд хамгийн олон арал ) үүсгэсэн байна. Цаашлаад, бороо орсоор

7 нэгж устай болоход зөвхөн 2 арал үлдсэнийг харж байна.

Хэрэв та ФЖ-ы талбайн өндрүүдийг мэдэж байгаа бол үерийн үеэр хамгийн ихдээ хэдэн арал үүсэхийг тооцоолно уу.

ОРОЛТ

Эхний мөрөнд талбайн хэсгийн тоо N ( 1 ≤ N ≤ 10^5 ) бүхэл тоо.

Дараагийн N мөр тус бүрт i-р хэсгийн өндөр H(i)  ( 1 ≤ H(i) ≤ 10^9 ) бүхэл тоо өгөгдөнө.

ЖИШЭЭ ОРОЛТ

8

3

5

2

3

1

4

2

3

ГАРАЛТ

Үерийн үеэр үүсч болох хамгийн олон арлын тоог нэг мөрөнд хэвлэж гаргана уу.

ЖИШЭЭ ГАРАЛТ

4

[Brian Dean, 2012]

Орчуулсан : УБ 1-р сургуулийн 12-р ангийн сурагч Б.Мөнх-Оргил