C. Үнээ саах

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

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

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

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

Яхаб өвөөгийнхөө фермд тусалдаг. Өнөөдөр тэр үнээ саах ёстой. Зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлагдаж, дараалан зогссон $n$ үнээ байна. Үнээ бүр зүүн эсвэл баруун тийшээ харсан байна. Яхаб үнээг сааж байх үед бүх үнээнүүд түүний одоогийн сааж байгаа үнээрүү хараад айх ба тэд өгж чадах сүүний хэмжээнээсээ нэг нэгжийг алдана. Сааж байгаа үнээ зүүн тийшээ харсан бол түүнээс бага индекстэй бүх үнээ түүнийг хардаг, ба баруун тийшээ харсан бол түүнээс их индекстэй бүх үнээ түүнийг хардаг. Нэг удаа айсан үнээ дахин айж болно (нэгээс илүү нэгж сүү алдаж болно). Нэг удаа саалгасан үнээ айхгүй бөгөөд ямар ч сүү алдахгүй. Нэг үнээ өөрийн өгч чадах бүх сүүг (үнээ хязгааргүй их сүү өгдөг) алддаггүй гэж үзэж болно.

Яхаб үнээнүүдээ дарааллаар саахаар шийдсэн. Гэхдээ үнээ бүрийг яг нэг удаа саах ёстой. Яхаб аль болох бага сүү алдахыг хүсдэг. Алдсан сүүний хамгийн бага хэмжээг хэвлэ.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 200000)$ бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг $a_{1}$, $a_{2}$, ..., $a_{n}$ бүхэл тоонуудыг агуулна, $a_{i}$ нь $0$ бол $i$-р үнээ зүүн тийшээ, $1$ бол баруун тийшээ харсан гэсэн үг.

Гаралт

Нэг бүхэл тоо хэвлэнэ, алдах сүүний хамгийн бага хэмжээ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхний жишээнд Яхаб дараах дарааллаар үнээнүүдийг саана: $3$, $4$, $2$, $1$. $3$-р үнээг сааж байхад, $4$-р үнээ $1$ нэгж сүү алдана. Үүний дараа ямар ч сүү алдахгүй.

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