sortLined

Nhóm của Hải có n bạn nữ ký hiệu là 0 và n bạn nam ký hiệu là 1.

Tất cả đã xếp lại một hàng ngang, tuy nhiên Hải muốn các bạn nam và nữ phải đứng xen kẽ nhau (không có hai bạn nào cùng giới đứng cạnh nhau).

Mỗi lần hoán đổi Hải được phép đổi chỗ 2 bạn bất kỳ, hỏi Hải cần phải dùng ít nhất mấy lần hoán đổi để các bạn sắp xếp theo yêu cầu.

Ví dụ:

Với a = [1,1,0,0] thì sortLined(a) = 1.
Giải thích:
Hải chỉ cần đổi chỗ 1 lần ở 2 vị trí là a[1] và a[2].
Với a = [1,0,0,1,1,0] thì sortLined(a) = 1.

Đầu vào/Đầu ra:

[Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
[Đầu vào] Array: integer: a
1 ≤ a.size() ≤ 10⁶.
0 ≤ a[i] ≤ 1.
[Đầu ra] Integer
Số lần di chuyển ít nhất để các bạn được sắp xếp xen kẽ.