C. Мөнгө шилжүүлэлт

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

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

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

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

Вася-ын амьдардаг хотод $n$ ширхэг банк байдаг ажээ. Тэдгээр нь нэг тойрог дээр байрлах бөгөөд хэрэв дугааруудынх нь зөрүү $1$-ээс ихгүй байвал тэдгээр 2 банк нь хөрш банкнууд байхаар байрласан байв. Түүнчлэн $1$-р банк болон $n$-р банк нь хэрэв $n > 1$ бол хөрш банкнууд байх юм. Ямар ч банк нь өөртөө хөрш биш байна.

Вася банк болгонд нэг данстай. Дансны үлдэгдэл нь сөрөг тоо байж болох бөгөөд энэ нь Вася уг банканд өртэй гэсэн үг юм.

Уг бодлогод зөвхөн нэг үйлдэл зөвшөөрөгдсөн байв: та ямар ч банкнаас хэсэг хэмжээний мөнгийг аль нэгэн хөрш банканд байх данс уруу шилжүүлж болно. Уг үйлдлийн хувьд шилжүүлж буй мөнгөний нийт дүнгийн хэмжээ болон дансны үлдэгдэлд хязгаар байхгүй гэж үзнэ.

Вася их тоо бодох дургүй учраас таныг түүнд туслан банк болгонд байх түүний данснуудын үлдэгдлүүдийг 0-тэй тэнцүү болгоход шаардагдах хамгийн бага үйлдлийн тоог тодорхойлж өгөхийг хүсжээ. Мөн ингэх боломжтой нь баттай бөгөөд өөрөөр хэлбэл бүх банкнуудад байх Вася-ын данснуудын үлдэгдлүүдийн нийлбэр нь 0-тэй тэнцүү юм.

Оролт

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

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{i}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$)-ууд өгөгдөх ба эдгээрийн $i$-дахь нь $i$-дахь банканд байх дансны анхны үлдэгдлийг илэрхийлнэ. Бүх $a_{i}$-уудын нийлбэр нь $0$-тэй тэнцүү байна.

Гаралт

Банк болгонд байх данснуудын үлдэгдлүүдийг 0-тэй тэнцүү болгоход шаардагдах хамгийн бага үйлдлийн тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3
5 0 -5
Гаралт
1
Оролт
4
-1 0 1 0
Гаралт
2
Оролт
4
1 2 3 -6
Гаралт
3

Тэмдэглэл

Эхний жишээнд Вася 1-р банкнаас 3-р банк уруу $5$-ыг шилжүүлнэ.

2-дахь жишээнд Вася эхлээд 3-р банкнаас 2-р банк уруу $1$-ыг шилжүүлнэ. Дараа нь 2-р банкнаас 1-р банк уруу $1$-ыг шилжүүлнэ.

3-дахь жишээний оновчтой хариулт нь дараах үйлдлүүдээр дүрслэгдэнэ:

  1. 1-р банкнаас 2-р банк уруу $1$-ыг шилжүүлнэ;
  2. 2-р банкнаас 3-р банк уруу $3$-ыг шилжүүлнэ;
  3. 3-р банкнаас 4-р банк уруу $6$-ыг шилжүүлнэ.
Сэтгэгдлүүдийг ачааллаж байна...