C. Моднууд

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

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

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

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

Бэртауны төв гудамжаар $i$ дугаартай мод $a_i$ ($1 ≤ i ≤ n$) өндөртэй байдаг $n$ мод ургасан байдаг. Бэрландын ерөнхийлөгчийн айлчлалын үеэр моднуудыг тэдний өндөр гоё дараалал үүсгэдэг байхаар өөрчлөхөөр шийдэв. Энэ нь захын моднууд ($1$-р болон $n$-р) тэнцүү өндөртэй, $2$-р болон $n - 1$-р моднууд тэнцүү өндөртэй бөгөөд $1$-р модноос $1$-ээр илүү өндөр байна гэх мэт байрлахыг хэлнэ. Өөрөөр хэлбэл моднуудын өндрүүд нь захаасаа ижил зайтай моднууд (дарааллын төгсгөлөөс) ижил өндөртэй ба зах хүртэлх зай нэгээр өсөхөд уг модны өндөр бас нэгээс өссөн байх ёстой. Жишээлбэл, $2$ $3$ $4$ $5$ $5$ $4$ $3$ $2$ ба $1$ $2$ $3$ $2$ $1$ нь гоё, $1$ $3$ $3$ $1$ ба $1$ $2$ $3$ $1$ нь биш.

Модны өндрийг өөрчлөнө гэдэг Бэрландын эрдэмтдийн нээсэн өндөр технологийг ашиглаж байгаа тул маш үнэтэй үйл ажиллагаа юм. Нэг үйлдэл хийхдээ ямар нэг мод сонгон авч түүнийг өндрийг дурын тоогоор өсгөх юмуу багасгаж болно. Ингэхэд модны өндөр эерэг бүхэл тоо болсон байх ёстой, өөрөөр хэлбэл тэгээс бага буюу тэнцүү өндөртэй байж болохгүй. Өндрүүдийг нь гоё дараалал болгохын тулд хамгийн цөөндөө хэдэн модны өндрийг өөрчлөх шаардлагатайг тодорхойл.

Оролт

Эхний мөр модны тоо болох $n$ ($1 ≤ n ≤ 10^5$) бүхэл тоо агуулна. Хоёрдахь мөр моднуудын өндөр болох $a_i$ ($1 ≤ a_i ≤ 10^5$) тоонуудыг агуулна.

Гаралт

Гоё дараалал болгохын тулд өндрийг нь өөрчлөх шаардлагатай хамгийн цөөн модны тоо болох ганц тоог хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
3
2 2 2
Гаралт
1
Оролт
4
1 2 2 1
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...