Піца

Обмеження: 2 сек., 256 МіБ

На бенкет з нагоди півфіналу світу з програмування організатори купили піцу, розділену на \(n\) рівних шматків (як на рисунку). На деяких шматках є оливка, а на деяких — немає.

Ви вже знаєте, як учасники змагань перебирають соком, але ще більше вони перебирають піцою. Не всім учасникам до вподоби оливки, тому організатори бенкету хочуть розділити піцу навпіл таким чином, щоб на одній з половин узагалі не було оливок. І для того, щоб зробити це можливим, вони можуть забирати оливки з деяких шматків піци.

Проте, за правилами етикету, витягувати оливки з піци не дуже культурно, тому організатори просять вас допомогти їм порахувати, яку мінімальну кількість оливок треба забрати, щоб вони могли поділити піцу на дві рівні частини так, щоб одна з них була без оливок.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість шматків піци.

У наступному рядку задано \(n\) чисел \(a_i\). \(a_i = 1\), якщо на \(i\)-му шматку піци є оливка, і 0, якщо немає.

Вихідні дані

В одному рядку виведіть ціле число — мінімальну кількість оливок, які треба забрати.

Обмеження

\(1 \le n \le 10^5\),

\(n\) — парне,

\(0 \le a_i \le 1\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
8 1 0 1 1 0 1 1 1	2

Примітки

Піца з прикладу з оптимальним розрізом