e-olymp
Competitions

Ukrainian Olympiad in Informatics, II Stage, I Round

D. Козак Вус та масив

Нещодавно Козак Вус знайшов масив $a$ з $n$ елементів, який складається лише з нулів та одиниць. Козаку стало цікаво: за яку мінімальну кількість перестановок сусідніх елементів масиву можна його відсортувати. \InputFile Перший рядок містить одне ціле число $n$ ($1 \le n \le 10^6$)~--- довжина масиву $a$. Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$)~--- масив $a$. \OutputFile Виведіть одне ціле число~--- відповідь на задачу. \Scoring Якщо рішення працює правильно при $n \le 1\,000$, то воно буде оцінюватися принаймні у $35$ балів.
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
1 1 0
Output example #1
2
Input example #2
7
1 0 1 1 0 1 0
Output example #2
8
Input example #3
8
1 1 0 0 1 1 0 0
Output example #3
12
Source Ukrainian Olympiad in Informatics 2021, II Stage, I Round