Tenka1 Programmer Beginner Contest 2019 - Stones

There are N stones arranged in a row. Every stone is painted white or black. A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is `.`, and the stone is black if the character is `#`.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone. Find the minimum number of stones that needs to be recolored.

Constraints

* 1 \leq N \leq 2\times 10^5
* S is a string of length N consisting of `.` and `#`.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the minimum number of stones that needs to be recolored.

Examples

Input

3
#.#


Output

1


Input

3
.#


Output

1


Input

5
.##.


Output

2


Input

9
.........


Output

0

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
s = input()
black = 0
ans = white = s.count('.')
for i in range(n):
	if s[i] == '#':
		black += 1
	else:
		white -= 1
	ans = min(ans, black + white)
print(ans)


n = int(input())
a = [0]
b = [0]
for i in input():
	t = i == '.'
	a += [a[-1] + t]
	b += [b[-1] + 1 - t * 2]
print(min([i + a[n] for i in b]))


n = int(input())
s = input()
num = s.count('.')
nums = [num]
for c in s:
	if c == '#':
		num += 1
	else:
		num -= 1
	nums.append(num)
print(min(nums))


n = int(input())
s = input()
w = s.count('.')
b = 0
r = w
for (i, x) in enumerate(s):
	if x == '#':
		b += 1
	else:
		w -= 1
		r = min(r, b + w)
print(r)


n = int(input())
s = input()
ans = 0
c = 0
for i in range(n):
	if s[i] == '#':
		c += 1
	elif c >= 1:
		ans += 1
		c -= 1
print(ans)


N = int(input())
S = list(input())
lb = 0
rw = S.count('.')
li = [rw]
for i in range(N):
	if S[i] == '#':
		lb += 1
	else:
		rw -= 1
	li.append(lb + rw)
print(min(li))


n = int(input())
s = input()
cnt = s.count('#')
l = [cnt]
for i in range(n):
	if s[n - i - 1] == '#':
		cnt -= 1
		l.append(cnt)
	else:
		cnt += 1
		l.append(cnt)
print(min(l))


N = int(input())
S = input()
tmp = S.count('.')
ans = tmp
for i in range(N):
	if S[i] == '.':
		tmp -= 1
	else:
		tmp += 1
	ans = min(ans, tmp)
print(ans)


N = int(input())
S = input()
w = S.count('.')
ans = 10 ** 9
cost = 0
for s in S:
	w -= s == '.'
	ans = w + cost if w + cost < ans else ans
	cost += s == '#'
print(ans)


n = int(input())
s = input()
a = [0]
for i in s:
	if i == '.':
		a += [a[-1] + 1]
	else:
		a += [a[-1]]
w = s.count('.')
print(min((i - a[i] + w - a[i] for i in range(n + 1))))


n = int(input())
s = input()
w = s.count('.')
b = 0
ans = w + b
for i in s:
	if i == '#':
		b += 1
	else:
		w -= 1
	if ans >= b + w:
		ans = b + w
print(ans)


n = int(input())
s = input()
tres = s.count('.')
res = tres
for c in s:
	if c == '.':
		tres -= 1
	else:
		tres += 1
	res = min(res, tres)
print(res)


n = int(input())
s = input()
m = s.count('.')
ans = m
for i in range(n):
	if s[i] == '#':
		m = m + 1
	else:
		m = m - 1
	ans = min(m, ans)
print(ans)


n = int(input())
s = input()
wcount = 0
min_val = 0
for i in range(n):
	if s[i] == '.':
		wcount += 1
	min_val = min(min_val, i + 1 - wcount * 2)
print(wcount + min_val)


n = int(input())
ls = list(input())
c_list = [ls.count('.')]
for i in ls:
	if i == '.':
		c_list.append(c_list[-1] - 1)
	else:
		c_list.append(c_list[-1] + 1)
print(min(c_list))


(n, s) = (int(input()), input())
(ans, lb, rw) = (s.count('.'), 0, s.count('.'))
for i in s:
	if i == '#':
		lb += 1
	elif i == '.':
		rw -= 1
	ans = min(ans, lb + rw)
print(ans)


n = int(input())
s = input()
w_cnt = s.count('.')
ans = [w_cnt]
b = 0
w = w_cnt
for i in s:
	if i == '#':
		b += 1
	else:
		w -= 1
	ans.append(b + w)
print(min(ans))


n = int(input())
s = input()
w = [0]
cnt = 0
for i in range(n):
	if s[i] == '#':
		cnt += 1
	w.append(cnt)
ans = len(s)
for i in range(n + 1):
	ans = min(ans, w[i] + (n - i - (w[-1] - w[i])))
print(ans)


n = int(input())
s = input()
ans = s.count('.')
num = ans
for c in s:
	if c == '.':
		num -= 1
	else:
		num += 1
	ans = min(ans, num)
print(ans)


n = int(input())
s = input()
w = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
	w[i] = w[i - 1] + 1 if s[i - 1] == '#' else w[i - 1]
	b[-i - 1] = b[-i] + 1 if s[-i] == '.' else b[-i]
print(min([x + y for (x, y) in zip(w, b)]))


_ = int(input())
S = input()
ans = 10 ** 9
cost = S.count('.')
for s in S:
	cost -= s == '.'
	ans = cost if cost < ans else ans
	cost += s == '#'
print(ans)


n = int(input())
s = input()
white = s.count('.')
black = 0
ans = white
for s_i in s:
	if s_i == '#':
		black += 1
	else:
		white -= 1
	ans = min(ans, white + black)
print(ans)


N = int(input())
S = input()
c = []
c.append(S.count('.'))
for i in range(1, N + 1):
	if S[i - 1] == '#':
		c.append(c[i - 1] + 1)
	if S[i - 1] == '.':
		c.append(c[i - 1] - 1)
print(min(c))


n = int(input())
s = input()
w = b = 0
mn = 0
for sk in s:
	if sk == '#':
		b += 1
	else:
		w -= 1
	if mn > b + w:
		mn = b + w
print(mn - w)


N = int(input())
S = input()
W = S.count('.')
B = 0
ans = B + W
for i in range(N):
	if S[i] == '.':
		W -= 1
	elif S[i] == '#':
		B += 1
	ans = min(ans, B + W)
print(ans)


n = int(input())
s = input()
bc = 0
cost = 0
for i in s:
	if i == '#':
		bc += 1
	elif bc > 0:
		bc -= 1
		cost += 1
print(cost)


N = int(input())
S = input()
ans = S.count('.')
ans2 = ans
for i in S:
	if i == '#':
		ans2 += 1
	else:
		ans2 -= 1
	ans = min(ans, ans2)
print(ans)


n = int(input())
s = input()
(x, ans) = ([0], n)
for i in s:
	if i == '#':
		x.append(x[-1] + 1)
	else:
		x.append(x[-1])
for i in range(n + 1):
	ans = min(ans, 2 * x[i] - x[-1] + n - i)
print(ans)


n = int(input())
s = input()
dp = [0] * (n + 1)
for i in range(1, n + 1):
	if s[i - 1] == '.':
		cnt = 0
	else:
		cnt = 1
	dp[i] = dp[i - 1] + cnt
ans = n
for i in range(n + 1):
	ans = min(ans, dp[i] + (n - i) - (dp[n] - dp[i]))
print(ans)


n = int(input())
a = list(map(lambda x: 1 if '#' == x else 0, list(input())))
mn = n - sum(a)
s = mn
for i in a:
	if i:
		s += 1
	else:
		s -= 1
	mn = min(mn, s)
print(mn)


import sys
input = sys.stdin.readline
N = int(input())
S = input()
w = S.count('.')
c = w
for i in range(N):
	if S[i] == '.':
		w -= 1
	else:
		w += 1
	c = min(c, w)
print(c)


N = int(input())
S = input()
(b, w, ans) = (0, 0, 0)
w = S.count('.')
ans = w
for i in S:
	if i == '#':
		b += 1
	else:
		w -= 1
	ans = min(b + w, ans)
print(ans)


n = int(input())
S = input()
b = 0
w = S.count('.')
res = w
for s in S:
	if s == '.':
		w -= 1
	else:
		b += 1
	res = min(res, b + w)
print(res)


N = int(input())
S = input()
w = S.count('.')
v = w
ans = w
for c in S:
	if c == '.':
		v -= 1
	else:
		v += 1
	ans = min(ans, v)
print(ans)


n = int(input())
s = input()
b = s.count('#')
w = s.count('.')
B = 0
ans = w
for i in range(n):
	if s[i] == '#':
		B += 1
	W = n - (i + 1) - (b - B)
	ans = min(ans, B + W)
print(ans)


N = int(input())
S = input()
tmp = 10 ** 9
cntB = S.count('#')
cnt = 0
for (i, s) in enumerate(S):
	if s == '#':
		tmp = min(tmp, cnt + N - i - (cntB - cnt))
		cnt += 1
print(min(cntB, tmp))


n = int(input())
s = input()
x = 0
y = s.count('.')
c = min(n - y, y)
for i in range(n):
	t = s[i] == '#'
	x += t
	y -= 1 - t
	c = min(c, x + y)
print(c)


n = int(input())
s = input()
w = s.count('.')
x = w
for i in s:
	if i == '#':
		x += 1
	else:
		x -= 1
	w = min(w, x)
print(w)


n = int(input())
minv = res = rd = 0
for e in input():
	if e == '.':
		res += 1
		rd -= 1
		minv = min(minv, rd)
	else:
		rd += 1
print(res + minv)


n = int(input())
s = input()
ans = s.count('.')
cnt = ans
for i in s:
	if i == '.':
		cnt -= 1
		ans = min(ans, cnt)
	else:
		cnt += 1
ans = min(ans, cnt)
print(ans)


n = int(input())
s = input()
best_cost = s.count('.')
cost = best_cost
for i in range(n):
	if s[i] == '#':
		cost += 1
	else:
		cost -= 1
	if cost < best_cost:
		best_cost = cost
print(best_cost)


n = int(input())
s = input()
ans = 0
blk = 0
for i in s:
	if i == '#':
		blk += 1
	elif blk > 0:
		ans += 1
		blk -= 1
print(ans)


N = int(input())
S = input()
lb = 0
rw = S.count('.')
ans = rw
for s in S:
	if s == '.':
		rw -= 1
	else:
		lb += 1
	ans = min(ans, lb + rw)
print(ans)


n = int(input())
s = list(input())
dp = [0] * (n + 1)
for i in range(n):
	if s[i] == '#':
		dp[0] += 1
for i in range(n):
	if s[n - i - 1] == '#':
		dp[i + 1] = dp[i] - 1
	else:
		dp[i + 1] = dp[i] + 1
print(min(dp))


N = int(input())
S = input()
res = dot = S.count('.')
sha = 0
for i in range(N):
	if S[i] == '#':
		sha += 1
	else:
		dot -= 1
	tmp = sha + dot
	res = min(res, tmp)
print(res)


n = int(input())
s = input()
r = s.count('.')
ans = [r]
for i in s:
	if i == '#':
		r += 1
	else:
		r -= 1
	ans.append(r)
print(min(ans))


n = int(input())
s = list(input())
rd = 0
for e in s:
	if e == '.':
		rd += 1
res = rd
for e in s:
	if e == '.':
		rd -= 1
	else:
		rd += 1
	res = min(res, rd)
print(res)


n = int(input())
s = input()
l = []
k = len(s.replace('.', ''))
ans = n - k
cnt = 0
for i in range(n):
	cnt += int(s[i] == '#')
	ans = min(ans, 2 * cnt + n - i - 1 - k)
print(ans)


n = int(input())
s = list(input())
kuro = 0
siro = s.count('.')
ans = siro
for i in range(n):
	if s[i] == '#':
		kuro += 1
	else:
		siro -= 1
	ans = min(ans, kuro + siro)
print(ans)


N = int(input())
S = input()
ws = [0]
for c in S:
	ws.append(ws[-1] + int(c == '.'))
ans = N
for (i, w) in enumerate(ws):
	rw = ws[-1] - w
	lb = i - w
	ans = min(ans, rw + lb)
print(ans)


n = int(input())
stones = input()
score = stones.count('.')
r = score
for i in range(n):
	if stones[i] == '.':
		r -= 1
	else:
		r += 1
	score = min(r, score)
print(score)


n = int(input())
s = list(input())
b = 0
w = s.count('.')
m = w
for i in range(n):
	if s[i] == '#':
		b += 1
	else:
		w -= 1
	m = min(m, b + w)
print(m)


N = int(input())
S = input()
ans = S.count('.')
printnum = ans
for c in S:
	if c == '.':
		printnum -= 1
	else:
		printnum += 1
	ans = min(ans, printnum)
print(ans)


N = int(input())
S = input()
count = [0] * (len(S) + 1)
count[0] = S.count('.')
for i in range(1, len(S) + 1):
	count[i] = count[i - 1] + (1 if S[i - 1] == '#' else 0) - (1 if S[i - 1] == '.' else 0)
print(min(count))


n = int(input())
s = list(input())
diff = s.count('.')
difflist = [diff]
for i in s:
	if i == '.':
		diff -= 1
	else:
		diff += 1
	difflist.append(diff)
print(min(difflist))


n = int(input())
s = str(input())
a = 0
b = s.count('.')
l = [b]
for i in range(n):
	if s[i] == '#':
		a += 1
	if s[i] == '.':
		b -= 1
	l.append(a + b)
print(min(l))


N = int(input())
S = list(input())
p = S.count('.')
q = 0
ans = p
for i in range(N):
	if S[i] == '#':
		q += 1
	else:
		p -= 1
	ans = min(ans, p + q)
print(ans)


n = int(input())
s_input = input()
check = s_input.count('.')
ans = check
for s in s_input:
	if s == '.':
		check -= 1
	else:
		check += 1
	ans = min(ans, check)
print(ans)


N = int(input())
S = input()
v = [S.count('.')]
for i in range(N):
	if S[i] == '#':
		v.append(v[i] + 1)
	else:
		v.append(v[i] - 1)
print(min(v))


n = int(input())
s = input()
w = s.count('.')
ans = w
for i in range(n):
	if s[i] == '#':
		w += 1
	if s[i] == '.':
		w -= 1
	ans = min(ans, w)
print(ans)


N = int(input())
S = input()
temp = S.count('.')
cnt = min(temp, N)
for i in range(N):
	if S[i] == '#':
		temp += 1
	else:
		temp -= 1
	cnt = min(temp, cnt)
print(cnt)


n = int(input())
s = input()
bs = 0
ws = s.count('.')
ans = ws
for c in s:
	if c == '.':
		ws -= 1
	else:
		bs += 1
	now = ws + bs
	if ans > now:
		ans = now
print(ans)


N = int(input())
S = input()
ans = cnt = S.count('.')
for s in S:
	if s == '#':
		cnt += 1
	else:
		cnt -= 1
	ans = min(ans, cnt)
print(ans)


n = int(input())
s = input()
b = 0
w = 0
for i in range(n):
	if s[i] == '.':
		b = min(b, w) + 1
	else:
		b = min(b, w)
		w += 1
print(min(b, w))


N = int(input())
S = input()
w = S.count('.')
b = 0
k = w
for i in range(N):
	if S[i] == '.':
		w -= 1
	else:
		b += 1
	k = min(k, w + b)
print(k)


s = input() == ''
b = [0]
for i in input():
	t = i == '.'
	b += [b[-1] + 1 - t * 2]
	s += t
print(min([i + s for i in b]))


N = int(input())
S = input()
b = 0
h = S.count('.')
m = h
for i in range(len(S)):
	if S[i] == '#':
		b += 1
	else:
		h -= 1
	if m > b + h:
		m = b + h
print(m)


n = int(input())
s = input()
k = 0
si = s.count('.')
m = si
for i in s:
	if i == '#':
		k += 1
	else:
		si -= 1
	m = min(m, k + si)
print(m)


input()
S = input()
dot = S.count('.')
ans = dot
count = 0
for s in S:
	if s == '#':
		count += 1
	else:
		dot -= 1
	ans = min(ans, count + dot)
print(ans)


from itertools import accumulate
input()
l = [0] + list(accumulate((c == '.' for c in input())))
print(min((i - x + l[-1] - x for (i, x) in enumerate(l))))


n = int(input())
s = list(input())
ans = 10 ** 6
w = [0]
for i in range(n):
	w.append(w[i] + (s[i] == '.'))
for i in range(n + 1):
	ans = min(ans, i - w[i] + (w[-1] - w[i]))
print(ans)


N = int(input())
S = input()
c_b = 0
c_w = S.count('.')
ans = c_w
for i in range(N):
	if S[i] == '#':
		c_b += 1
	else:
		c_w -= 1
	ans = min(c_b + c_w, ans)
print(ans)


n = int(input())
s = input()
ans = 0
w = s.count('.')
b = 0
ans = w + b
for c in s:
	if c == '#':
		b += 1
	else:
		w -= 1
	ans = min(ans, w + b)
print(ans)


n = int(input())
s = input()
(right, left) = (0, s.count('.'))
r = [left]
for i in range(n):
	if s[i] == '#':
		right += 1
	else:
		left -= 1
	r.append(right + left)
print(min(r))


(n, s) = open(0)
b = 0
a = w = s.count('.')
for x in s:
	b += x < '.'
	w -= x > '#'
	a = min(a, b + w)
print(a)


n = int(input())
s = input()
w = s.count('.')
b = 0
ans = w
for i in s:
	b += i == '#'
	w -= i == '.'
	ans = min(ans, w + b)
print(ans)


n = int(input())
s = input()
b = s.count('#')
w = s.count('.')
M = n
noww = 0
for i in range(n - 1):
	if s[i] == '.':
		noww += 1
		if s[i + 1] == '#':
			M = min(M, i - noww + 1 + w - noww)
print(min(b, w, M))


n = int(input())
s = input()
a = s.count('.')
g = [a]
b = 0
while b < n:
	if s[b] == '.':
		a -= 1
	else:
		a += 1
	g.append(a)
	b += 1
print(min(g))


N = int(input())
S = input()
a = 0
b = S.count('.')
num = min(N - b, b)
for i in range(N):
	x = S[i] == '#'
	a += x
	b -= 1 - x
	num = min(num, a + b)
print(num)


n = int(input())
s = list(input())
(b, w) = (0, 0)
for x in s:
	if x == '#':
		b += 1
	elif b > 0:
		w += 1
		b -= 1
print(w)


_n = int(input())
_s = input()
t = len([1 for s in _s if s == '.'])
c = []
c.append((t, 0))
for n in range(_n):
	if _s[n] == '#':
		t += 1
	else:
		t -= 1
	c.append((t, n + 1))
c.sort()
print(c[0][0])


n = int(input())
s = input()
w = s.count('.')
ww = 0
b = s.count('#')
bb = 0
ans = [bb + w]
for i in range(n):
	if s[i] == '.':
		w -= 1
		ww += 1
	else:
		b -= 1
		bb += 1
	ans.append(bb + w)
print(min(ans))


n = int(input())
S = input()
cW = S.count('.')
cB = 0
ans = cW
for i in range(n):
	if S[i] == '#':
		cB += 1
	else:
		cW -= 1
	ans = min(ans, cW + cB)
print(ans)


N = int(input())
S = input()
A = []
r = S.count('.')
result = r
for i in range(N):
	if S[i] == '#':
		r = r + 1
	else:
		r = r - 1
	result = min(result, r)
print(result)


n = int(input())
s = input()
sr = s[::-1]
ans = s.count('.')
num = ans
for i in range(n):
	if s[i] == '.':
		num -= 1
	else:
		num += 1
	ans = min(num, ans)
print(ans)


N = int(input())
S = input()
(one, d) = (0, 0)
for i in range(N):
	if S[i] == '#':
		one += 1
	elif d > one - (i + 1 - one):
		d = one - (i + 1 - one)
print(d + N - one)


N = int(input())
S = input()
tb = S.count('.')
tw = 0
mi = tb + tw
for i in range(N):
	if S[i] == '#':
		tw = tw + 1
	else:
		tb = tb - 1
	mi = min(mi, tb + tw)
print(mi)


N = int(input())
S = list(input())
ans = S.count('.')
cnt = ans
for i in range(N):
	if S[i] == '#':
		cnt += 1
	else:
		cnt -= 1
	ans = min(ans, cnt)
print(ans)


n = int(input())
s = input()
a = 0
ans = 0
for i in range(n):
	if s[i] == '.':
		ans += 1
a = ans
for i in range(n):
	if s[i] == '.':
		a -= 1
	else:
		a += 1
	if a < ans:
		ans = a
print(ans)


n = int(input())
s = input()
t = s.count('#')
for i in s:
	if i == '#':
		t -= 1
	else:
		t += 1
	t = min(t, s.count('#'))
print(t)


N = int(input())
S = list(input())
a = 0
b = 0
A = []
for i in range(N):
	if S[i] == '.':
		a += 1
	else:
		b += 1
	A.append(b - a)
A.sort()
ans = min(a, b, a + A[0])
print(ans)


n = int(input())
s = list(input())
m = n
counts = s[:].count('.')
m = min(n, counts)
for i in range(n):
	counts += s[i].count('#') - s[i].count('.')
	if m > counts:
		m = counts
print(m)


N = int(input())
S = input()
left = 0
right = S.count('.')
ans = left + right
for c in S:
	if c == '#':
		left += 1
	else:
		right -= 1
	ans = min(ans, left + right)
print(ans)


n = int(input())
s = input()
rw = s.count('.')
lb = 0
M = rw + lb
for i in range(n):
	if s[i] == '#':
		lb += 1
	else:
		rw -= 1
	M = min(M, rw + lb)
print(M)


input()
s = input()
cnt = s.count('.')
l = [cnt]
for i in s:
	cnt = cnt - 1 if i == '.' else cnt + 1
	l.append(cnt)
print(min(l))


n = int(input())
s = input()
tmp = 0
for i in range(n):
	if s[i] == '.':
		tmp += 1
ans = tmp
for i in range(n):
	if s[i] == '.':
		tmp -= 1
	else:
		tmp += 1
	ans = min(ans, tmp)
print(ans)


n = int(input())
s = str(input())
k = [s.count('.')]
for i in range(n):
	if s[i] == '#':
		k.append(k[i] + 1)
	else:
		k.append(k[i] - 1)
print(min(k))


N = int(input())
S = str(input())
x = S.count('.')
ans = x
for i in range(N):
	if S[i] == '#':
		x += 1
	else:
		x -= 1
	ans = min(ans, x)
print(ans)


N = int(input())
S = input()
A = []
a = S.count('.')
A.append(a)
for i in range(N):
	if S[i] == '#':
		a = a + 1
	else:
		a = a - 1
	A.append(a)
print(min(A))


N = int(input())
S = input()
black = 0
ans = 0
for s in S:
	if s == '#':
		black += 1
	elif black > 0:
		ans += 1
		black -= 1
print(ans)


n = int(input())
s = input()
w = 0
e = s.count('.')
result = e
for i in range(n):
	if s[i] == '#':
		w += 1
	else:
		e -= 1
	result = min(result, w + e)
print(result)


(_, s) = open(0)
c = s.count('.')
a = [c]
for i in s:
	c += i < '.' or -1
	a += (c,)
print(min(a))


n = int(input())
s = input()
sirocnt = s.count('.')
kurocnt = 0
ans = [sirocnt]
for i in range(n):
	if s[i] == '.':
		sirocnt -= 1
	else:
		kurocnt += 1
	ans.append(sirocnt + kurocnt)
print(min(ans))


input()
minv = res = rd = 0
for e in input():
	if e == '.':
		res += 1
		rd -= 1
		if rd < minv:
			minv = rd
	else:
		rd += 1
print(res + minv)


n = int(input())
s = input()
w = s.count('.')
m = w
for c in s:
	if c == '.':
		w -= 1
		if w < m:
			m = w
	elif c == '#':
		w += 1
print(m)


N = int(input())
S = input()
ws = S.count('.')
bs = 0
ans = ws + bs
for i in range(N):
	if S[i] == '#':
		bs += 1
	else:
		ws -= 1
	ans = min(ans, ws + bs)
print(ans)


n = int(input())
s = input()
r = s.count('.')
l = 0
c = 0
ans = r
for i in s:
	if i == '#':
		l += 1
	else:
		r -= 1
	if ans > l + r:
		ans = l + r
print(ans)


N = int(input())
S = input()
w_N = S.count('.')
ans = w_N
b = 0
w = 0
for (i, s) in enumerate(S):
	if s == '#':
		b += 1
	if s == '.':
		w += 1
	ans = min(ans, b + w_N - w)
print(ans)


n = int(input())
s = input()
b_c = 0
b_t = s.count('#')
ans = b_t
for i in range(n):
	a = b_c + (n - i) - (b_t - b_c)
	ans = min(a, ans)
	if s[i] == '#':
		b_c += 1
print(ans)


n = int(input())
s = input()
cost = s.count('.')
min = cost
for i in range(len(s)):
	if s[i] == '.':
		cost -= 1
	else:
		cost += 1
	if cost < min:
		min = cost
print(min)


n = int(input())
s = input()
k = 0
a = [0]
for t in s:
	if t == '#':
		k += 1
	a.append(k)
m = a[n]
p = n
for i in range(n + 1):
	p = min(p, a[i] + (n - i) - (m - a[i]))
print(p)


N = int(input())
S = list(str(input()))
WH = S.count('.')
ans = WH
for i in range(N):
	if S[i] == '#':
		WH += 1
	else:
		WH -= 1
	ans = min(ans, WH)
print(ans)


n = int(input())
s = list(input())
white = s.count('.')
diff = 0
diff_min = 0
for i in range(n):
	diff += 1 if s[i] == '#' else -1
	diff_min = min(diff, diff_min)
print(white + diff_min)


n = int(input())
l = input()
l1 = []
c = 0
for i in range(n):
	if l[i] == '#':
		c += 1
	l1.append(c)
l2 = []
for i in range(n):
	l2.append(n - (i + 1) - (c - l1[i]) + l1[i])
print(min(min(l2), c, n - c))


n = int(input())
S = list(input())
w = S.count('.')
b = 0
ans = w + b
for i in range(n):
	if S[i] == '.':
		w -= 1
	else:
		b += 1
	ans = min(ans, w + b)
print(ans)


N = int(input())
S = input()
A = [None] * (N + 1)
A[0] = 0
cnt = 0
for (i, s) in enumerate(S[::-1]):
	if s == '.':
		A[i + 1] = A[i] + 1
	else:
		A[i + 1] = A[i] - 1
		cnt += 1
print(min(A) + cnt)


n = int(input())
s = input()
l_b = 0
r_w = s.count('.')
ans = l_b + r_w
for x in s:
	if x == '#':
		l_b += 1
	else:
		r_w -= 1
	ans = min(ans, l_b + r_w)
print(ans)


n = int(input())
s = input()
s = s
ll = 0
rr = s.count('.')
result = ll + rr
for item in s:
	if item == '#':
		ll += 1
	else:
		rr -= 1
	result = min(result, ll + rr)
print(result)


N = int(input())
S = input()
white = S.count('.')
countb = 0
ans = white
for i in range(len(S)):
	if S[i] == '.':
		white -= 1
	else:
		countb += 1
	ans = min(ans, countb + white)
print(ans)


n = int(input())
dp = [0, 0]
for c in input():
	if c == '.':
		dp[1] += 1
	else:
		dp[1] = min(dp[1], dp[0])
		dp[0] += 1
print(min(dp))


n = int(input())
s = list(input())
ans = s.count('.')
temp = ans
for i in range(n):
	if s[i] == '#':
		temp += 1
	else:
		temp -= 1
	ans = min(ans, temp)
print(ans)


n = int(input())
S = list(input())
ans = S.count('.')
c = ans
for i in range(n):
	if S[i] == '#':
		c += 1
	else:
		c -= 1
	ans = min(ans, c)
print(ans)


n = int(input())
s = input()
r = s.count('.')
a = r
for i in range(n):
	if s[i] == '#':
		r += 1
	else:
		r -= 1
	a = min(a, r)
print(a)


from itertools import *
input()
s = input()
print(min(map(sum, zip(*[list(accumulate([0] + list(map(int, s.translate(str.maketrans('#.', '10'[::p]))))[::p]))[::p] for p in [1, -1]]))))


_ = input()
S = input().lstrip('.').rstrip('#')
n = len(S)
x = 0
y = S.count('.')
c = min(n - y, y)
for i in range(n):
	if S[i] == '#':
		x += 1
	else:
		y -= 1
	c = min(c, x + y)
print(c)


n = int(input())
s = input()
t = s.count('.')
r = 0
ans = t
for m in range(n):
	if s[m] == '.':
		t -= 1
	else:
		r += 1
	ans = min(ans, t + r)
print(ans)


n = int(input())
s = input()
w = s.count('.')
b = 0
ans = 10 ** 9
for i in range(n):
	if w + b < ans:
		ans = w + b
	if s[i] == '.':
		w -= 1
	else:
		b += 1
if w + b < ans:
	ans = w + b
print(ans)


N = int(input())
S = input()
ans = S.count('.')
l = [0, ans]
for i in range(N):
	if S[i] == '#':
		l[0] += 1
	else:
		l[1] -= 1
	if ans > sum(l):
		ans = sum(l)
print(ans)


N = int(input())
S = input()
b = S.count('#')
cnt = 0
result = N - b
for i in range(N):
	if S[i] == '#':
		cnt += 1
	result = min(result, cnt + N - i - (b - cnt) - 1)
print(result)


N = int(input())
S = str(input())
a = S.count('.')
r = a
for i in range(N):
	if S[i] == '#':
		a += 1
	else:
		a -= 1
	r = min(r, a)
print(r)


N = int(input())
S = list(map(lambda x: 1 * (x == '#'), input()))
L = M = S.count(0)
for i in range(N):
	if S[i]:
		M += 1
	else:
		M -= 1
		L = min(L, M)
print(L)


n = int(input())
s = input()
w = s.count('.')
b = 0
ret = w
for i in range(0, n):
	if s[i] == '.':
		w -= 1
	else:
		b += 1
	if ret > w + b:
		ret = w + b
print(ret)


N = int(input())
S = input()
blk = 0
white = S.count('.')
ans = white
for n in range(N):
	if S[n] == '#':
		blk += 1
	else:
		white -= 1
	ans = min(blk + white, ans)
print(ans)


n = int(input())
s = list(input())
bk = 0
wh = s.count('.')
cnt = wh
for i in range(n):
	if s[i] == '#':
		bk += 1
	else:
		wh -= 1
	cnt = min(cnt, bk + wh)
print(cnt)


n = int(input())
s = input()
l = 0
r = s.count('.')
m = r
for i in range(n):
	if s[i] == '.':
		r -= 1
	else:
		l += 1
	m = min(m, r + l)
print(m)


n = int(input())
s = input()
m = s.count('.')
c = (0, m)
for i in range(n):
	if s[i] == '#':
		c = (c[0] + 1, c[1])
	else:
		c = (c[0], max(c[1] - 1, 0))
	m = min(c[0] + c[1], m)
print(m)


n = int(input())
S = input()
c = S.count('.')
Min = c
for j in range(n):
	if S[j] == '#':
		c += 1
	else:
		c -= 1
	Min = min(Min, c)
print(Min)


n = int(input())
s = str(input())
x = s.count('.')
res = x
for c in s:
	if c == '#':
		x += 1
	else:
		x -= 1
	res = min(res, x)
print(res)


n = int(input())
s = input()
a = s.count('.')
b = 0
ans = a
for i in range(n):
	if s[i] == '#':
		b += 1
	else:
		a -= 1
	ans = min(ans, a + b)
print(ans)


n = int(input())
s = input()
c = [0]
for i in range(n):
	c.append(c[i] + (s[i] == '#'))
p = n
for i in range(n + 1):
	p = min(n - c[-1] + c[i] + (c[i] - i), p)
print(p)


N = int(input())
S = str(input())
white = S.count('.')
black = 0
ans = S.count('.')
for i in range(N):
	if S[i] == '.':
		white -= 1
	else:
		black += 1
	ans = min(ans, white + black)
print(ans)


n = int(input())
s = input()
w_right = s.count('.')
b_left = 0
ans = w_right
for i in range(n):
	if s[i] == '#':
		b_left += 1
	else:
		w_right -= 1
	ans = min(ans, w_right + b_left)
print(ans)