Піца

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

Constraints

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
8 1 0 1 1 0 1 1 1	2

Notes

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