Given a string S consisting of only opening and closing curly brackets '{' and '}', find out the minimum number of reversals required to convert the string into a balanced expression.
A reversal means changing '{' to '}' or vice-versa.
Example 1:
Input:
S = "}{{}}{{{"
Output: 3
Explanation: One way to balance is:
"{{{}}{}}". There is no balanced sequence
that can be formed in lesser reversals.
Example 2:
Input: 
S = "{{}{{{}{{}}{{"
Output: -1
Explanation: There's no way we can balance
this sequence of braces.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countRev() which takes the string S as the input parameter and returns the minimum number of reversals required to balance the bracket sequence. If balancing is not possible, return -1. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: def countRev (s):

    # your code here

Solutions:
def countRev(s):
	stack = []
	n = len(s)
	for i in range(n):
		if s[i] == '{':
			stack.append('{')
		elif len(stack) == 0 or stack[-1] == '}':
			stack.append('}')
		else:
			stack.pop()
	t1 = 0
	for i in stack:
		if i == '}':
			t1 += 1
		else:
			break
	t2 = len(stack) - t1
	if (t1 + t2) % 2 == 0:
		if t1 % 2 == 0 and t2 % 2 == 0:
			ans = t1 // 2 + t2 // 2
		elif t1 % 2 == 1 and t2 % 2 == 1:
			ans = t1 // 2 + t2 // 2 + 2
		else:
			return -1
	else:
		return -1
	return ans


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	check = []
	closing_brak = 0
	opening_brak = 0
	res = 0
	for i in range(len(s)):
		if s[i] == '{':
			check.append(s[i])
		elif s[i] == '}' and len(check) > 0 and (check[-1] == '{'):
			check.pop()
		elif s[i] == '}':
			check.append('{')
			res += 1
	opening_brak = len(check)
	res += opening_brak // 2
	return res


def countRev(s):
	stack = [-1]
	for elm in s:
		if elm == '{' or stack[-1] != '{':
			stack.append(elm)
		else:
			stack.pop()
	a = 0
	b = 0
	top = len(stack) - 1
	while top > 0:
		if stack[top] == '{':
			a += 1
		else:
			b += 1
		top -= 1
	if a % 2 == 0 and b % 2 != 0 or (a % 2 != 0 and b % 2 == 0):
		return -1
	else:
		return (a + 1) // 2 + (b + 1) // 2


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	st = [-1]
	for ele in s:
		if ele == '{':
			st.append(ele)
		elif st[-1] == '{':
			st.pop()
		else:
			st.append(ele)
	a = st.count('{')
	b = st.count('}')
	ans = (a + 1) // 2 + (b + 1) // 2
	return int(ans)


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	(open, close) = (0, 0)
	for i in range(len(s)):
		if s[i] == '{':
			open += 1
		elif open:
			open -= 1
		else:
			close += 1
	return (open + 1) // 2 + (close + 1) // 2


import math

def countRev(s):
	left_p = 0
	right_p = 0
	if len(s) % 2 != 0:
		return -1
	for i in s:
		if i == '{':
			left_p += 1
		elif left_p:
			left_p -= 1
		else:
			right_p += 1
	return math.ceil(left_p / 2) + math.ceil(right_p / 2)


from math import ceil

def countRev(s):
	open_b = 0
	close_b = 0
	if len(s) % 2 != 0:
		return -1
	for i in s:
		if i == '{':
			open_b += 1
		elif open_b == 0:
			close_b += 1
		else:
			open_b -= 1
	return ceil(open_b / 2.0) + ceil(close_b / 2.0)


import math

def countRev(expr):
	length = len(expr)
	if length % 2 != 0:
		return -1
	left_brace = 0
	right_brace = 0
	for i in range(length):
		if expr[i] == '{':
			left_brace += 1
		elif left_brace == 0:
			right_brace += 1
		else:
			left_brace -= 1
	ans = math.ceil(left_brace / 2) + math.ceil(right_brace / 2)
	return ans


def valid(s):
	stack = []
	for i in range(len(s)):
		if s[i] == '{':
			stack.append(s[i])
		elif stack and stack[-1] == '{':
			stack.pop()
		else:
			stack.append(s[i])
	return stack

def countRev(s):
	arr = valid(s)
	if len(s) % 2 != 0:
		return -1
	a = 0
	b = 0
	for i in arr:
		if i == '{':
			a += 1
		else:
			b += 1
	res = (a + 1) // 2 + (b + 1) // 2
	return res


def countRev(s):
	lenn = len(s)
	stk = []
	if lenn % 2 != 0:
		return -1
	for i in range(lenn):
		if s[i] == '}' and len(stk):
			if stk[0] == '{':
				stk.pop(0)
			else:
				stk.insert(0, s[i])
		else:
			stk.insert(0, s[i])
	red_len = len(stk)
	n = 0
	while len(stk) and stk[0] == '{':
		stk.pop(0)
		n += 1
	return red_len // 2 + n % 2


from collections import deque
import math

def countRev(s):
	if len(s) & 1:
		return -1
	countOfOpening = 0
	countOfClosing = 0
	stack = deque()
	for i in range(len(s)):
		if s[i] == '{':
			stack.append('{')
		elif s[i] == '}':
			if not stack:
				countOfOpening += 1
			else:
				stack.pop()
	while stack:
		stack.pop()
		countOfClosing += 1
	return math.ceil(countOfOpening / 2) + math.ceil(countOfClosing / 2)


def countRev(s):
	ans = 0
	z = []
	for i in s:
		if i == '{':
			z.append('{')
		elif len(z) == 0:
			ans = ans + 1
			z.append('{')
		else:
			z.pop()
	if len(z) % 2 == 0:
		return ans + int(len(z) / 2)
	else:
		return -1


def countRev(s):
	n = len(s)
	if n % 2 != 0:
		return -1
	else:
		Open = 0
		close = 0
		for i in range(n):
			if s[i] == '{':
				Open += 1
			elif Open == 0:
				close += 1
			else:
				Open -= 1
		if Open % 2 != 0:
			a = Open // 2 + 1
		if Open % 2 == 0:
			a = Open // 2
		if close % 2 != 0:
			b = close // 2 + 1
		if close % 2 == 0:
			b = close // 2
		c = a + b
		return c


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	stack = []
	reverse_count = 0
	for i in range(len(s)):
		if s[i] == '{':
			stack.append(s[i])
		elif len(stack) > 0 and stack[-1] == '{':
			stack.pop()
		else:
			stack.append('{')
			reverse_count += 1
	reverse_count += len(stack) // 2
	return reverse_count


import math

def countRev(s):
	n = len(s)
	if n % 2 == 1:
		return -1
	stack = []
	for i in s:
		if i == '}' and len(stack) != 0:
			top = stack[-1]
			if top == '{':
				stack.pop()
			else:
				stack.append(i)
		else:
			stack.append(i)
	open_count = 0
	close_count = 0
	while len(stack) != 0:
		top = stack.pop()
		if top == '{':
			open_count += 1
		else:
			close_count += 1
	ans = math.ceil(open_count / 2) + math.ceil(close_count / 2)
	return ans


def countRev(s):
	ans = 0
	st = []
	n = len(s)
	if n & 1 == 1:
		return -1
	for i in range(n):
		if len(st) == 0 and s[i] == '}':
			st.append('{')
			ans += 1
		elif s[i] == '{':
			st.append('{')
		elif len(st) != 0 and st[-1] == '{':
			st.pop()
	return ans + len(st) // 2


def countRev(s):
	stack = []
	for x in s:
		if x == '{':
			stack.append(x)
		elif len(stack) == 0:
			stack.append(x)
		elif stack[-1] == '{':
			stack.pop()
		else:
			stack.append(x)
	open = 0
	closed = 0
	while len(stack) != 0:
		a = stack.pop()
		if a == '{':
			open += 1
		else:
			closed += 1
	if open % 2 == 0 and closed % 2 == 0:
		return open // 2 + closed // 2
	elif open % 2 != 0 and closed % 2 != 0:
		return open // 2 + closed // 2 + 2
	else:
		return -1


def countRev(exp):
	stack = []
	for i in exp:
		if i == '{':
			stack.append(i)
		elif stack and stack[-1] == '{':
			stack.pop()
		else:
			stack.append(i)
	if len(stack) % 2:
		return -1
	ans = 0
	i = 0
	while i < len(stack):
		if stack[i] == stack[i + 1]:
			ans += 1
		else:
			ans += 2
		i += 2
	return ans


def countRev(s):
	d = []
	l = len(s)
	if l % 2 != 0:
		return -1
	for i in s:
		if i == '}' and d:
			if d[0] == '{':
				d.pop(0)
			else:
				d.insert(0, i)
		else:
			d.insert(0, i)
	length = len(d)
	n = 0
	while d and d[0] == '{':
		d.pop(0)
		n += 1
	return length // 2 + n % 2


from collections import deque

def countRev(s):
	d = []
	l = len(s)
	if l % 2 != 0:
		return -1
	for i in s:
		if i == '}' and d:
			if d[0] == '{':
				d.pop(0)
			else:
				d.insert(0, i)
		else:
			d.insert(0, i)
	length = len(d)
	n = 0
	while d and d[0] == '{':
		d.pop(0)
		n += 1
	return length // 2 + n % 2


import math

def countRev(s):
	if len(s) % 2 == 0:
		stack = []
		count = 0
		for i in s:
			if i == '{':
				stack.append(i)
			elif i == '}':
				if stack:
					stack.pop()
				else:
					count += 1
		rev = math.ceil(len(stack) / 2) + math.ceil(count / 2)
		return rev
	else:
		return -1


def countRev(expr):
	import math
	length = len(expr)
	if length % 2 != 0:
		return -1
	left_b = 0
	right_b = 0
	for i in range(length):
		if expr[i] == '{':
			left_b += 1
		elif left_b == 0:
			right_b += 1
		else:
			left_b -= 1
	ans = math.ceil(left_b / 2) + math.ceil(right_b / 2)
	return ans


def countRev(s):
	import math
	stck = []
	cnt = 0
	if len(s) % 2 != 0:
		return -1
	for i in s:
		if i == '{':
			stck.append('{')
		if i == '}':
			if stck:
				stck.pop()
			else:
				cnt += 1
	open = len(stck)
	close = cnt
	return math.ceil(open / 2) + math.ceil(close / 2)


import math

def countRev(s):
	if len(s) % 2 != 0:
		return -1
	open = 0
	close = 0
	rev = 0
	for i in range(len(s)):
		if s[i] == '{':
			open += 1
		elif open == 0:
			close += 1
		else:
			open -= 1
	rev = math.ceil(open / 2) + math.ceil(close / 2)
	return rev


def countRev(s):
	stack = []
	count = 0
	if len(s) % 2:
		return -1
	for i in s:
		if stack == [] and i == '}':
			count += 1
			stack.append('{')
			continue
		if i == '{':
			stack.append(i)
		elif stack[-1] == '{' and i == '}':
			stack.pop()
		else:
			stack.append(i)
	return count + len(stack) // 2


def countRev(arr):
	r = 0
	op = 0
	n = len(arr)
	cl = 0
	a1 = 0
	a2 = 0
	while r < n:
		if arr[r] == '{':
			op += 1
		else:
			cl += 1
		if cl > op:
			op = 0
			cl = 0
			a1 += 1
		v = min(op, cl)
		op -= v
		cl -= v
		r += 1
	if op > 0:
		a2 += op
	if a1 + a2 & 1 == 0:
		return a1 // 2 + min(1, a1 % 2) + a2 // 2 + min(1, a2 % 2)
	return -1


from math import ceil

def countRev(s):
	st = []
	for i in s:
		if i == '{':
			st.append(i)
		elif st and st[-1] == '{':
			st.pop()
		else:
			st.append(i)
	if len(st) % 2 != 0:
		return -1
	close = open = 0
	for i in st:
		if i == '{':
			open += 1
		else:
			close += 1
	rev = ceil(open / 2) + ceil(close / 2)
	return rev


def countRev(s):
	if len(s) % 2:
		return -1
	stack = 0
	count = 0
	for c in s:
		if c == '{':
			stack += 1
		elif stack:
			stack -= 1
		else:
			count += 1
			stack += 1
	return count + stack // 2


from math import ceil

def countRev(s):
	n = len(s)
	if n == 0 or n % 2 != 0:
		return -1
	open = 0
	close = 0
	for i in range(n):
		if s[i] == '{':
			open += 1
		elif open == 0:
			close += 1
		else:
			open -= 1
	return ceil(open / 2) + ceil(close / 2)


def countRev(s):
	lenn = len(s)
	if lenn % 2:
		return -1
	backPointer = {i: i - 1 for i in range(lenn)}
	front = 0
	back = -1
	while front < lenn:
		if back == -1 or s[back] == '}' or s[front] == '{':
			backPointer[front] = back
			back = front
		else:
			back = backPointer[back]
		front += 1
	forward = 0
	backward = 0
	while back != -1:
		if s[back] == '{':
			forward += 1
		else:
			backward += 1
		back = backPointer[back]
	total = 0
	if forward % 2:
		total += forward // 2 + 1
	else:
		total += forward // 2
	if backward % 2:
		total += backward // 2 + 1
	else:
		total += backward // 2
	return total


def countRev(s):
	st = []
	n = 0
	for i in s:
		if not st:
			st.append(i)
			n += 1
		elif st[-1] == '{' and i == '}':
			st.pop()
			n -= 1
		else:
			st.append(i)
			n += 1
	c = 0
	if n % 2 == 1:
		return -1
	else:
		while st:
			if st[-1] == '{' and st[-2] == '{' or (st[-1] == '}' and st[-2] == '}'):
				c += 1
				st.pop()
				st.pop()
			elif st[-1] == '{' and st[-2] == '}':
				c += 2
				st.pop()
				st.pop()
		return c


def countRev(s):
	n = len(s)
	if n % 2 != 0:
		return -1
	stack = []
	count = 0
	for i in range(n):
		if s[i] == '{':
			stack.append(s[i])
		elif stack == []:
			stack.append(s[i])
			count += 1
		else:
			stack.pop()
	return count + len(stack) // 2


def countRev(s):
	stack = []
	if len(s) % 2 == 1:
		return -1
	counter = 0
	for item in s:
		if len(stack) == 0 and item == '}':
			counter += 1
			stack.append('{')
		elif len(stack) == 0 and item == '{':
			stack.append(item)
		elif item == '}' and stack[-1] == '{':
			stack.pop()
		else:
			stack.append(item)
	return counter + len(stack) // 2


def countRev(s):
	temp = []
	count = 0
	exp = s
	if len(exp) % 2 == 1:
		return -1
	else:
		for i in range(len(exp)):
			if exp[i] == '{':
				temp.append(exp[i])
			else:
				try:
					if temp[-1] == '{':
						temp.pop()
					else:
						temp.append('}')
				except:
					temp.append('}')
	for i in range(0, len(temp), 2):
		if temp[i] == '}' and temp[i + 1] == '}':
			count += 1
		elif temp[i] == '}' and temp[i + 1] == '{':
			count += 2
		elif temp[i] == '{' and temp[i + 1] == '{':
			count += 1
	return count


def countRev(s):
	(temp, res, n) = (0, 0, len(s))
	if n % 2 != 0:
		return -1
	for i in range(n):
		if s[i] == '{':
			temp += 1
		elif temp == 0:
			res += 1
			temp += 1
		else:
			temp -= 1
	if temp > 0:
		res += temp // 2
	return res


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	count = 0
	stack = 0
	for item in s:
		if item is '{':
			stack += 1
		elif stack:
			stack -= 1
		else:
			count += 1
			stack += 1
	return count + stack // 2


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	cl = clean(s)
	count = 0
	flag = False
	for c in cl:
		if c == '{':
			if flag:
				count += 1
				flag = False
			else:
				flag = True
		elif flag:
			flag = False
		else:
			flag = True
			count += 1
	return count

def clean(s):
	ret = []
	for i in range(len(s)):
		c = s[i]
		if c == '{':
			ret.append('{')
		elif len(ret) > 0 and ret[len(ret) - 1] == '{':
			del ret[len(ret) - 1]
		else:
			ret.append('}')
	return ret


def countRev(s):
	s1 = []
	c = 0
	for i in range(len(s)):
		if s[i] == '{':
			s1.append(s[i])
		elif len(s1) == 0:
			c += 1
			s1.append('}')
		else:
			s1.pop()
	if len(s1) % 2 == 0:
		c += len(s1) // 2
		return c
	else:
		return -1


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	else:
		queue = []
		while s:
			if queue == []:
				temp = s[0]
				s = s[1:]
				queue.append(temp)
			elif queue[-1] == '{' and s[0] == '}':
				queue.pop()
				s = s[1:]
			else:
				temp = s[0]
				s = s[1:]
				queue.append(temp)
		n = len(queue)
		ans = n
		current = []
		while queue:
			if current == []:
				current.append(queue.pop(0))
			elif current[-1] == '}' and queue[0] == '}':
				ans -= 1
				current.pop()
				queue.pop(0)
			else:
				current.append(queue.pop(0))
		for i in range(int(len(current) / 2)):
			if current[i] == '{':
				ans -= 1
		for i in range(int(len(current) / 2), len(current) - 1):
			if current[i] == '}':
				ans -= 1
		return ans


def countRev(s):
	k = 0
	k1 = 0
	if len(s) % 2:
		return -1
	for i in s:
		if i is '{':
			k = k + 1
		elif k:
			k = k - 1
		else:
			k1 = k1 + 1
			k = k + 1
	return k1 + k // 2


import math

def countRev(s):
	if len(s) % 2:
		return -1
	leftBrace = 0
	rightBrace = 0
	for c in s:
		if c == '{':
			leftBrace += 1
		elif leftBrace == 0:
			rightBrace += 1
		else:
			leftBrace -= 1
	return math.ceil(leftBrace / 2) + math.ceil(rightBrace / 2)


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	stack = []
	for i in range(len(s)):
		if not stack:
			stack.append(s[i])
		elif s[i] == '{':
			stack.append(s[i])
		elif stack[-1] == '{':
			stack.pop()
		else:
			stack.append('}')
	count = 0
	while stack:
		x = stack.pop()
		y = stack.pop()
		if x == y:
			count += 1
		else:
			count += 2
	return count


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	o1 = 0
	c1 = 0
	res = 0
	for i in s:
		if i == '{':
			o1 += 1
		else:
			c1 += 1
		if c1 > o1:
			res += c1 - o1
			(c1, o1) = (o1, c1)
	res += abs(c1 - o1) // 2
	return res


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	op = 0
	cl = 0
	res = 0
	for i in s:
		if i == '{':
			op += 1
		else:
			cl += 1
		if cl > op:
			res += cl - op
			(cl, op) = (op, cl)
	res += abs(cl - op) // 2
	return res


from collections import deque

def countRev(s):
	stack = deque()
	q = deque()
	count = 0
	if len(s) % 2 == 1:
		return -1
	for i in s:
		if len(stack) == 0:
			stack.append(i)
		elif i == '{':
			stack.append(i)
		elif stack[-1] == '{':
			stack.pop()
		else:
			stack.append(i)
	while len(stack):
		q.appendleft(stack.pop())
	while len(q):
		temp = q.popleft()
		if temp == q[0]:
			count += 1
		else:
			count += 2
		q.popleft()
	return count


import math

def countRev(s):
	if len(s) % 2 != 0:
		return -1
	open = 0
	close = 0
	str = []
	for i in range(len(s)):
		if s[i] == '{':
			str.append(s[i])
			open += 1
		elif s[i] == '}' and len(str) != 0 and (str[-1] == '{'):
			str.pop()
			open -= 1
		else:
			close += 1
	close = math.ceil(close / 2)
	open = math.ceil(open / 2)
	return open + close


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	st = []
	for i in s:
		if len(st) > 0 and st[len(st) - 1] != i and (st[len(st) - 1] == '{'):
			st.pop()
		else:
			st.append(i)
	count = 0
	for j in range(0, len(st), 2):
		if st[j] == st[j + 1]:
			count += 1
		else:
			count += 2
	return count


def top(stack):
	if len(stack) == 0:
		return 0
	return stack[len(stack) - 1]

def countRev(inputString):
	stack = []
	count = 0
	for i in range(len(inputString)):
		if top(stack) == '{' and inputString[i] == '}':
			stack.pop()
		else:
			stack.append(inputString[i])
	stack2 = list()
	for i in range(len(stack)):
		if top(stack2) == stack[i]:
			count += 1
			stack2.pop()
		elif top(stack2) == '}' and stack[i] == '{':
			count += 2
			stack2.pop()
		else:
			stack2.append(stack[i])
	if len(stack2) % 2 == 0:
		return count + len(stack2) // 2
	else:
		return -1


def countRev(s):
	opens = 0
	res = 0
	for c in s:
		if opens == 0:
			if c == '}':
				res += 1
			opens += 1
		elif c == '}':
			opens -= 1
		else:
			opens += 1
	if opens % 2 != 0:
		return -1
	return res + opens // 2


def countRev(s):
	if len(s) & 1:
		return -1
	li = []
	fb = 0
	bb = 0
	for i in s:
		if i == '{':
			li.append(i)
			fb += 1
		elif i == '}' and len(li) > 0 and (li[len(li) - 1] == '{'):
			li.pop()
			fb -= 1
		else:
			bb += 1
	if fb & 1:
		fb = fb // 2 + 1
	else:
		fb = fb // 2
	if bb & 1:
		bb = bb // 2 + 1
	else:
		bb = bb // 2
	return fb + bb


def countRev(s):
	n = len(s)
	if n % 2 == 1:
		return -1
	open = 0
	close = 0
	li = []
	for i in s:
		if i == '{':
			li.append(i)
			open += 1
		elif i == '}' and len(li) != 0 and (li[-1] == '{'):
			li.pop()
			open -= 1
		else:
			close += 1
	co = open // 2 + 1 if open % 2 == 1 else open // 2
	cc = close // 2 + 1 if close % 2 == 1 else close // 2
	ans = cc + co
	return ans


def countRev(s):
	if len(s) % 2 == 1:
		return -1
	count = 0
	stack = 0
	for i in s:
		if i is '{':
			stack += 1
		elif stack != 0:
			stack -= 1
		else:
			count += 1
			stack += 1
	ans = count + stack // 2
	return ans


def countRev(s):
	stack = []
	cnt = 0
	for ele in s:
		if ele == '{':
			stack.append(ele)
		elif len(stack) == 0:
			cnt += 1
			stack.append(ele)
		else:
			stack.pop()
	if len(stack) % 2 != 0:
		return -1
	return cnt + len(stack) // 2


def countRev(s):
	l = []
	if len(s) % 2:
		return '-1'
	else:
		for i in s:
			if i == '{':
				l.append(i)
			elif i == '}' and len(l) > 0:
				if l[-1] == '{':
					l.pop()
				else:
					l.append(i)
			else:
				l.append(i)
		t = len(l)
		o = 0
		while len(l) and l[-1] == '{':
			l.pop()
			o = o + 1
		return t // 2 + o % 2


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	else:
		while s != '':
			if '{}' in s:
				s = s.replace('{}', '')
			else:
				break
		if s == '':
			return 0
		else:
			a = 0
			b = 0
			if '{' in s:
				a = s.count('{')
			if '}' in s:
				b = s.count('}')
			return (a + 1) // 2 + (b + 1) // 2


def countRev(s):
	n = len(s)
	lst = []
	pt = 0
	for i in range(n):
		if pt == 0:
			lst.append(s[i])
			pt += 1
		elif s[i] == '{':
			lst.append(s[i])
			pt += 1
		elif lst[-1] == '{':
			lst.pop()
			pt -= 1
		else:
			lst.append(s[i])
			pt += 1
	if len(lst) % 2:
		return -1
	else:
		l = 0
		r = len(lst) - 1
		ans = 0
		while r > l:
			if lst[l] == lst[r]:
				ans += 1
				l += 1
				r -= 1
			elif lst[l] == lst[l + 1]:
				ans += 1
				l += 2
			else:
				ans += 2
				l += 1
				r -= 1
	return ans


def countRev(s):
	Str = s
	st = []
	ans = 0
	for i in range(len(Str)):
		if Str[i] == '{':
			st.append(Str[i])
		elif len(st) > 0:
			st.pop()
		else:
			st.append('{')
			ans += 1
	if len(st) % 2 != 0:
		return -1
	ans += len(st) // 2
	return ans


def countRev(s):
	import math
	if len(s) % 2 != 0:
		return -1
	openn = 0
	close = 0
	rcount = 0
	for b in s:
		if b == '{':
			openn += 1
		elif openn == 0:
			close += 1
		else:
			openn -= 1
	rcount = math.ceil(openn / 2.0) + math.ceil(close / 2.0)
	return rcount


import math

def countRev(s):
	if len(s) % 2 != 0:
		return -1
	o = c = 0
	for x in s:
		if o == 0:
			if x == '}':
				c += 1
			else:
				o += 1
		elif x == '}':
			o -= 1
		else:
			o += 1
	return math.ceil(c / 2) + math.ceil(o / 2)


def countRev(s):
	St = []
	c = 0
	if s[0] == '}':
		St.append('{')
		c += 1
	else:
		St.append('{')
	for i in range(1, len(s)):
		if St and s[i] == '}' and (St[-1] == '{'):
			St.pop()
		else:
			St.append(s[i])
	if len(St) % 2 == 0:
		c += St.count('{') % 2 + len(St) // 2
	else:
		c = -1
	return c


def countRev(s):
	st = []
	ans = 0
	for i in s:
		if i == '{':
			st.append(i)
		elif st and st[-1] == '{':
			st.pop()
		else:
			st.append(i)
	ans = 0
	if len(st) % 2:
		return -1
	while st:
		c1 = st.pop()
		c2 = st.pop()
		if c1 == c2:
			ans += 1
		else:
			ans += 2
	return ans


def countRev(s):
	n = len(s)
	count_close = 0
	count_open = 0
	if n % 2:
		return -1
	for i in range(n):
		if s[i] == '{':
			count_open += 1
		elif count_open == 0:
			count_close += 1
			count_open = 1
		else:
			count_open -= 1
	return count_close + count_open // 2


def countRev(input_string):
	n = len(input_string)
	if n % 2 != 0:
		return -1
	brackets_pair = {'[': ']', '(': ')', '{': '}'}
	output_stacks = []
	non_pair_closing_count = 0
	for i in range(0, n):
		element = input_string[i]
		if element in brackets_pair:
			output_stacks.append(element)
		elif len(output_stacks) > 0:
			element_from_output_stack = output_stacks.pop()
			if not check_pair(element_from_output_stack, element):
				output_stacks.append(element_from_output_stack)
				non_pair_closing_count = non_pair_closing_count + 1
		else:
			non_pair_closing_count = non_pair_closing_count + 1
	open_brackets_count = len(output_stacks)
	closing_brackets_count = non_pair_closing_count
	single_flip = open_brackets_count // 2 + closing_brackets_count // 2
	dual_flip = open_brackets_count % 2 + closing_brackets_count % 2
	return single_flip + dual_flip

def check_pair(opening_element, closing_element):
	opening_brackets = {'[': ']', '(': ')', '{': '}'}
	return closing_element == opening_brackets[opening_element]


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	opens = 0
	closes = 0
	for i in s:
		if i == '{':
			opens += 1
		else:
			closes += 1
			if opens:
				opens -= 1
				closes -= 1
	if opens % 2 != 0 and closes % 2 != 0:
		return int((opens + closes) / 2) + 1
	elif opens == closes:
		return int((opens + closes) / 2)
	elif opens % 2 == 0 and closes % 2 == 0:
		reversal = 0
		reversal = int(opens / 2)
		reversal += int(closes / 2)
		return reversal


def countRev(s):
	(opened_braces, closed_braces) = (0, 0)
	for c in s:
		if c == '{':
			opened_braces += 1
		elif opened_braces > 0:
			opened_braces -= 1
		else:
			closed_braces += 1
	count = 0
	count += opened_braces // 2
	opened_braces %= 2
	count += closed_braces // 2
	closed_braces %= 2
	if opened_braces == closed_braces:
		return count + opened_braces * 2
	else:
		return -1


def countRev(s):
	n = len(s)
	if n % 2 != 0:
		return -1
	opened = 0
	closed = 0
	for i in s:
		if i == '{':
			opened += 1
		elif opened > 0:
			opened -= 1
		else:
			closed += 1
	return (opened + 1) // 2 + (closed + 1) // 2


def countRev(s):
	n = len(s)
	if n % 2 != 0:
		return -1
	stack = []
	closing = 0
	for i in s:
		if i == '{':
			stack.append(i)
		elif i == '}' and stack:
			stack.pop()
		else:
			closing += 1
	opening = len(stack)
	if opening % 2 == 0:
		opening /= 2
	else:
		opening = opening // 2 + 1
	if closing % 2 == 0:
		closing /= 2
	else:
		closing = closing // 2 + 1
	return int(opening + closing)


def countRev(s):
	if len(s) % 2 != 0:
		return -1
	st = []
	for i in range(len(s)):
		if len(st) > 0 and s[i] == '}':
			if st[0] == '{':
				st.pop(0)
			else:
				st.insert(0, s[i])
		else:
			st.insert(0, s[i])
	l = len(st)
	n = 0
	while len(st) and st[0] == '{':
		st.pop(0)
		n += 1
	return l // 2 + n % 2


def countRev(s):
	stack = []
	c = -1
	for i in range(0, len(s)):
		if c == -1:
			stack.append(s[i])
			c = c + 1
		elif s[i] == '}':
			if stack[c] == '{':
				stack.pop()
				c = c - 1
			else:
				c = c + 1
				stack.append(s[i])
		else:
			c = c + 1
			stack.append(s[i])
	c1 = 0
	c2 = 0
	if len(stack) % 2 != 0:
		return -1
	for i in stack:
		if i == '{':
			c1 = c1 + 1
		else:
			c2 = c2 + 1
	z = 0
	z = c1 // 2
	z = z + c2 // 2
	if c1 % 2 != 0:
		z = z + 2
	return z


from math import ceil

def countRev(s):
	if len(s) % 2 != 0:
		return -1
	stack = []
	count_open = 0
	count_close = 0
	for i in s:
		if i == '{':
			stack.append(i)
		elif i == '}' and stack:
			stack.pop()
		else:
			count_close += 1
	count_open = len(stack)
	count_close = ceil(count_close / 2)
	count_open = ceil(count_open / 2)
	return count_close + count_open