Балансування інверсій#10324
Бессі та Елсі грали з булевим масивом довжини . Оцінка Бессі - це кількість інверсій у першій половині , а оцінка Елсі - кількість інверсій у другій половині . Інверсія - це пара чисел A_i = і A_j = , де < . Наприклад, масив, що складається з блоку , за яким слідує блок , не має інверсій, а масив, що складається з блоку , за яким слідує блок , має інверсій.
Фермер Джон натрапив на ігрове поле, і йому цікаво дізнатися, яку мінімальну кількість перестановок необхідно здійснити між сусідніми елементами, щоб гра виглядала так, ніби це була нічия. Допоможіть фермеру Джону знайти відповідь на це питання.
Перша строка містить ( ≤ ≤ 10^5). Наступна строка містить цілих чисел - нулів та одиниць.
Виведіть найменшу кількість перестановок сусідніх елементів, яку необхідно здійснити для отримання нічиєї.
У цьому прикладі перша половина масиву спочатку має інверсію, а друга половина має інверсії. Після обміну -го та -го бітів обидва підмасиви мають інверсій.
Приклад 1