B. Баавгай ба шоо

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

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

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

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

Хөгшин баавгай Лимак шоонуудаас бүтсэн цамхаг нурааж тоглохоор болов. Тэрээр $n$ ширхэг баганан цамхаг барьжээ. $i$ дэх цамхаг $h_{i}$ өндөртэй. Жишээ зургийг харна уу.

Лимак шоонуудыг дуустал дараах үйлдлийг давтан хийнэ.

Хэрэв шооны дээд, доод, баруун, зүүн гэсэн дөрвөн тал бүрт шоо эсвэл шал байвал уг шоог дотоод шоо гэнэ. Бусад шоог гадаргуун шоо гэнэ. Лимак нэг үйлдлээр бүх гадаргуун шоог устгана. Түүний сарвуу их хүчтэй тул бүх гадаргуун шоог нэг дор устгадаг байна.

Лимак эхлэхэд бэлэн болжээ. Чиний даалгавар бол бүх цамхгийг устгахын тулд хэчнээн үйлдэл хийхийг олох юм.

Оролт

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

Хоёр дахь мөрөнд цамхгуудын өндрүүдийг илэрхийлэх $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{9})$ гэсэн $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан байна.

Гаралт

Бүх цамхгийг устгахын тулд хэчнээн үйлдэл хийхийг хэвлэ.

Орчуулсан: Бат-Од

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

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

Тэмдэглэл

Эхний жишээнд хийгдэх үйлдлүүдийг доорх зурагт харуулав. Гадаргуун шоонууд улаанаар будагдсан байна.

Эхний үйлдэл хийгдсэний дараа дөрвөн шоо үлдсэн. Хоёр дахь үйлдлийн дараа ганц шоо үлдсэн. Сүүлийн шоог нэг үйлдлээр устгана.

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