C. Далайн эрэг дээр өнгөрүүлсэн өдөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг өдөр Стюарт, Спонжбоб болон Патрик нар далайн эрэгрүү явахаар шийдсэн. Харамсалтай нь цаг агаар муу байсан учраас найзууд далайн давалгаан дээр гулгах боломжгүй байсан. Гэсэн хэдий ч тэд цагаа элсэн цамхагууд хийн өнгөрүүлэхээр шийдсэн.

Өдрийн төгсгөлд тэд $n$ цамхаг барьсан байсан. Цамхагууд $1$-c $n$ хүртэл дугаарлагдсан ба $i$-р цамхагийн өндөр нь $h_{i}$-тэй тэнцүү. Найзууд явах гэж байсан ба Стюарт цамхагууд өөрсдийн өндрөөрөө эрэмбэлэгдээгүй ба тиймхэн харагдаж байгааг анзаарсан. Одоо найзууд $1$-c $n - 1$ хүртэлх бүх $i$-ийн хувьд $h_{i} ≤ h_{i + 1}$ нөхцөлийг хангахаар цамхагуудыг дахин эрэмбэлэх гэж байна.

Стюарт цамхагуудыг эрэмбэлэхдээ дараах үйл явцыг дагахыг санал болгосон:

  • Цамхагуудыг дараалласан цамхагуудын групп болох блокуудад хуваана. $i$-c $j$ хүртэлх блок нь $i, i + 1, ..., j$ цамхагуудыг багтаана. Блок нь нэг цамхагаас тогтож болно.
  • Хуваалт нь цамхаг бүр зөвхөн нэг блокын хэсэг байх замаар хийгдэнэ.
  • Блок бүр бусад блокоос үл хамааран эрэмбэлэгдэх буюу $h_{i}, h_{i + 1}, ..., h_{j}$ дараалал эрэмбэлэгдэнэ.
  • Хуваалт нь блок бүр эрэмбэлэгдсэний дараа $h_{i}$ дараалал дараалал эрэмбэлэгдэх нөхцөлийг хангах ёстой.

Хуваалтанд байгаа блокуудын тоо ихсэх тусам эрэмбэлэх үйл ажиллагааг хялбаршуулна гэдгийг Патрик ойлгосон. Одоо найзууд дээрх бүх нөхцөлийг хангах хуваалтад хамгийн ихдээ хэдэн боломжит хэдэн блок байх вэ гэдгийг танаас асууж байна.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх ба Спонжбоб, Патрик болон Стюартын өдрийн турш хийсэн элсэн цамхагуудын тоо.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоон утга $h_{i}$ ($1 ≤ h_{i} ≤ 10^{9}$) байна. Эдгээр тоонуудын $i$-р тоо бүр $i$-р цамхагийн өндөртэй харгалзана.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3
1 2 3
Гаралт
3
Оролт
4
2 1 3 2
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр хуваалт нь дараах байдалтай харагдана: [1][2][3].

Хоёр дахь жишээн дээр хуваалт нь дараах байдалтай харагдана: [2, 1][3, 2]

Сэтгэгдлүүдийг ачааллаж байна...