You are given a binary string S. You need to transform this string into another string of equal length consisting only of zeros, with the minimum number of operations.
A single operation consists of taking some prefix of the string S and flipping all its values. That is, change all the 0s in this prefix to 1s, and all the 1s in the prefix to 0s. You can use this operation as many number of times as you want over any prefix of the string.

-----Input-----
The only line of the input contains the binary string,  S . 

-----Output-----
Output a single line containing one integer, the minimum number of operations that are needed to transform the given string S into the string of equal length consisting only of zeros.

-----Constraints-----
- 1 ≤ |S| ≤ 100,000

-----Subtasks-----
- Subtask #1 (30 points): 1 ≤ |S| ≤ 2000
- Subtask #2 (70 points): Original constraints.

-----Example-----
Input:
01001001

Output:
6

-----Explanation-----
For the given sample case, let us look at the way where we achieved minimum number of operations.

Operation 1: You flip values in the prefix of length 8 and transform the string into 10110110 
Operation 2: You flip values in the prefix of length 7 and transform the string into 01001000 
Operation 3: You flip values in the prefix of length 5 and transform the string into 10110000 
Operation 4: You flip values in the prefix of length 4 and transform the string into 01000000 
Operation 5: You flip values in the prefix of length 2 and transform the string into 10000000 
Operation 6: You flip values in the prefix of length 1 and finally, transform the string into 00000000

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
s = input()
s1 = s[::-1]
arr = []
cnt = 0
for i in range(len(s1)):
	arr.append(s1[i])
for i in range(len(arr)):
	if arr[i] == '1':
		for j in range(i, len(arr)):
			if arr[j] == '1':
				arr[j] = '0'
			else:
				arr[j] = '1'
		cnt += 1
print(cnt)


def rev(s):
	s1 = ''
	for i in s:
		if i == '0':
			s1 = s1 + '1'
		else:
			s1 = s1 + '0'
	return s1
s = input()
s1 = ''
c = 0
for i in range(len(s) - 1, -1, -1):
	if s[i] == '1':
		s1 = rev(s[:i])
		c = c + 1
		s = s1
print(c)


try:
	s = input()
	c = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			c = c + 1
	if s[-1] == '1':
		print(c + 1)
	else:
		print(c)
except:
	pass


n = input()
cnt = 0
x = n[0]
for i in range(len(n)):
	if n[i] != x:
		cnt += 1
		x = n[i]
if n[-1] == '1':
	print(cnt + 1)
else:
	print(cnt)


def main():
	rev_s = reversed(input())
	flips = 0
	flipped = False
	for b in rev_s:
		if b == '0':
			if not flipped:
				continue
			else:
				flipped = False
				flips += 1
				continue
		elif flipped:
			continue
		else:
			flipped = True
			flips += 1
			continue
	print(flips)
main()


l = input()
cnt = 0
n = len(l)
for i in range(n - 1):
	if l[i] != l[i + 1]:
		cnt += 1
if l[-1] == '1':
	cnt += 1
print(cnt)


t = 1
for n in range(t):
	s = input()
	count = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			count += 1
	if s[len(s) - 1] == '0':
		count -= 1
	print(count)


S = str(input())
a = []
for i in S:
	a.append(i)
c = 0
for i in range(len(a) - 1, -1, -1):
	if a[i] == '1':
		for k in range(0, i + 1):
			if a[k] == '1':
				a[k] = '0'
			else:
				a[k] = '1'
		c = c + 1
print(c)


s = input()
arr = []
n = len(s)
i = 0
while i < n:
	x = s[i]
	while i < n and s[i] == x:
		i += 1
	arr.append(x)
m = len(arr)
if arr[0] == '0':
	if m == 1:
		print(0)
	else:
		print(m // 2 * 2)
elif m & 1 == 1:
	print(m // 2 * 2 + 1)
else:
	m -= 1
	print(m // 2 * 2 + 1)


t = 1
for _ in range(t):
	a = input()
	count = 1
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			count += 1
	if a[len(a) - 1] == '0':
		count -= 1
	print(count)


s = input()
s = list(s)
(n, c) = (0, 0)
j = 0
while n != 1:
	j += 1
	p = -1
	for i in range(len(s) - 2, -1, -1):
		if j % 2 != 0:
			if s[i] == '0':
				p = i
				break
		elif s[i] == '1':
			p = i
			break
	if p != -1:
		c += 1
	s = s[0:p + 1]
	if len(s) == 1 or len(s) == 0:
		n = 1
print(c + 1)