F. Хашаа

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

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

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

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

Вася байшингийнхаа урд талын хашааг будах хэрэгтэй болжээ. Хашаа нь нэг эгнээ $n$ ширхэг модон хавтангуудын дараалал юм. Хавтан бүр нь $1$ см өргөн, тэгш өнцөгт хэлбэртэй байна. Бүгдээрээ хашааны хавтангуудыг зүүнээс баруун тийш нь $1, 2, ..., n$ гэж дугаарлая. $i$-р хавтангийн өндөр нь $h_{i}$ см байна.

Васяд $1$ см өргөнтэй багс, улаан ба ногоон өнгийн будаг байв. Мэдээж будагны хэмжээ хязгаартай. Тиймээс Вася будаг бүрээр будаж болох талбайн хэмжээг гаргажээ. Тэгээд улаан өнгөөр $a$ см.кв-аас илүү, ногоон өнгөөр $b$ см.кв-аас илүү будаж хүрэлцэхгүй болжээ. Хашааны хавтан бүрийг $2$ өнгийн нэгээр нь л будаж болно. Магадгүй Васяд нэг өнгө нь хэрэггүй байж болох юм.

Нэмж хэлэхэд Вася хашаагаа сонирхолтой харагдуулахыг хүсч байгаа. Үүний тулд Васягийн үзэмжгүй байдлын утга гэж нэрлэдэг утгыг хамгийн байга байлгахаар хашааг будах хэрэгтэй. Вася дараалсан хавтангуудыг өөр өнгөөр будах нь үзэмжгүй харагдана гэж үзэж байгаа. Хашааны үзэмжгүй байдлын утга нь өөр өнгөөр будагдсан зэргэлдээ хавтангуудын хоорондох залгаасны уртын нийлбэр байна. Хашааг сайхан харагдуулахын тулд та энэхүү утгыг байж болох хамгийн багаар байлгах хэрэгтэй. Таны даалгавар бол Вася хашаагаа бүхэлд нь будсан үеийн үзэмжгүй байдлын хамгийн бага утгыг олох явдал юм.

Дээрх зураг нь $2$, $3$, $2$, $4$, $3$, $1$ (зүүнээс баруун) өндөр хавтангуудтай хашааг харуулжээ. Эхний болон $5$ дахь хавтангууд улаанаар, бусад нь ногооноор будагдсан байна. Эхний болон $2$ дахь хавтангуудын залгаасны урт нь $2$, $4$ болон $5$ дахь хавтангуудын залгаасны урт $3$, $5$ болон $6$ дахь хавтангуудын залгаасны урт 1 байна. Тиймээс энэхүү будагдсан хашааны үзэмжгүй байдал нь $2+3+1=6$.

Оролт

Эхний мөр нь Васягийн хашааны хавтангуудын тоог харуулах $n$ ($1 ≤ n ≤ 200$) бүхэл тоог агуулна.

$2$ дахь мөр нь улаанаар будаж болох болон ногооноор будаж болох талбайг харуулах $a$ ба $b$ ($0 ≤ a, b ≤ 4 \cdot 10^{4}$) бүхэл тоонуудыг агуулна.

$3$ дахь мөр хашааны хавтангуудын өндрийг харуулах $n$ ширхэг $h_{1}, h_{2}, ..., h_{n}$ $(1 ≤ h_{i} ≤ 200)$ бүхэл тоонуудыг агуулна.

$1$ мөрөнд байгаа тоонууд хоосон зайгаар тусгаарлагдана.

Гаралт

Хашаагаа бүрэн будаж дууссаны дараа Васягийн авч болох үзэмжгүй байдлын хамгийн бага утга болох бүхэл тоог хэвлэ. Боломжгүй бол $-1$ гэж хэвлэ.

Орчуулсан: Солонго

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

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