D. Дурсгалт байшин

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

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

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

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

Бидэнд $n+2$ ширхэг баганатай хуучин дурсгалт байшин байна. Эдгээр багананууд таазыг түшдэг. Эдгээр баганануудын координатууд нь $0 = x_{0} < x_{1} < ... < x_{n} < x_{n + 1}$. Хамгийн зүүн болон баруун талын багананууд нь онцгой бөгөөд тэднийг тулгуур багана гэдэг. Харин бусад багана нь энгийн.

Бид багана болгоны даац $d_{i}$-ыг мэднэ. Нэгэн координат $x$-тэй энгийн баганыг авч үзье. Хэрвээ түүнд хамгийн ойрхон зүүн талын багана нь $a$ (энгийн эсвэл тулгуур аль нь ч байж болно), хамгийн ойрхон баруун талын багана нь $b$ (энгийн эсвэл тулгуур аль нь ч байж болно) гэвэл багана $x$ нь таазны цэгээс цэг хүртэл хэсгийг түшнэ. Хэрвээ энэхүү түшиж буй хэсгийн урт нь баганы даац $d_{i}$-ээс их байвал хэсэг хугацааны дараа энэ багана нурна. Үүний дараагаар энэ таазны хэсэг нь хөрш 2 баганад адил дүрмээр шинээр хувиарлагдана.

Тиймээс энгийн багананууд нь нурсаар аль нэг мөчид зогсох нь гарцаагүй. Энд баганануудын хэрхэн үлдэх нь баганануудын нурах дараалалтай хамаарахгүй гэдэг нь харагдаж байна. Хэрвээ эцэст нь зөвхөн 2 тулгуур багана үлдвэл энэхүү дурсгалт байшинг нурсан гэж тооцно. Харин 2 тулгуур баганаас гадна дор хаяж 1 багана үлдвэл тухайн байшинг нураагүй гэж тооцно.

Барилгыг нурахгүй байлгах үүднээс бид дурын $d'$ даацтай баганыг $0 < x' < x_{n + 1}$ координатуудын хооронд дурын координатад (бүхэл тооны координат байх албагүй) байрлуулж болно. Хэрвээ энэ координатад багана байрлаж байвал тухайн баганыг шинэчлэн оронд нь $d'$ даацтай багана тавина гэсэн үг.

Таны даалгавар бол барилга нурахгүй байхаар шинээр нэмэх багананы хамгийн бага даацыг олох юм.

Оролт

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

2 дахь мөрөнд баганануудын координатууд болох $n+2$ ширхэг бүхэл тоонууд $x_{0}, x_{1}, ..., x_{n}, x_{n + 1}$ ($x_{0} = 0$, $x_{i} < x_{i + 1}$, $0 ≤ i ≤ n$, $x_{n + 1} ≤ 10^{9}$) өгөгдөнө.

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

Гаралт

Барилга нурахгүй байхаар шинээр нэмэх багананы хамгийн бага даац болох нэг тоог хэвлэнэ үү. Хэрвээ та багана нэмэх шаардлагагүй бол $0$ гэж хэвлэнэ үү. Таны хариултыг $10^{ - 4}$ үнэмлэхүй болон харьцангуй алдааны дотор шалгана.

Орчуулсан: Энхлут

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

Оролт
2
0 20 40 100
15 40
Гаралт
10
Оролт
3
0 4 10 28 30
9 13 5
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...