C. Сул тал ба Хомсдол

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

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

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

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

Танд $n$ ширхэг элементтэй $a_{1}, a_{2}, ..., a_{n}$ дараалал өгөгдсөн.

Дарааллын сул тал болсон $a_{1} - x, a_{2} - x, ..., a_{n} - x$ байх $x$ бодит тоог хамгийн бага байхаар тодорхойл.

Дарааллын сул тал нь дарааллын бүх сегментийн (үргэлжилсэн дэд дараалал) хомсдолын хамгийн их утгаар тодорхойлогдоно.

Сегментийн хомсдол нь сегментийн бүх элементийн нийлбэрийн абсолют утга.

Оролт

Эхний мөрөнд дарааллын урт болох $n$ ($1 ≤ n ≤ 200 000$) тоо.

Хоёр дах мөрөнд $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ ($|a_{i}| ≤ 10 000$) тоонууд.

Гаралт

Хамгийн бага байж болох $a_{1} - x, a_{2} - x, ..., a_{n} - x$-ын сул тал болох бодит тоо. Таны хариулт хариунаас $10^{ - 6}$-аас бага утгаар зөрвөл зөвд тооцогдоно.

Орчуулсан: Ц.Баттулга

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

Оролт
3
1 2 3
Гаралт
1.000000000000000
Оролт
4
1 2 3 4
Гаралт
2.000000000000000
Оролт
10
1 10 2 9 3 8 4 7 5 6
Гаралт
4.500000000000000

Тэмдэглэл

Эхний тохиолдолд, $x$-ын хамгийн ашигтай утга нь $2$ ба дараалал $ - 1$, $0$, $1$ болно, эндээс хамгийн их сул талтай сегментүүд "-1" эсвэл "1" болно. Сул талын тоон утга (хариу) энэ тохиололд $1$-тэй тэнцүү.

Хоёрдох жишээн дээр $x$-ын хамгийн ашигтай утга нь $2.5$ ба дараалал $ - 1.5,  - 0.5, 0.5, 1.5$ болно, эндээс хамгийн их сул талтай сегментүүд "-1.5 -0.5" эсвэл "0.5 1.5". Сул талын тоон утга (хариу) энэ тохиололд $2$-тэй тэнцүү.

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