Given an array of 0s and 1s, we need to write a program to find the minimum number of swaps required to group all 1s present in the array together.
Example 1:
Input : arr[ ] = {1, 0, 1, 0, 1}
Output : 1
Explanation:
Only 1 swap is required to group all 1's together. 
Swapping index 1 and 4 will give arr[] = {1, 1, 1, 0, 0}.
Example 2:
Input : arr[ ] = {1, 0, 1, 0, 1, 1} 
Output :  1
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function minSwaps() that takes an array (arr), sizeOfArray (n) and return the minimum number of swaps required and if no 1's are present print -1. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N  ≤ 10^{5}
0 ≤ Arr_{i} ≤ 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def minSwaps (self, arr, n) : 

        #Complete the function

Solutions:
class Solution:

	def minSwaps(self, A, N):
		K = 0
		for i in range(N):
			K += A[i]
		if K == 0:
			return -1
		if K == N:
			return 0
		mxones = 0
		for i in range(K):
			mxones += A[i]
		c = mxones
		i = 0
		j = K
		while j < N:
			c += A[j]
			c -= A[i]
			mxones = max(mxones, c)
			j += 1
			i += 1
		return K - mxones


class Solution:

	def minSwaps(self, arr, n):
		num_ones = arr.count(1)
		if num_ones == 0:
			return -1
		curr_ones = 0
		window_size = num_ones
		for i in range(window_size):
			curr_ones += arr[i]
		max_ones = curr_ones
		for i in range(window_size, n):
			curr_ones += arr[i] - arr[i - window_size]
			max_ones = max(max_ones, curr_ones)
		return num_ones - max_ones


class Solution:

	def minSwaps(self, arr, n):
		ones_count = arr.count(1)
		if ones_count == 0:
			return -1
		start = 0
		end = 0
		min_zeros = len(arr)
		zeros_count = 0
		while end < len(arr):
			if arr[end] == 0:
				zeros_count += 1
			if end - start + 1 > ones_count:
				if arr[start] == 0:
					zeros_count -= 1
				start += 1
			if end - start + 1 == ones_count:
				min_zeros = min(min_zeros, zeros_count)
			end += 1
		return min_zeros


class Solution:

	def minSwaps(self, arr, n):
		c = arr.count(1)
		if c == 0:
			return -1
		mx = 0
		t = arr[0:c].count(1)
		for i in range(0, n - c):
			if t > mx:
				mx = t
			if arr[i] == 1:
				t -= 1
			if arr[i + c] == 1:
				t += 1
		if t > mx:
			mx = t
		return c - mx


class Solution:

	def minSwaps(self, arr, n):
		k = arr.count(1)
		if k == 0:
			return -1
		s = arr[:k].count(1)
		res = k - s
		for i in range(k, n):
			s += arr[i] - arr[i - k]
			res = min(res, k - s)
		return res


class Solution:

	def minSwaps(self, arr, n):
		window = sum(arr)
		if window == 0:
			return -1
		if window == 1 or window == n:
			return 0
		min_swaps = n
		(l, r) = (0, window - 1)
		ones = sum(arr[:window - 1])
		while r < n:
			ones += arr[r]
			min_swaps = min(min_swaps, window - ones)
			ones -= arr[l]
			l += 1
			r += 1
		return min_swaps


class Solution:

	def minSwaps(self, arr, n):
		totalcount = 0
		for i in range(n):
			totalcount += arr[i]
		if totalcount == 0:
			return -1
		currcount = 0
		maxcount = 0
		i = 0
		j = 0
		while j < n:
			currcount += arr[j]
			if j - i + 1 == totalcount:
				maxcount = max(maxcount, currcount)
				if arr[i] == 1:
					currcount -= 1
				i += 1
			j += 1
		return totalcount - maxcount


class Solution:

	def minSwaps(self, arr, n):
		count = 0
		for i in range(n):
			if arr[i] == 1:
				count += 1
		currOnes = 0
		maxOnes = 0
		if len(arr) == 1:
			if arr[0] == 0:
				return -1
			else:
				return 0
		i = 0
		if count == 0:
			return -1
		for i in range(count):
			if arr[i] == 1:
				currOnes += 1
		maxOnes = max(maxOnes, currOnes)
		for i in range(count, len(arr)):
			if arr[i] == 1:
				currOnes += 1
			if arr[i - count] == 1:
				currOnes -= 1
			maxOnes = max(maxOnes, currOnes)
		return count - maxOnes


class Solution:

	def minSwaps(self, arr, n):
		k = 0
		for i in range(n):
			if arr[i] == 1:
				k += 1
		if k == 0:
			return -1
		(ctr, i, mini) = (0, 0, n)
		j = 0
		while j < len(arr):
			if j - i + 1 <= k:
				if arr[j] == 0:
					ctr += 1
				j += 1
			if j - i + 1 > k:
				mini = min(ctr, mini)
				if arr[i] == 0:
					ctr -= 1
				i += 1
		return mini


class Solution:

	def minSwaps(self, a, n):
		n1 = sum(a)
		if n1 == 0:
			return -1
		i = 0
		j = n1
		x = sum(a[i:j])
		ans = n1 - x
		while j < len(a):
			x -= a[i]
			x += a[j]
			i += 1
			j += 1
			ans = min(ans, n1 - x)
		return ans


class Solution:

	def minSwaps(self, arr, n):
		k = 0
		for ele in arr:
			if ele == 1:
				k += 1
		ws = 0
		zeros = 0
		ones = 0
		res = 0
		sol = -1
		for i in range(len(arr)):
			if arr[i] == 0:
				zeros += 1
			else:
				ones += 1
			if i - ws + 1 >= k:
				if ones > res:
					res = ones
					sol = zeros
				f_num = arr[ws]
				if f_num == 0:
					zeros -= 1
				else:
					ones -= 1
				ws += 1
		return sol


class Solution:

	def minSwaps(self, nums, n):
		no_ones = nums.count(1)
		if no_ones == 0:
			return -1
		curr_ones = nums[:no_ones].count(1)
		max_ones = curr_ones
		for i in range(no_ones, n):
			curr_ones += nums[i] - nums[i - no_ones]
			max_ones = max(max_ones, curr_ones)
		return no_ones - max_ones


class Solution:

	def minSwaps(self, arr, n):
		total_ones = arr.count(1)
		(temp_ones, max_ones) = (arr[:total_ones].count(1), 0)
		max_ones = temp_ones
		for i in range(total_ones, n):
			if arr[i] == 1:
				temp_ones += 1
			if arr[i - total_ones] == 1:
				temp_ones -= 1
			max_ones = max(max_ones, temp_ones)
		return total_ones - max_ones if total_ones > 0 else -1


class Solution:

	def minSwaps(self, arr, n):
		count = 0
		for i in range(n):
			count += arr[i]
		if count == 0:
			return -1
		curr = 0
		start = 0
		end = count
		maxi = 0
		for i in range(count):
			curr += arr[i]
		maxi = max(maxi, curr)
		while end < n:
			curr += arr[end]
			curr -= arr[start]
			maxi = max(maxi, curr)
			start += 1
			end += 1
		return count - maxi


class Solution:

	def minSwaps(self, arr, n):
		one_count = 0
		for ele in arr:
			one_count += 1 if ele == 1 else 0
		max_len = 0
		for r in range(one_count):
			max_len += 1 if arr[r] == 1 else 0
		l = 0
		s = 0
		e = max_len - 1
		ans = max_len
		for r in range(one_count, len(arr)):
			if arr[r] == 1:
				max_len += 1
			max_len -= 1 if arr[l] == 1 else 0
			l += 1
			ans = max(max_len, ans)
		return one_count - ans if one_count != 0 else -1


class Solution:

	def minSwaps(self, arr, n):
		totalNoOfOnes = 0
		for e in arr:
			if e == 1:
				totalNoOfOnes = totalNoOfOnes + 1
		if totalNoOfOnes == 0:
			return -1
		currNoOfOnes = 0
		st = 0
		end = totalNoOfOnes
		currNoOfOnes = 0
		minSwaps = n
		for i in range(st, end):
			if arr[i] == 1:
				currNoOfOnes = currNoOfOnes + 1
		minSwaps = min(minSwaps, totalNoOfOnes - currNoOfOnes)
		while end < n:
			if arr[st] == 1:
				currNoOfOnes = currNoOfOnes - 1
			if arr[end] == 1:
				currNoOfOnes = currNoOfOnes + 1
			end = end + 1
			st = st + 1
			minSwaps = min(minSwaps, totalNoOfOnes - currNoOfOnes)
		return minSwaps


class Solution:

	def minSwaps(self, arr, n):
		a = sum(arr)
		i = j = 0
		minn = float('inf')
		b = 0
		while j < n:
			if arr[j] == 0:
				b += 1
			if j - i + 1 == a:
				minn = min(minn, b)
				if arr[i] == 0:
					b -= 1
				i += 1
			j += 1
		return minn if minn != float('inf') else -1


import sys

class Solution:

	def get_ones(self, arr, n):
		ones = 0
		for num in arr:
			if num == 1:
				ones += 1
		return ones

	def minSwaps(self, arr, n):
		n_ones = self.get_ones(arr, n)
		if n_ones == 0:
			return -1
		n_zeros = 0
		min_swap = sys.maxsize
		for i in range(n_ones):
			if not arr[i]:
				n_zeros += 1
		min_swap = n_zeros
		for i in range(n_ones, n):
			if not arr[i]:
				n_zeros += 1
			if not arr[i - n_ones]:
				n_zeros -= 1
			min_swap = min(min_swap, n_zeros)
		return min_swap


def minSwaps(arr, n):
	if len(set(arr)) == 1 and arr[0] == 0:
		return -1
	numberOfOnes = 0
	for i in range(0, n):
		if arr[i] == 1:
			numberOfOnes = numberOfOnes + 1
	x = numberOfOnes
	count_ones = 0
	maxOnes = 0
	for i in range(0, x):
		if arr[i] == 1:
			count_ones = count_ones + 1
	maxOnes = count_ones
	for i in range(1, n - x + 1):
		if arr[i - 1] == 1:
			count_ones = count_ones - 1
		if arr[i + x - 1] == 1:
			count_ones = count_ones + 1
		if maxOnes < count_ones:
			maxOnes = count_ones
	numberOfZeroes = x - maxOnes
	return numberOfZeroes


def minSwaps(arr, n):
	ones = 0
	for i in range(n):
		if arr[i] == 1:
			ones += 1
	if ones == n:
		return 0
	if ones == 0:
		return -1
	zeroes = 0
	for i in range(ones):
		if arr[i] == 0:
			zeroes += 1
	start = 0
	end = ones - 1
	min_swaps = float('inf')
	while end < n:
		min_swaps = min(min_swaps, zeroes)
		if arr[start] == 0:
			zeroes -= 1
		start += 1
		end += 1
		if end < n and arr[end] == 0:
			zeroes += 1
	return min_swaps


def minSwaps(arr, n):
	c = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			c += 1
	if c == 0:
		return -1
	res = c
	c1 = 0
	for i in range(c):
		if arr[i] == 0:
			c1 += 1
	mini = c1
	for i in range(c, len(arr)):
		if arr[i - c] == 0:
			c1 -= 1
		if arr[i] == 0:
			c1 += 1
		mini = min(mini, c1)
	return mini


def minSwaps(arr, n):
	k = arr.count(1)
	we = 0
	ws = 0
	zeros = 0
	mini = 1000000000000000000000000
	if k == 0:
		return -1
	while we < n:
		if arr[we] == 0:
			zeros += 1
		if we - ws + 1 == k:
			mini = min(mini, zeros)
			if arr[ws] == 0:
				zeros -= 1
			ws += 1
		we += 1
	return mini


def minSwaps(arr, n):
	even_count = 0
	for v in arr:
		if v == 1:
			even_count += 1
	if even_count == 0:
		return -1
	accumulate = [0]
	sum_ = 0
	for (i, v) in enumerate(arr):
		if v == 1:
			sum_ += 1
		accumulate.append(sum_)
	max_ = 0
	for i in range(even_count, len(arr) + 1):
		even_number = accumulate[i] - accumulate[i - even_count]
		if even_number > max_:
			max_ = even_number
	return even_count - max_


def minSwaps(arr, n):
	windowSize = arr.count(1)
	windowCnt = arr[:windowSize].count(0)
	res = windowCnt
	if windowSize == 0:
		return -1
	for i in range(windowSize, len(arr)):
		if arr[i] == 0:
			windowCnt += 1
		if arr[i - windowSize] == 0:
			windowCnt -= 1
		res = min(res, windowCnt)
	return res


def minSwaps(arr, n):
	mn = float('inf')
	ctr = arr.count(1)
	ctr2 = arr[0:ctr].count(0)
	mn = ctr2
	if ctr == 0:
		return -1
	for i in range(ctr, n):
		if arr[i] == 0:
			ctr2 += 1
		if arr[i - ctr] == 0:
			ctr2 -= 1
		mn = min(mn, ctr2)
	return mn


def minSwaps(arr, n):
	c = 0
	for ix in arr:
		if ix == 1:
			c += 1
	b = c
	i = 0
	a = 0
	ans = -1
	j = 0
	su = 0
	while i < len(arr):
		su += arr[i]
		i += 1
		if i == c:
			ans = max(su, ans)
			su -= arr[j]
			j += 1
			c += 1
	if ans == -1:
		return -1
	return b - ans


def minSwaps(arr, n):
	if len(arr) == 1:
		if arr[0] == 0:
			return -1
		else:
			return 0
	ones = 0
	for i in arr:
		if i == 1:
			ones += 1
	if ones == 0:
		return -1
	elif ones == 1:
		return 0
	(i, j) = (0, 0)
	count = 0
	swaps = 99999999
	while i < len(arr) and j < len(arr):
		while j < len(arr) and j - i < ones:
			if arr[j] == 1:
				count += 1
			j += 1
		if j - i == ones:
			swaps = min(swaps, ones - count)
		if arr[i] == 1:
			count -= 1
		i += 1
	return swaps


def minSwaps(arr, n):
	c1 = 0
	for i in range(n):
		c1 += arr[i]
	if c1 == 0:
		return -1
	t = c1
	c2 = 0
	for i in range(t):
		if arr[i] == 1:
			c2 += 1
	m = 0
	m = c2
	for i in range(1, n - t + 1):
		if arr[i - 1] == 1:
			c2 -= 1
		if arr[i + t - 1] == 1:
			c2 += 1
		m = max(m, c2)
	return t - m


def minSwaps(arr, n):
	count_1 = 0
	current_swap = 0
	for element in arr:
		if element == 1:
			count_1 += 1
	if count_1 == 0:
		return -1
	left_idx = 0
	right_idx = count_1 - 1
	for ele in arr[left_idx:right_idx + 1]:
		if ele == 0:
			current_swap += 1
	min_swap = current_swap
	left_idx += 1
	right_idx += 1
	while right_idx < n:
		if arr[left_idx - 1] == 0:
			current_swap -= 1
		if arr[right_idx] == 0:
			current_swap += 1
		if current_swap < min_swap:
			min_swap = current_swap
		left_idx += 1
		right_idx += 1
	return min_swap


def minSwaps(arr, n):
	count_ones = 0
	for i in range(n):
		if arr[i] == 1:
			count_ones += 1
	if n - count_ones == n:
		return -1
	pref_sum = [0] * n
	if arr[0] == 1:
		pref_sum[0] = 1
	for i in range(1, n):
		pref_sum[i] = pref_sum[i - 1] + arr[i]
	subarr_len = count_ones
	max_ones = pref_sum[subarr_len - 1]
	for i in range(subarr_len, n):
		curr_sum = pref_sum[i] - pref_sum[i - subarr_len]
		if curr_sum > max_ones:
			max_ones = curr_sum
	ans = subarr_len - max_ones
	return ans


def minSwaps(arr, n):
	end = 0
	start = 0
	count1 = 0
	m = 0
	f = arr.count(1)
	if f == 0:
		return -1
	for i in range(len(arr)):
		if i >= f:
			if arr[end] == 1:
				count1 += 1
			if arr[start] == 1:
				count1 -= 1
			if count1 > m:
				m = count1
			start += 1
			end += 1
		else:
			if arr[end] == 1:
				count1 += 1
			if count1 > m:
				m = count1
			end += 1
	return f - m


def minSwaps(arr, n):
	window = sum(arr)
	if not window:
		return -1
	i = j = 0
	(curr, maxone) = (0, 0)
	while j < n:
		curr += arr[j]
		if j - i + 1 == window:
			maxone = max(maxone, curr)
			curr -= arr[i]
			i += 1
		j += 1
	return window - maxone


def minSwaps(arr, n):
	if arr.count(1) == 1:
		return 0
	if arr.count(1) == 0:
		return -1
	else:
		cnt = arr.count(1)
		sumi = 0
		ans = 9999999
		for i in range(cnt):
			sumi += arr[i]
		j = cnt
		ans = min(ans, cnt - sumi)
		i = 0
		sumi -= arr[i]
		i += 1
		while j < n:
			sumi += arr[j]
			ans = min(ans, cnt - sumi)
			sumi -= arr[i]
			i += 1
			j += 1
		return ans


def minSwaps(nums, length):
	ct = 0
	for num in nums:
		ct += 1 if num else 0
	if ct == 0:
		return -1
	length = len(nums)
	(st, res) = (0, 0)
	cur = 0
	for end in range(length):
		if nums[end] == 1:
			cur += 1
		if end - st + 1 == ct:
			res = max(cur, res)
			if nums[st] == 1:
				cur -= 1
			st += 1
	return ct - res


def minSwaps(arr, n):
	ct = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			ct += 1
	mxo = 0
	if ct == 0:
		return -1
	for j in range(ct):
		if arr[j] == 1:
			mxo += 1
	co = mxo
	for j in range(1, n - ct + 1):
		if arr[j - 1] == 1:
			co -= 1
		if arr[ct + j - 1] == 1:
			co += 1
		mxo = max(mxo, co)
	return ct - mxo


def minSwaps(arr, n):
	cnt = 0
	for i in arr:
		if i == 1:
			cnt += 1
	if cnt == 0:
		return -1
	t = 0
	for i in range(cnt):
		if arr[i] == 0:
			t += 1
	left = 0
	right = cnt
	ans = t
	while right < n:
		t += 1 - arr[right]
		t -= 1 - arr[left]
		right += 1
		left += 1
		ans = min(ans, t)
	return ans


def minSwaps(arr, n):
	k = arr.count(1)
	ones = 0
	ans = -1
	for i in range(k):
		if arr[i] == 1:
			ones += 1
	ans = ones
	start = 0
	for end in range(k, n):
		if arr[start] == 1:
			ones -= 1
		if arr[end] == 1:
			ones += 1
		ans = max(ans, ones)
		start += 1
	if ans == 0:
		return -1
	return k - ans


def minSwaps(arr, n):
	k = 0
	for i in range(n):
		if arr[i]:
			k += 1
	if k == 0:
		return -1
	maxx = -float('inf')
	curr = 0
	for i in range(n):
		if i < k:
			if arr[i]:
				curr += 1
		else:
			maxx = max(maxx, curr)
			if arr[i]:
				curr += 1
			if arr[i - k]:
				curr -= 1
	maxx = max(maxx, curr)
	return k - maxx


def minSwaps(arr, n):
	k = sum(arr)
	left = 0
	s = 0
	ans = 0
	for i in range(n):
		s += arr[i]
		if i - left + 1 > k:
			if arr[left] == 1:
				s -= arr[left]
			left += 1
		if i - left + 1 == k:
			ans = max(s, ans)
	if k == 0:
		return -1
	return k - ans


from collections import deque

def minSwaps(arr, n):
	if n == 1 and arr[0] == 0:
		return -1
	count = arr.count(1)
	if count == 0:
		return -1
	czeros = 0
	for i in range(count):
		if arr[i] == 0:
			czeros += 1
	ans = czeros
	for i in range(count, n):
		if arr[i] == 0:
			czeros += 1
		if arr[i - count] == 0:
			czeros -= 1
		ans = min(ans, czeros)
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = minSwaps(arr, n)
	print(ans)


def minSwaps(arr, n):
	k = arr.count(1)
	if k == 0:
		return -1
	prefix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = prefix[i - 1] + arr[i]
	sm = prefix[k - 1]
	for i in range(1, n - k + 1):
		sum = prefix[i + k - 1] - prefix[i - 1]
		if sum > sm:
			sm = sum
	return k - sm
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = minSwaps(arr, n)
	print(ans)


def minSwaps(arr, n):
	count = 0
	for i in arr:
		if i == 1:
			count += 1
	if count == 0:
		return -1
	if count == 1:
		return 0
	hm = {}
	if arr[0] == 1:
		hm[0] = 1
	else:
		hm[0] = 0
	for i in range(1, n):
		if arr[i] == 1:
			hm[i] = hm[i - 1] + 1
		else:
			hm[i] = hm[i - 1]
	ma = hm[count - 1]
	for i in range(count, n):
		ma = max(ma, hm[i] - hm[i - count])
	return count - ma


def minSwaps(arr, n):
	ws = arr.count(1)
	if ws == 0:
		return -1
	p = q = ones = 0
	maxdiff = ws
	t1 = ws - 1
	lmin = min
	while q < n:
		ones += arr[q]
		if q - p > t1:
			ones -= arr[p]
			p += 1
		maxdiff = lmin(maxdiff, ws - ones)
		q += 1
	return maxdiff


def minSwaps(arr, n):
	i = j = 0
	one = zero = 0
	maxOne = 0
	minSwap = 0
	k = 0
	for l in range(n):
		if arr[l] == 1:
			k += 1
	if k == 0:
		return -1
	while j < n:
		if arr[j] == 1:
			one += 1
		elif arr[j] == 0:
			zero += 1
		if j - i + 1 < k:
			j += 1
		elif j - i + 1 == k:
			if one > maxOne:
				maxOne = one
			if arr[i] == 1:
				one -= 1
			elif arr[i] == 0:
				zero -= 1
			j += 1
			i += 1
	return k - maxOne


def minSwaps(arr, n):
	x = sum(arr)
	if x == 0:
		return -1
	(i, j) = (0, 0)
	max_ones = 0
	curr = 0
	while j < x:
		curr += arr[j]
		j += 1
	max_ones = curr
	while j < n:
		curr -= arr[i]
		curr += arr[j]
		i += 1
		j += 1
		max_ones = max(curr, max_ones)
	return x - max_ones


def minSwaps(nums, length):
	count = 0
	for i in range(length):
		if nums[i] == 1:
			count += 1
	if count == 0:
		return -1
	st = 0
	(max_one, cur) = (0, 0)
	for end in range(length):
		if nums[end] == 1:
			cur += 1
		if end - st + 1 == count:
			max_one = max(cur, max_one)
			if nums[st] == 1:
				cur -= 1
			st += 1
	return count - max_one


def minSwaps(arr, n):
	numOfOnes = 0
	for num in arr:
		numOfOnes += num
	if numOfOnes == 0:
		return -1
	i = j = 0
	currOnes = 0
	maxOnes = 0
	while j < n:
		currOnes += arr[j]
		if j - i + 1 == numOfOnes:
			maxOnes = max(maxOnes, currOnes)
			if arr[i] == 1:
				currOnes -= 1
			i += 1
		j += 1
	return numOfOnes - maxOnes


def minSwaps(arr, n):
	count = 0
	for i in range(n):
		if arr[i] == 1:
			count += 1
	if count == 0:
		return -1
	(currCount, maxCount) = (0, 0)
	for i in range(count):
		if arr[i] == 1:
			currCount += 1
	maxCount = currCount
	for i in range(1, n - count + 1):
		if arr[i - 1] == 1:
			currCount -= 1
		if arr[i + count - 1] == 1:
			currCount += 1
		if currCount > maxCount:
			maxCount = currCount
	return count - maxCount


def minSwaps(arr, n):
	nums = arr
	wlen = 0
	for n in nums:
		wlen += 1 if n == 1 else 0
	if not wlen:
		return -1
	count = [0] * 2
	(res, l) = (len(nums), 0)
	for i in range(len(nums)):
		count[nums[i]] += 1
		if i >= wlen - 1:
			res = min(count[0], res)
			count[nums[l]] -= 1
			l += 1
	return res


def minSwaps(arr, n):
	ones = 0
	for num in arr:
		if num == 1:
			ones += 1
	if ones == 0:
		return -1
	(i, j) = (0, ones - 1)
	tempOnes = 0
	maxx = 0
	for k in range(i, ones):
		if arr[k] == 1:
			tempOnes += 1
	maxx = max(maxx, tempOnes)
	i += 1
	j += 1
	while i < n and j < n:
		if arr[i - 1] == 1:
			tempOnes -= 1
		if arr[j] == 1:
			tempOnes += 1
		i += 1
		j += 1
		maxx = max(maxx, tempOnes)
	return ones - maxx


def minSwaps(arr, n):
	count = 0
	for i in range(n):
		if arr[i] == 1:
			count = count + 1
	if count == 0:
		return -1
	i = 0
	j = 0
	swapcount = 0
	ans = 0
	while i < count:
		if arr[i] == 0:
			swapcount = swapcount + 1
		i = i + 1
	ans = swapcount
	while i < n:
		if arr[j] == 0:
			swapcount = swapcount - 1
		if arr[i] == 0:
			swapcount = swapcount + 1
		ans = min(ans, swapcount)
		i = i + 1
		j = j + 1
	return ans


def minSwaps(arr, n):
	c1 = arr.count(1)
	if c1 == 0:
		return -1
	i = 0
	j = 0
	ans = n
	o1 = 0
	while j < n:
		if arr[j] == 1:
			o1 += 1
		if j - i + 1 == c1:
			ans = min(ans, c1 - o1)
			if arr[i] == 1:
				o1 -= 1
			i += 1
		j += 1
	return ans


from math import inf

def minSwaps(arr, n):
	total_ones = sum(arr)
	if total_ones == 0:
		return -1
	min_swaps = inf
	curr_swaps = 0
	j = 0
	for i in range(n):
		if arr[i] == 0:
			curr_swaps += 1
		if i >= total_ones - 1:
			min_swaps = min(min_swaps, curr_swaps)
			if arr[j] == 0:
				curr_swaps -= 1
			j += 1
	return min_swaps


def minSwaps(arr, n):
	zeroes = [0]
	for i in range(1, n + 1):
		if arr[i - 1] == 0:
			zeroes.append(1 + zeroes[i - 1])
		else:
			zeroes.append(zeroes[i - 1])
	zeroes.pop(0)
	k = n - zeroes[-1]
	if k == 0:
		return -1
	ans = float('inf')
	for i in range(n - k + 1):
		zeroesInWindow = zeroes[i + k - 1] - zeroes[i - 1] if i != 0 else zeroes[i + k - 1]
		ans = min(ans, zeroesInWindow)
	return ans


def minSwaps(arr, n):
	total_ones = 0
	cur_zero = 0
	for i in arr:
		if i == 1:
			total_ones += 1
	if total_ones == n:
		return 0
	for i in range(total_ones):
		if arr[i] == 0:
			cur_zero += 1
	ans = cur_zero
	for i in range(total_ones, n):
		if arr[i] == 0:
			cur_zero += 1
		if arr[i - total_ones] == 0:
			cur_zero -= 1
		ans = min(ans, cur_zero)
	return ans if total_ones != 0 else -1


def minSwaps(arr, n):
	ones = sum(arr)
	if ones == 0:
		return -1
	curr = 0
	max1 = 0
	i = 0
	j = 0
	while j < n:
		curr += arr[j]
		if j - i + 1 == ones:
			max1 = max(max1, curr)
			if arr[i] == 1:
				curr -= 1
			i += 1
		j += 1
	return ones - max1


def minSwaps(arr, n):
	c = 0
	for i in range(n):
		if arr[i] == 1:
			c += 1
	if c == 0:
		return -1
	start = 0
	end = c - 1
	maxO = 0
	for i in range(start, end + 1):
		if arr[i] == 1:
			maxO += 1
	ans = maxO
	start += 1
	end += 1
	while end < n:
		if arr[start - 1] == 1:
			maxO -= 1
		if arr[end] == 1:
			maxO += 1
		ans = max(ans, maxO)
		start += 1
		end += 1
	return c - ans


def minSwaps(arr, n):
	window = sum(arr)
	if window == 0:
		return -1
	windowOnes = sum(arr[:window])
	ans = windowOnes
	for i in range(window, len(arr)):
		windowOnes += arr[i]
		windowOnes -= arr[i - window]
		ans = max(ans, windowOnes)
	return window - ans


def minSwaps(arr, n):
	c = 0
	for i in range(n):
		if arr[i] == 1:
			c += 1
	if c == n:
		return 0
	if c == 0:
		return -1
	window = c
	c = 0
	for i in range(window):
		if arr[i] == 1:
			c += 1
	mx = c
	for i in range(window, n):
		if arr[i] == 1:
			c += 1
		if arr[i - window] == 1:
			c -= 1
		mx = max(c, mx)
	return window - mx


def minSwaps(arr, n):
	res = float('inf')
	length = sum(arr)
	if length == 0:
		return -1
	curr_sum = sum(arr[:length])
	for i in range(length, len(arr)):
		res = min(res, length - curr_sum)
		curr_sum += arr[i] - arr[i - length]
	return min(res, length - curr_sum)


import sys

def minSwaps(arr, n):
	k = arr.count(1)
	if k == 0:
		return -1
	zeros = 0
	ones = 0
	for i in range(k):
		if arr[i] == 1:
			ones += 1
		else:
			zeros += 1
	ans = zeros
	start = 0
	for i in range(k, n):
		if arr[i] == 1:
			ones += 1
		else:
			zeros += 1
		if arr[start] == 1:
			ones -= 1
		else:
			zeros -= 1
		ans = min(ans, zeros)
		start += 1
	return ans


def minSwaps(arr, n):
	c = 0
	h = {}
	for i in range(len(arr)):
		if arr[i] == 1:
			c += 1
		h[i] = c
	if c == 0:
		return -1
	start = 0
	stop = c - 1
	m = 0
	while stop < len(arr):
		if start == 0:
			m = h[stop]
		else:
			m = max(m, h[stop] - h[start - 1])
		stop += 1
		start += 1
	return c - m


def minSwaps(arr, n):
	if arr == [0]:
		return -1
	if sum(arr) == 0:
		return -1
	numberOfOnes = 0
	for i in range(0, n):
		if arr[i] == 1:
			numberOfOnes = numberOfOnes + 1
	x = numberOfOnes
	count_ones = 0
	maxOnes = 0
	for i in range(0, x):
		if arr[i] == 1:
			count_ones = count_ones + 1
	maxOnes = count_ones
	for i in range(1, n - x + 1):
		if arr[i - 1] == 1:
			count_ones = count_ones - 1
		if arr[i + x - 1] == 1:
			count_ones = count_ones + 1
		if maxOnes < count_ones:
			maxOnes = count_ones
	numberOfZeroes = x - maxOnes
	return numberOfZeroes


import sys

def minSwaps(arr, n):
	p = arr.count(1)
	if p == 0:
		return -1
	ans = sys.maxsize
	c = 0
	for i in range(p):
		if arr[i] == 0:
			c += 1
	ans = min(c, ans)
	k = 0
	for i in range(p, len(arr)):
		if arr[k] == 0:
			c -= 1
		if arr[i] == 0:
			c += 1
		k += 1
		ans = min(c, ans)
	return ans


def minSwaps(arr, n):
	c = 0
	if 0 not in arr:
		return 0
	elif 1 not in arr:
		return -1
	for i in arr:
		if i == 1:
			c += 1
	m = 10 ** 9
	c1 = 0
	for i in range(0, c):
		if arr[i] == 0:
			c1 += 1
	m = min(m, c1)
	j = 0
	for i in range(c, n):
		if arr[j] == 0:
			c1 -= 1
		if arr[i] == 0:
			c1 += 1
		m = min(m, c1)
		j += 1
	return m


def minSwaps(arr, n):
	one = arr.count(1)
	curr = 0
	mx = 0
	i = 0
	j = 0
	if one == 0:
		return -1
	while j < n:
		curr += arr[j]
		if j - i + 1 == one:
			mx = max(mx, curr)
			if arr[i] == 1:
				curr -= 1
			i += 1
		j += 1
	return one - mx if one - mx >= 0 else -1


def minSwaps(arr, n):
	cum = [0]
	for i in range(0, len(arr)):
		if arr[i] == 1:
			cum.append(cum[i] + 1)
		else:
			cum.append(cum[i])
	cum.pop(0)
	k = cum[len(arr) - 1]
	if k == 0:
		return -1
	maxi = cum[k - 1]
	for i in range(k, len(arr)):
		maxi = max(maxi, cum[i] - cum[i - k])
	return k - maxi


def minSwaps(arr, n):
	ones = sum(arr)
	if ones == 0:
		return -1
	(i, j) = (0, 0)
	maxi = 0
	window = 0
	while j < n:
		window += arr[j]
		if j - i + 1 == ones:
			maxi = max(maxi, window)
			window -= arr[i]
			i += 1
		j += 1
	return ones - maxi


def minSwaps(arr, n):
	if n == 0:
		return -1
	ones = 0
	for i in range(n):
		ones += arr[i]
	if ones == 0:
		return -1
	currOnes = 0
	maxOnes = 0
	i = 0
	j = 0
	while j < n:
		currOnes += arr[j]
		if j - i + 1 == ones:
			maxOnes = max(maxOnes, currOnes)
			currOnes -= arr[i]
			i += 1
		j += 1
	return ones - maxOnes


def minSwaps(arr, n):
	count1 = 0
	for i in range(n):
		if arr[i] == 1:
			count1 += 1
	noof1 = 0
	for i in range(count1):
		if arr[i] == 1:
			noof1 += 1
	currOne = noof1
	maxnof1 = noof1
	for i in range(1, n - count1 + 1):
		if arr[i - 1] == 1:
			currOne -= 1
		if arr[i + count1 - 1] == 1:
			currOne += 1
		maxnof1 = max(maxnof1, currOne)
	if count1 == 0:
		return -1
	else:
		return count1 - maxnof1


def minSwaps(arr, n):
	length = len(arr)
	if length == 0:
		return -1
	ones = 0
	for i in range(length):
		if arr[i] == 1:
			ones += 1
	if ones == 0:
		return -1
	ans = 0
	ones_wndw = 0
	for i in range(ones):
		if arr[i] == 1:
			ones_wndw += 1
	ans = max(ans, ones_wndw)
	for i in range(1, length - ones + 1):
		if arr[i - 1] == 1:
			ones_wndw -= 1
		if arr[i + ones - 1] == 1:
			ones_wndw += 1
		ans = max(ans, ones_wndw)
	return ones - ans


def minSwaps(arr, n):
	start = 0
	number_of_one = arr.count(1)
	if number_of_one == 0:
		return -1
	else:
		end = number_of_one - 1
		minimum = 0
		current = 0
		while end != len(arr):
			if start == 0:
				number_of_zero = arr[start:end + 1].count(0)
				minimum = number_of_zero
				current = minimum
				start += 1
				end += 1
			else:
				e1 = arr[start - 1]
				e2 = arr[end]
				if e1 == e2:
					start += 1
					end += 1
				elif e1 == 1 and e2 == 0:
					current += 1
					start += 1
					end += 1
				elif e1 == 0 and e2 == 1:
					current -= 1
					start += 1
					end += 1
				if current < minimum:
					minimum = current
		return minimum


def minSwaps(arr, n):
	if arr.count(0) == len(arr):
		return -1
	k = arr.count(1)
	numZero = arr[0:k].count(0)
	minSwap = numZero
	j = 0
	for i in range(k, n):
		if arr[j] == 0:
			numZero -= 1
		if arr[i] == 0:
			numZero += 1
		minSwap = min(minSwap, numZero)
		j += 1
	return minSwap


def minSwaps(arr, n):
	k = sum(arr)
	if k == 0:
		return -1
	minZ = curZ = arr[0:k].count(0)
	for i in range(n - k):
		l = i
		r = i + k
		if arr[r] == 0 and arr[l] == 1:
			curZ += 1
		if arr[l] == 0 and arr[r] == 1:
			curZ -= 1
		minZ = min(minZ, curZ)
	return minZ


def minSwaps(arr, n):
	cursum = 0
	k = arr.count(1)
	for i in range(0, k):
		cursum += arr[i]
	j = 0
	mxsum = cursum
	for i in range(k, n):
		cursum = cursum + arr[i] - arr[j]
		mxsum = max(mxsum, cursum)
		j += 1
	if k >= 1:
		return k - mxsum
	else:
		return -1


def minSwaps(arr, n):
	n1 = arr.count(1)
	if n1 == 0:
		return -1
	zeros = 0
	for i in range(0, n1):
		if arr[i] == 0:
			zeros += 1
	minzero = n
	minzero = min(zeros, minzero)
	j = 0
	for i in range(n1, n):
		if arr[i] == 0:
			zeros += 1
		if arr[j] == 0:
			zeros -= 1
		minzero = min(minzero, zeros)
		j += 1
	return minzero


def minSwaps(arr, n):
	k = arr.count(1)
	if k == 0:
		return -1
	c = 0
	for i in range(k):
		if arr[i] == 1:
			c += 1
	d = c
	for i in range(k, n):
		if arr[i] == 1:
			c += 1
		if arr[i - k] == 1:
			c -= 1
		d = max(c, d)
	return k - d


def minSwaps(arr, n):
	k = sum(arr)
	if k == 0:
		return -1
	maxi = 0
	for i in range(k):
		maxi += arr[i]
	cur = maxi
	j = 0
	for i in range(k, n):
		cur = cur - arr[j] + arr[i]
		j += 1
		maxi = max(maxi, cur)
	return k - maxi


def minSwaps(nums, n):
	k = nums.count(1)
	if k == 0:
		return -1
	s = sum(nums[:k])
	mx = s
	for i in range(k, n):
		s += nums[i]
		s -= nums[i - k]
		mx = max(mx, s)
	return k - mx


def minSwaps(arr, n):
	max_size = sum(arr)
	if max_size == 0:
		return -1
	(i, j) = (max_size, 0)
	curr_ones = sum(arr[:max_size])
	min_zeros = max_size - curr_ones
	while i < len(arr):
		curr_ones += arr[i]
		curr_ones -= arr[j]
		min_zeros = min(min_zeros, max_size - curr_ones)
		i += 1
		j += 1
	return min_zeros


def minSwaps(arr, n):
	totalcount = 0
	for i in range(n):
		totalcount += arr[i]
	if totalcount == 0:
		return -1
	maxcount = 0
	currcount = 0
	i = 0
	j = 0
	while j < n:
		currcount += arr[j]
		if j - i + 1 == totalcount:
			maxcount = max(maxcount, currcount)
			if arr[i] == 1:
				currcount -= 1
			i += 1
		j += 1
	ans = totalcount - maxcount
	return ans


def minSwaps(arr, n):
	c = 0
	for i in arr:
		if i == 1:
			c += 1
	if c == 0:
		return -1
	s = 0
	for i in range(c):
		if arr[i] == 0:
			s += 1
	j = c
	i = 0
	m = s
	while j < n:
		if arr[i] == 0:
			s -= 1
		if arr[j] == 0:
			s += 1
		i += 1
		j += 1
		m = min(s, m)
	return m


def minSwaps(arr, n):
	totalOnes = sum(arr)
	currentOnes = maxOnes = 0
	left = right = 0
	while right < n:
		currentOnes += arr[right]
		right += 1
		if right - left > totalOnes:
			currentOnes -= arr[left]
			left += 1
		maxOnes = max(maxOnes, currentOnes)
	return totalOnes - maxOnes if totalOnes > 0 else -1


import collections

def minSwaps(arr, n):
	if not arr:
		return -1
	counter = collections.Counter(arr)
	if 1 not in counter:
		return -1
	num = counter[1]
	curr = 0
	for i in range(num):
		if arr[i] == 0:
			curr += 1
	res = curr
	for i in range(num, len(arr)):
		if arr[i] == 0:
			curr += 1
		if arr[i - num] == 0:
			curr -= 1
		res = min(curr, res)
	return res


def minSwaps(arr, n):
	ones = arr.count(1)
	if ones == 0:
		return -1
	curZeros = 0
	for i in range(ones):
		if arr[i] == 0:
			curZeros += 1
	ans = curZeros
	for i in range(ones, n):
		if arr[i] == 0:
			curZeros += 1
		if arr[i - ones] == 0:
			curZeros -= 1
		ans = min(ans, curZeros)
	return ans


def minSwaps(arr, n):
	total_ones = 0
	for num in arr:
		if num == 1:
			total_ones += 1
	if total_ones == 0:
		return -1
	zeroes = 0
	for i in range(0, total_ones):
		if arr[i] == 0:
			zeroes += 1
	min_swaps = zeroes
	(l, r) = (1, total_ones)
	while r < len(arr):
		if arr[l - 1] == 0:
			zeroes -= 1
		if arr[r] == 0:
			zeroes += 1
		r += 1
		l += 1
		min_swaps = min(min_swaps, zeroes)
	return min_swaps


def minSwaps(arr, n):
	sizeWindow = arr.count(1)
	if sizeWindow == 0:
		return -1
	minSwap = zeroes = arr[:sizeWindow].count(0)
	j = sizeWindow
	while j < len(arr):
		zeroes -= 1 if arr[j - sizeWindow] == 0 else 0
		zeroes += 1 if arr[j] == 0 else 0
		minSwap = min(minSwap, zeroes)
		j += 1
	return minSwap
	return min_swaps


def minSwaps(arr, n):
	oneCount = 0
	for i in arr:
		if i == 1:
			oneCount += 1
	if oneCount == 0:
		return -1
	curr_count = 0
	for i in range(oneCount):
		if arr[i] == 1:
			curr_count += 1
	max_count = curr_count
	for i in range(1, n - oneCount + 1):
		if arr[i - 1] == 1:
			curr_count -= 1
		if arr[i + oneCount - 1] == 1:
			curr_count += 1
		max_count = max(max_count, curr_count)
	return oneCount - max_count


def minSwaps(arr, n):
	total_ones = 0
	for item in arr:
		if item:
			total_ones += 1
	if total_ones == 0:
		return -1
	one_in_this_window = 0
	for i in range(total_ones):
		if arr[i]:
			one_in_this_window += 1
	max_ones = one_in_this_window
	for i in range(total_ones, len(arr)):
		one_in_this_window += arr[i] - arr[i - total_ones]
		max_ones = max(max_ones, one_in_this_window)
	return total_ones - max_ones