A. Хамгийн бага бартаа

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

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

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

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

Майк хаданд авирах оролдлого хийж байгаа боловч үүнээс жаахан эмээж байна.

Ханан дээр $i$-р бариул нь газраас дээш $a_{i}$ өндөрт байрласан $n$ ширхэг бариул байгаа. Түүнийг $1$-ээс $n - 1$ хүртэлх бүх $i$-н хувьд $a_{i} < a_{i + 1}$ байх $a_{i}$ дараалал гэж үзье; Бид ийм дарааллыг зам гэж нэрлэх болно. Майк $a_{1}$, ..., $a_{n}$ зам нь $d = max(a_{i+1} - a_{i})$ бартаатай гэж бодож байгаа. Өөрөөр хэлбэл хамгийн их өндрийн зөрүүтэй зэргэлдээх хоёр бариулны хоорондох зай нь бартаатай тэнцүү юм.

Өнөөдөр Майк $a_{1}$, ..., $a_{n}$ өндрүүдэд бэхлэгдсэн бариултай замаар авирахаар шийджээ. Илүү хүнд болгохын тулд Майк нэг бариулыг хасахаар болсон бөгөөд энэ нь дарааллын нэг элементийг устгана гэсэн үг (жишээлбэл $(1, 2, 3, 4, 5)$ дарааллаас гуравдугаар элементийг устгавал бид $(1, 2, 4, 5)$ гэсэн дараалалтай болно). Гэхдээ Майк авирахаас айж байгаа учраас бариул хасах боломжит бүх хувилбарууд дундаас үүсэх бартааг (өөрөөр хэлбэл нэг бариул хассаны дараах зэргэлдээх бариулнуудын хоорондох хамгийн их өндрийн зөрүүг) аль болох бага байлгахыг хүсэж байгаа. Эхний ба сүүлийн бариулнууд байрандаа байх ёстой.

Нэг бариул хассаны дараах замын хамгийн бага бартааг тодорхойлоход Майкд тусал.

Оролт

Эхний мөр нь бариулнуудын тоо болох нэг бүхэл $n$ ($3 ≤ n ≤ 100$) тоог агуулна.

Дараагийн мөр нь зайгаар тусгаарлагдсан $n$ ширхэг $a_{i}$ ($1 ≤ a_{i} ≤ 1000$) бүхэл тоонуудыг агуулна. $i$-р бариул $a_{i}$ өндөрт байна. Мөн $a_{i}$ өсөх дараалал байна (өөрөөр хэлбэл эхний элементээс бусад элемент бүр нь өмнөх элементээсээ заавал их байна).

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь нэг бариул хассаны дараах замын хамгийн бага бартаа юм.

Орчуулсан: Даариймаа

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

Оролт
3
1 4 6
Гаралт
5
Оролт
5
1 2 3 4 5
Гаралт
2
Оролт
5
1 2 3 7 8
Гаралт
4

Тэмдэглэл

Эхний жишээнд та хоёр дахь бариулыг л хасаж чадах ба үүний дараа дараалал $(1, 6)$ болно. Иймээс хөрш элементүүдийн хамгийг их зөрүү 5 байна.

Хоёр дахь жишээнд дурын бариулыг хассаны дараах бартаа 2 байна.

Гурав дахь жишээнд та $(1, 3, 7, 8)$, $(1, 2, 7, 8)$, $(1, 2, 3, 8)$ дарааллуудыг гарган авч чадах ба тэдгээрийн бартаа нь харгалзан $4$, $5$, $5$ байна. Тиймээс хоёр дахь элементийг устгах нь оновчтой ба хариу $4$ байна.

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