Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#ABC129 D
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H)]
U = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        elif L[i][j - 1] == 0:
            L[i][j] = 1            
        else:
            L[i][j] = L[i][j - 1] + 1
 
for i in range(H):
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif j == W - 1:
            R[i][j] = 1
        elif L[i][j + 1] == 0:
            R[i][j] = 1            
        else:
            R[i][j] = R[i][j + 1] + 1
            
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            continue
        elif i == 0:
            D[i][j] = 1
        elif L[i - 1][j] == 0:
            D[i][j] = 1            
        else:
            D[i][j] = D[i - 1][j] + 1
            
for j in range(W):
    for i in range(H - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif i == H - 1:
            U[i][j] = 1
        elif L[i + 1][j] == 0:
            U[i][j] = 1            
        else:
            U[i][j] = U[i + 1][j] + 1
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, (L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3))
print(ans)

### FIXED CODE ###

#ABC129 D
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H)]
U = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        elif L[i][j - 1] == 0:
            L[i][j] = 1            
        else:
            L[i][j] = L[i][j - 1] + 1
            
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif j == W - 1:
            R[i][j] = 1
        elif L[i][j + 1] == 0:
            R[i][j] = 1            
        else:
            R[i][j] = R[i][j + 1] + 1

for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            continue
        elif i == 0:
            D[i][j] = 1
        elif L[i - 1][j] == 0:
            D[i][j] = 1            
        else:
            D[i][j] = D[i - 1][j] + 1
            
    for i in range(H - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif i == H - 1:
            U[i][j] = 1
        elif L[i + 1][j] == 0:
            U[i][j] = 1            
        else:
            U[i][j] = U[i + 1][j] + 1
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, (L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        for wa in range(S+1):
            DP[i][wa] = 2*DP[i-1][wa]
            DP[i][wa] %= MOD
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
if N <= 9:
    print(N)
    exit()

tot_count = 0
for af in map(str, range(1, 10)):
    for bf in map(str, range(1, 10)):
        a_count = 0
        b_count = 0
        for a in map(str, range(1, N + 1)):
            if a[0] == af and a[-1] == bf:
                a_count += 1
        for b in map(str, range(1, N + 1)):
            if b[0] == bf and b[-1] == af:
                b_count += 1

        tot_count += a_count * b_count

print(tot_count)

### FIXED CODE ###


N = int(input())
if N <= 9:
    print(N)
    exit()

tot_count = 0
for af in map(str, range(1, 10)):
    for bf in map(str, range(1, 10)):
        a_count = 0
        b_count = 0
        for a in map(str, range(1, N + 1)):
            if a[0] == af and a[-1] == bf:
                a_count += 1
        for b in map(str, range(1, N + 1)):
            if b[0] == bf and b[-1] == af:
                b_count += 1

        tot_count += a_count * b_count

print(tot_count)
### BUGGY CODE ###

N,A,B = map(int,input().split())
ans = 0
while N >= A+B:
  N = N -A-B
  ans += 1
if N >= A:
  print(A*(ans+1))
else:
  print(A*ans+N)

### FIXED CODE ###

N,A,B = map(int,input().split())
a = N // (A+B)
b = N - a*(A+B)
if b >= A:
  print(A*(a+1))
else:
  print(A*a+b)
### BUGGY CODE ###

H, W = [int(a) for a in input().split()]
S = [None] * H

for i in range(H):
    S[i] = input()


light = [[[0, 0] for _ in range(W)] for _ in range(H)]
ans = 0

# 横を調べる
for i in range(H):
    j = 0
    while j < W:
        horizontal = 0
        while j < W and S[i][j] == '.':
            horizontal += 1
            j += 1
        for jj in range(horizontal):
            light[i][j - 1 - jj][0] = horizontal
        while j < W and S[i][j] == '#':
            j += 1

# 縦を調べる
for j in range(W):
    i = 0
    while i < H:
        vertical = 0
        while i < H and S[i][j] == '.':
            vertical += 1
            i += 1
        for ii in range(vertical):
            light[i - 1 - ii][j][1] = vertical
            ans = max( ans, sum(light[i - 1 - ii][j]) - 1)
        while i < H and S[i][j] == '#':
            i += 1

print(ans)

### FIXED CODE ###

H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]

ans = 0

# L, R, Uを求める
for i in range(H):
    for j in range(W):

        if S[i][j] == '#':
            pass  # L, R, Uは0で初期化されている
        else:
            # Uを求める
            if i == 0:  U[i][j] = 1
            else:       U[i][j] = U[i - 1][j] + 1

            # Lを求める
            if j == 0:  L[i][j] = 1
            else:       L[i][j] = L[i][j - 1] + 1

        # Rを求める
        if S[i][W - 1 - j] == '#':
            pass
        elif j == 0:
            R[i][W - 1 - j] = 1
        else:
            R[i][W - 1 - j] = R[i][W - j] + 1

# Dを求める
for i in range(H - 1, -1, -1):
    for j in range(W):
        if S[i][j] == '#':  pass
        elif i == H - 1:    D[i][j] = 1
        else:               D[i][j] = D[i + 1][j] + 1
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)
### BUGGY CODE ###

from fractions import gcd
import itertools

def answer():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        # divisors.sort()
        return divisors

    a, b = map(int, input().split())
    g = gcd(a, b)
    divisors = make_divisors(g)
    set_divisors = set(divisors)

    for div1, div2 in itertools.combinations(divisors[1:], 2):
        item = div1 * div2 / gcd(div1, div2)
        if item in set_divisors:
            set_divisors.remove(item)

    print(len(set_divisors))


if __name__ == '__main__':
    answer()


### FIXED CODE ###

from fractions import gcd

def answer():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        divisors.sort()
        return divisors

    a, b = map(int, input().split())
    g = gcd(a, b)
    divisors = make_divisors(g)

    length = len(divisors)
    removed = 1

    for i in range(1, length):
        d1 = divisors[i]
        for d2 in divisors[i:-1]:
            if d1 * d2 in divisors:
                divisors.remove(d1*d2)
                removed += 1
        if i + removed >= length:
            break

    print(length - removed + 1)


if __name__ == '__main__':
    answer()
### BUGGY CODE ###

n=input()
n=int(n)
l=[]
for i in range(n):
    x=input()
    x=int(x)
    l.append(x)
for i in range(n):
    x=l[0]
    del l[0]
    print(max(l))
    l.append(x)
    


### FIXED CODE ###

n=input()
n=int(n)
l=[]
for i in range(n):
    x=input()
    x=int(x)
    l.append(x)
ans=max(l)
x=l.index(ans)
del l[x]
sec=max(l)
for i in range(n):
    if i==x:
        print(sec)
        continue
    print(ans)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

resultCount = 0
for i in range(N):
    isMitasu = True
    for j in range(i):
        if P[i] > P[j]:
            isMitasu = False
    if isMitasu:
        resultCount += 1
print(resultCount)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))


# 最小値更新して越えてたらアウト
resultCount = 0
minNum = P[0]
for i in range(N):
    isMitasu = True
    if i != 0:
        if P[i] > minNum:
            isMitasu = False
        else:
            # 最小値更新
            minNum = P[i]
    if isMitasu:
        resultCount += 1
print(resultCount)
### BUGGY CODE ###


def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = []
  min_maxs.insert(0, [A[-1], A[-1]])

  for a in reversed(A[:-1]):
    min_maxs.insert(0, [min_maxs[0][0] // 2 + a, min_maxs[0][1] + a])
  # print(min_maxs)
  # max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # # 各 depth における最小値
  # min_node_in_depth = [0] * (len(A))
  # min_node_in_depth[-1] = max_node_in_depth[-1]
  # index = -1
  # for i in range(1, len(A)):
  #   min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
  #   index = index - 1

  # for min_max in min_maxs:
  #   print(min_max)

  result = 1
  recent = 1
  for min_max, a in zip(min_maxs[1:], A):
    num_of_node = (recent - a) * 2
    # print(min_max, num_of_node)
    if num_of_node < min_max[0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_max[1])
    recent = min(num_of_node, min_max[1])

  print(result)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = {}
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]
  # print(min_maxs)
    # min_maxs.insert(0, [min_maxs[0][0] // 2 + a, min_maxs[0][1] + a])
  # print(min_maxs)
  # max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # # 各 depth における最小値
  # min_node_in_depth = [0] * (len(A))
  # min_node_in_depth[-1] = max_node_in_depth[-1]
  # index = -1
  # for i in range(1, len(A)):
  #   min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
  #   index = index - 1

  # for min_max in min_maxs:
  #   print(min_max)

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    # print(min_max, num_of_node)
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

n = int(input())
as_ =  list(map(int, input().split()))

l = as_[0:n]
m = as_[n:2*n]
r = as_[2*n:3*n]
r = [(-1)*a for a in r]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  else:
    l_max = sum(l)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

d = [0]*(n+1)
for i in range(n+1):
  d[i] = l_maxs[i] + r_mins[n-i]
print(max(d))

### FIXED CODE ###

n = int(input())
as_ =  list(map(int, input().split()))

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

sl = sum(l)
sr = sum(r)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    a = heapq.heappop(l)
    sl += m[j] -a
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    b = heapq.heappop(r)
    sr += m[k]*(-1) - b
    
  l_maxs[i] = sl
  r_mins[i] = sr

#print(l_maxs)
#print(r_mins)

print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))
### BUGGY CODE ###

N, Y = map(int, input().split())

answer = [-1, -1, -1]

for i in range(N+1):
    for j in range(N+1):
        if i+j+(N-i-j) == N and i*10000 + j*5000 + (N-i-j)*1000 == Y and N-i-j>=0:
            answer[0] = i
            answer[1] = j
            answer[2] = N-i-j

print("{} {} {}".format((answer[0]),(answer[1]),(answer[2])))



### FIXED CODE ###

N, Y = map(int, input().split())

answer = [-1, -1, -1]

for i in range(N+1):
    for j in range(N+1):
        k = N-i-j
        if k < 0:
            continue
        if i+j+k == N and i*10000 + j*5000 + k*1000 == Y:
            answer[0] = i
            answer[1] = j
            answer[2] = N-i-j

print("{} {} {}".format((answer[0]),(answer[1]),(answer[2])))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
hL = [0]*(10**5+k)
for i in range(n):
    hL[i] = h[i]

dp = [10**10]*(10**5+k)
dp[0] = 0
for i in range(0,n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))

print(dp[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
hL = list(map(int, input().split()))

dp = [10**10]*(n)
dp[0] = 0
for i in range(0,n):
    if i+k<=n-1:
        for j in range(1,k+1):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))
    else:
        for j in range(1, n-i):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))

print(dp[n-1])
### BUGGY CODE ###

k=int(input())


cnt=0
for i in range(1,k):
    for j in range(1,k+2):
        
            
        if i*j<k:
            cnt+=1
        else:
            break
print(cnt)

### FIXED CODE ###

k=int(input())


cnt=0
if k>6:
    for i in range(7,k):
        for j in range(1,k):
            
                
            if i*j<k:
                cnt+=1
            else:
                break
print(cnt+k-1+((k-1)//2)+((k-1)//3)+((k-1)//4)+((k-1)//5)+((k-1)//6))
### BUGGY CODE ###

# 2019-11-13 08:30:54(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]
    a.sort()

    bc = []
    for _ in range(m):
        bi, ci = [int(x) for x in sys.stdin.readline().split()]
        bc.append([bi, ci])
    
    bc.sort(reverse=True, key=lambda x: x[1])
    
    for i in range(m):
        index = bi_l(a, bc[i][1])
        if index == 0:
            break
        else:
            if index > bc[i][0]:
                a = [bc[i][1]] * bc[i][0] + a[bc[i][0]:]
            else:
                a = [bc[i][1]] * index + a[index:]
            a.sort()

    print(sum(a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-13 08:30:54(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]

    a = list(collections.Counter(a).items())

    for _ in range(m):
        b, c = [int(x) for x in sys.stdin.readline().split()]
        a.append((c,b))
    
    a.sort(reverse=True)
    
    total = 0
    count = 0
    for i in range(n+m): # max
        select = a[i]
        for j in range(select[1], 0, -1):
            if count + j > n:
                continue
            else:
                count += j
                total += select[0] * j
                break
        if count == n:
            break
    
    print(total)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
    

if len(c) <= k:
    print(0)
else:
    sum = 0
    for i in range(k, len(c)):
        sum += c.most_common()[i][1]
    print(sum)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
d = c.most_common()
if len(c) <= k:
    print(0)
else:
    sum = 0
    for i in range(k, len(c)):
        sum += d[i][1]
    print(sum)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A=[0]+A
B=[]
for i in range(N):
  k=N-i 
  c=0
  for j in range(k,N+1,k):
    if j in B:
      c+=1
      c%=2
  if A[k]!=c:
    B.append(k)
    
print(len(B))
for i in range(len(B)):
  print(B[-(i+1)])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=[0]+A
B=[0]*(N+1)
for i in range(N):
  k=N-i 
  c=0
  for j in range(k,N+1,k):
    c+=B[j]
    c%=2
  if A[k]!=c:
    B[k]=1
    
print(sum(B))
for i in range(len(B)):
  if B[i]==1:
    print(i)
### BUGGY CODE ###

n, k = map(int, input().split())
xv, yv = [], []
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xv.append(x)
    yv.append(y)
    xy.append((x, y))

xv = sorted(xv)
yv = sorted(yv)
ans = (xv[n-1] - xv[0]) * (yv[n-1] - yv[0])
for l in range(n):
    lx = xv[l]
    for r in range(l+1, n):
        rx = xv[r]
        for b in range(n):
            by = yv[b]
            for t in range(b+1, n):
                ty = yv[t]
                cnt = 0
                for x, y in xy:
                    if lx <= x <= rx and by <= y <= ty:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (rx - lx)*(ty - by))
print(ans)



### FIXED CODE ###

n, k = map(int, input().split())
xv, yv = [], []
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xv.append(x)
    yv.append(y)
    xy.append((x, y))

xv = sorted(xv)
yv = sorted(yv)
ans = (xv[n-1] - xv[0]) * (yv[n-1] - yv[0])
for l in range(n):
    lx = xv[l]
    for r in range(l+1, n):
        rx = xv[r]
        for b in range(n):
            by = yv[b]
            for t in range(b+1, n):
                ty = yv[t]
                cnt = 0
                for x, y in xy:
                    if lx <= x <= rx and by <= y <= ty:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (rx - lx)*(ty - by))
print(ans)
### BUGGY CODE ###

import sys

target = int(input())

list_After = [str(n) for n in range(10)]
list_Before = []

count = 9

while 1:
  list_Before = list_After
  list_After = []
  for i in range(10):
    flag = 0
    for element in list_Before:
      if (abs(i - int(element[0])) >= 2) & (flag == 1):
        break
      elif abs(i - int(element[0])) >= 2:
        continue
      else:
        flag = 1
        list_After.append(str(i) + element)
        if i != 0:
          count += 1
          if count == target:
            print(str(i) + element)
            sys.exit()


### FIXED CODE ###

import queue
target = int(input())

q = queue.Queue()

for i in range(1,10):
  q.put(str(i))


for cnt in range(1, target):
  num = q.get()
  mod = int(num) % 10
  
  if mod == 0:
    q.put(num + "0")
    q.put(num + "1")
  elif mod == 9:
    q.put(num + "8")
    q.put(num + "9")
  else:
    q.put(num + str(mod - 1))
    q.put(num + str(mod))
    q.put(num + str(mod + 1))

print(q.get())
### BUGGY CODE ###

s = input()
q = int(input())
q_list = [list(input().split()) for _ in range(q)]

flag = 1

for q in q_list:
    if q[0] == '1':
        flag *= -1
    else:
        if flag == 1:
            if q[1] == '1':
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if q[1] == '2':
                s = q[2] + s
            else:
                s = s + q[2]
if flag == 1:            
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
q_list = [list(input().split()) for _ in range(q)]

top_list = []
end_list = []

flag = 1

for q in q_list:
    if q[0] == '1':
        flag *= -1
    else:
        if flag == 1:
            if q[1] == '1':
                top_list.append(q[2])
            else:
                end_list.append(q[2])
        else:
            if q[1] == '2':
                top_list.append(q[2])
            else:
                end_list.append(q[2])
if flag == 1:            
    print(''.join(top_list[::-1]) + s + ''.join(end_list))
else:
    print(''.join(end_list[::-1]) + s[::-1] + ''.join(top_list))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(n, s):
    b = '#'
    w = '.'
    last = ''

    s2 = [ c == '#' for c in s]
    ans =[sum(s2[:i])+n-i-sum(s2[i:]) for i in range(n+1)]
    return min(ans)

def main():
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    ans = calc(n, s)
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(n, s):
    s2 = [ c == '#' for c in s]
    total = sum(s2)
    _min = min(total, n-total)
    tr = 0
    for i,c in enumerate(s2):
        if c:
            tr += 1
        op = 2*tr+n-(i+1)-total
        if op < _min:
            _min = op

    return _min

def main():
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    ans = calc(n, s)
    print(ans)
    
if __name__=='__main__':
    main()