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

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(r2 + c2 + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans += comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)
    ans %= MOD

print(ans % MOD)

### FIXED CODE ###

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(r2 + c2 + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

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

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        up = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

S = input()
Q = int(input())
for _ in range(Q):
  a, *b = input().split()
  if a == "1":
    S = S[::-1]
  else:
    if b[0] == "1":
      S = b[1] + S
    else:
      S += b[1]
print (S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
f = 0
for _ in range(Q):
  a, *b = input().split()
  f += int(a)
  if a == "2":
    if (int(b[0]) + f) % 2 == 1 :
      S.appendleft(b[1])
    else:
      S.append(b[1])
D = list(S)
print ("".join(D) if f % 2 == 0 else "".join(D[::-1]))
### BUGGY CODE ###

n = int(input())

a = []
s = [0] * n
a.append(input().split())

for i in range(n-1):
    a[0][i] = int(a[0][i])

for i in range(n-1):
    for j in range(n):
        if j == a[0][i]:
            s[j-1] += 1

for i in range(n):
    print(s[i])


### FIXED CODE ###

n = int(input())

a = []
s = [0] * n
a.append(input().split())

for i in range(n - 1):
    a[0][i] = int(a[0][i])
    s[a[0][i]-1] += 1

for i in range(n):
    print(s[i])
### BUGGY CODE ###

class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and self.a[l] > self.a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and self.a[r] > self.a[largest]:
            largest = r
        if largest != i:
            self.a[i], self.a[largest] = self.a[largest], self.a[i]
            self.maxHeapify(largest)

    def extract(self):
        if self.h < 1:
            return -1
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -1
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [-1] * 2000000 * 1
    x = MaxHeap(a, 0)
    while True:
        com = input().rstrip()
        if com == "end":
            break
        elif com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("extract"):
            print(x.extract())
    

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

def main():
  H,N = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  ab = min(AB,key = lambda x:x[1])
  INF = float('inf')
  dp = [INF]*(H+1)
  mi_a = ab[0]
  mi_b = ab[1]
  dp[0] = 0
  for i in range(1,H+1):
    if i<=mi_a:
      dp[i]=mi_b
    else:
      mi = float('inf')
      for a,b in AB:
        mi = min(mi,dp[max(0,i-a)]+b)
      if dp[i]>mi:
        dp[i] = mi

  print(dp[H])
  
main()

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [INF]*(H+1)
dp[0] = 0
for i in range(1,H+1):
  for k in AB:
    a = k[0]
    b = k[1]
    tmp = max(0,i-a)
    dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])
### BUGGY CODE ###

import numpy as np
from itertools import combinations_with_replacement

def main():
    k = int(input())
    res = 0
    for c in combinations_with_replacement(range(1,k+1), 3):
        tmp = np.gcd.reduce(c)
        l = len(set(c))
        mul = 1
        if l == 2:
            mul = 3
        elif l == 3:
            mul = 6
        res += tmp * mul
    print(res)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np
from itertools import combinations

def main():
    k = int(input())
    res = 0
    memo = np.zeros((k+1, k+1), int)
    for i in range(1, k+1):
        for j in range(i, k+1):
            tmp = np.gcd(i,j)
            memo[i][j] = tmp
            memo[j][i] = tmp

    for i in range(1, k+1):
        res += i 

    for c in combinations(range(1,k+1),2):
        ab = memo[c[0], c[1]]
        res += ab * 6

    for c in combinations(range(1,k+1), 3):
        ab = memo[c[0], c[1]]
        abc = memo[ab, c[2]]
        res += abc * 6
    print(res)


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

from collections import Counter

S = list(map(int,list(input())))
n = len(S)

dp = [0]*(n+1)

dp[n-1] = S[-1]

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+(10**(n-i-1))*(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)


### FIXED CODE ###

from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+pow(10,n-i-1,2019)*int(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

ans = 0
balls = N
for r in range(0,(balls//R)+1):
  balls_r = balls - R*r
  for g in range(0,(balls//G)+1):
    balls_g = balls_r - G*g
    if (balls_g >= 0) and (balls_g % B == 0):
      ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())

ans = 0
balls = N
for r in range(0,(balls//R)+1):
  balls_r = balls - R*r
  for g in range(0,(balls_r//G)+1):
    balls_g = balls_r - G*g
    if (balls_g >= 0) and (balls_g % B == 0):
      ans += 1

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

N,M=map(int,input().split())
mod = 10**9+7
def fact_list(a):
  ans = [1]
  for i in range(1,a+1):
    ans.append(ans[-1]*i % mod)
  return ans

factlist = fact_list(M)

def comb_mod(a,b):
  return (factlist[a]*pow(factlist[b],mod-2,mod)*pow(factlist[a-b],mod-2,mod) )% mod

def permu_mod(a,b):
  return (factlist[a]*pow(factlist[a-b],mod-2,mod) % mod)

ans = 0
for i in range(N+1):
  ans += comb_mod(N,i)*(-1)**i*permu_mod(M,i)*permu_mod(M-i,N-i)**2 
  ans = ans % mod
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
mod = 10**9+7
def fact_list(a):
  ans = [1]
  for i in range(1,a+1):
    ans.append(ans[-1]*i % mod)
  return ans

factlist = fact_list(M)

def comb_mod(a,b):
  return (factlist[a]*pow(factlist[b],mod-2,mod)*pow(factlist[a-b],mod-2,mod) )% mod

def permu_mod(a,b):
  return (factlist[a]*pow(factlist[a-b],mod-2,mod) % mod)

ans = 0
for i in range(N+1):
  ans += comb_mod(N,i)*(-1)**i*permu_mod(M,i)*permu_mod(M-i,N-i)**2 
  ans = ans % mod
print(ans)
### BUGGY CODE ###

n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(min(10**5,n)):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
        a = int(input())
        A.append(a)

remain = N
color = 0

while remain != 0:
        num = A[0]
        B = []
        remain -= 1
        for i in range(1, len(A)):
                if num >= A[i]:
                        B.append(A[i])
                else:
                        num = A[i]
                        remain -= 1
        
        color += 1
        A = B

print(color)





### FIXED CODE ###

N = int(input())
A = [-1 for i in range(N)]

color = 1
A[0] = int(input())


def search(A, color, a):
        left = 0
        right = color - 1
        signal = 0
        while left < right:
                mid = (left + right) // 2
                if A[mid] == a - 1:
                        return mid
                        signal = 1
                elif a <= A[mid]:
                        left = mid + 1
                else:
                        right = mid
        if signal == 0:
                return left


for i in range(N - 1):
        
        a = int(input())
        num = search(A, color, a)
        if num == color - 1 and a <= A[num]:
                A[color] = a
                color += 1
        else:
                A[num] = a

print(color)
### BUGGY CODE ###

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)
    return divisors

N = int(input())
a = list(map(int, input().split()))
b = []
multiple = [[i] for i in range(1,N+1)]
balls = [0] * N

for i in range(N,0,-1):
    if balls[i-1] % 2 != a[i-1]:
        for x in make_divisors(i):
            balls[x-1] += 1
        b.append(i)
print(len(b))
print(*b)

### FIXED CODE ###

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)
    return divisors

N = int(input())
a = list(map(int, input().split()))
b = []
multiple = [[i] for i in range(1,N+1)]
balls = [0] * N

for i in range(N,0,-1):
    if balls[i-1] % 2 != a[i-1]:
        for x in make_divisors(i):
            balls[x-1] += 1
        b.append(i)
print(len(b))
print(*b)
### BUGGY CODE ###

n = int(input())

ans=0
for i in range(n-1):
    ans += (i+1)
print(ans)

### FIXED CODE ###

n = int(input())
print((n-1)*n//2)
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

a = [0]
b = [0]
for i in range(len(A)):
    a.append(a[i] + A[i])

for i in range(len(B)):
    b.append(b[i] + B[i])


# print(a)
# print(b)


ans = 0

for i_n in range(n + 1):
    if a[i_n] > k:
        break

    for j_n in range(m + 1):
        if a[i_n] + b[j_n] <= k:
            # print(i_n, j_n, a[i_n] + b[j_n])
            ans = max(ans, i_n + j_n)

print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

a = [0]
b = [0]
for i in range(len(A)):
    a.append(a[i] + A[i])

for i in range(len(B)):
    b.append(b[i] + B[i])


# print(a)
# print(b)

j_n = m
ans = 0

for i_n in range(len(a)):
    if a[i_n] > k:
        break

    while b[j_n] > k - a[i_n]:
        j_n -= 1

    ans = max(ans, i_n + j_n)

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

N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

count = []
for i in range(1,N + 1):
    count.append(S[0:i].count("AC"))


for i in range(0,Q):
    l,r = map(int,input().strip().split())
    if r > len(count):
        r = len(count)
    print(count[r - 1] - count[l - 1])



### FIXED CODE ###

N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

count = [0]
for i in range(0,N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        count.append(count[i] + 1)
    else:
        count.append(count[i])


for i in range(0,Q):
    l,r = map(int,input().strip().split())
    if r > len(count):
        r = len(count)
    if l == 0:
        l += 1
    print(count[r - 1] - count[l - 1])
### BUGGY CODE ###

from collections import Counter
from copy import copy

N, Q = map(int, input().split())
c = list(map(int, input().split()))

cs = []

counter = Counter()
for ci in c:
    counter.update([ci])
    c2 = copy(counter)
    cs.append(c2)

for i in range(Q):
    l, r = map(int, input().split())
    c3 = copy(cs[r-1])
    if l > 1:
        c3.subtract(cs[l-2])
        c3 = +c3
    print(len(c3))


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

    def sum(self, i):  # sum in [0, i)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
c = list(map(int, input().split()))

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l-1, r-1, i])

lr.sort(key=lambda x: x[1])

rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]]+1, -1)
    rightest[c[i]] = i
    bit.add(i+1, 1)

    while current_q < Q and lr[current_q][1] == i:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1] + 1) - bit.sum(lr[current_q][0])
        current_q += 1

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

from math import *

def Prime_Factorization(M):
    factor_count_list = []
    root_M = int(sqrt(M))

    while root_M > 1:
        root_M = int(sqrt(M))

        for i in range(2, root_M + 1):
            e = 0
            while M % i == 0:
                e += 1
                M = M // i
            if e > 0:
                factor_count_list.append(e)
                break
        else:
            break

    if M > root_M:
        factor_count_list.append(1)

    return factor_count_list

def comb(num_object, num_bar):
    return factorial(num_object) // (factorial(num_object - num_bar) * factorial(num_bar))

def all_comb(N, factor_count_list):
    ans = 1
    for factor in factor_count_list:
        ans = (ans * comb(factor + N - 1, factor)) % (10 ** 9 + 7)
    return ans

def main():
    N, M = map(int, input().split())
    factor_count_list = Prime_Factorization(M)

    if (factor_count_list == 1):
        print(N)
    else:
        print(all_comb(N, factor_count_list))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import *

def Prime_Factorization(M):
    factor_count_list = []
    root_M = int(sqrt(M))

    while root_M > 1:
        root_M = int(sqrt(M))

        for i in range(2, root_M + 1):
            e = 0
            while M % i == 0:
                e += 1
                M = M // i
            if e > 0:
                factor_count_list.append(e)
                break
        else:
            break

    if M > root_M:
        factor_count_list.append(1)

    return factor_count_list

def comb(num_object, num_bar):
    numerator = 1

    for i in range(num_bar):
        numerator = (numerator * (num_object - i))

    return  numerator // factorial(num_bar)

def all_comb(N, factor_count_list):
    ans = 1
    for factor in factor_count_list:
        ans = (ans * comb(factor + N - 1, factor)) % (10 ** 9 + 7)
    return ans

def main():
    N, M = map(int, input().split())
    factor_count_list = Prime_Factorization(M)

    print(all_comb(N, factor_count_list))

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

str=input()
count=0
for i in range(4,len(str)+1):
    for j in range(0,len(str)-i+1):
        if int(str[j:i+j])%2019==0:
            count=count+1
print(count)

### FIXED CODE ###

s=input()
b=[0]*2019
b[0]=1
now=0
m=2019
c=1
ans=0
for i in range(len(s)-1,-1,-1):
    now+=int(s[i])*c
    now=now%m
    c=c*10
    ans=ans+b[now]
    b[now]=b[now]+1
    c=c%m

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

P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])

### FIXED CODE ###

P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])
### BUGGY CODE ###

#coding:utf-8
N = int(input())
S = input()
ans = 1000000
for i in range(N+1):
    l = S[:i]
    r = S[i:]
    #print (l,r)
    cnt = l.count("#")+r.count(".")
    #print (cnt)
    if cnt < ans:
        ans = cnt
print (ans)


### FIXED CODE ###

#coding:utf-8
N = int(input())
S = input()
lb = 0
lw = 0
rb = S.count("#")
rw = S.count(".")
ans = lb + rw
for i in range(N):
    if S[i] == "#":
        lb += 1
        rb -= 1
    else:
        lw += 1
        rw -= 1
    ans = min(ans,lb+rw)
print (ans)