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

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

lcm = 1
for f in d.keys():
    lcm *= f ** d[f]

ans = (lcm * cnt_1)%mod
# 1のかず
for factors in factors_list:
    cnt = 1
    for f in d.keys():
       cnt *= f ** (d[f]-factors[f])
       cnt %= mod
    ans += cnt
    ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

import fractions
from functools import reduce
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
 
N = int(input())
A = list(map(int,input().split()))
fact = [1]*(10**7+10)
rfact = [1]*(10**7+10)
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
value = lcm_list(A)
ans = 0
for i in range(N):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)

### FIXED CODE ###

import fractions
from functools import reduce
# Python3 program to compute LCM of 
# array elements modulo M
MAX = 10**6+1
mod = 1000000007
prime = [0 for i in range(MAX)] 
max_map = dict() 
# function to return a^n 
def power(a, n):
	if n == 0: 
		return 1
	p = power(a, n // 2) % mod
	p = (p * p) % mod
	if n & 1: 
		p = (p * a) % mod
	return p 

# function to find the smallest prime
# factors of numbers upto MAX
def sieve(): 
	prime[0], prime[1] = 1, 1
	for i in range(2, MAX): 
		if prime[i] == 0: 
			for j in range(i * 2, MAX, i): 
				if prime[j] == 0: 
					prime[j] = i 
			prime[i] = i 

# function to return the LCM modulo M 
def lcmModuloM(arr, n): 
	for i in range(n): 
		num = arr[i] 
		temp = dict() 
		# temp stores mapping of prime factors 
		# to its power for the current element 
		while num > 1:
			# factor is the smallest prime
			# factor of num
			factor = prime[num]
			# Increase count of factor in temp
			if factor in temp.keys():
				temp[factor] += 1
			else:
				temp[factor] = 1
			# Reduce num by its prime factor
			num = num // factor
		for i in temp:
			# store the higest power of every prime
			# found till now in a new map max_map
			if i in max_map.keys():
				max_map[i] = max(max_map[i], temp[i])
			else: 
				max_map[i] = temp[i]
	ans = 1
	for i in max_map:
		ans = (ans * power(i, max_map[i])) % mod
	return ans
# Driver code
sieve()
X = int(input())
A = list(map(int,input().split()))
N = max(A)
value = lcmModuloM(A, X)
ans = 0
for i in range(X):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)
### BUGGY CODE ###

N,K = [ int(it) for it in input().split() ]
S = [ int(it) for it in input() ]

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  ds = sum( li[i*2:i*2+2*K+1] )
  s = max(s,ds)
print (s)

### FIXED CODE ###

N,K = [ int(it) for it in input().split() ]
S = [ int(it) for it in input() ]

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
lis = [0]*(len(li)+1)
for i in range(len(li)):
  lis[i+1]=lis[i]+li[i]
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  a = min(i*2,len(li))
  b = min(i*2+2*K+1,len(li))

  ds2 = lis[b]-lis[a]
  s = max(s,ds2)
print (s)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
result = 1

for number in A:
  result *= number
  if (result == 0):
    print(0)
    break

if (result > 10 ** 18):
  print(-1)
elif (result != 0):
  print(result)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
result = 1

if 0 in A:
  print(0)
else:
  for number in A:
    result *= number
    if (result > 10 ** 18):
      print(-1)
      break
  else:
    print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        ai = a[i]-1
        bi = b[i]-1
        ci = cost[i]
        link[ai].append((bi, ci))
        link[bi].append((ai, ci))

    def dfs(v, c, p):
        for nv in link[v]:
            nv0 = nv[0]
            if nv0 != p:
                cost[nv0] += c
                dfs(nv0, cost[nv0], v)

    dfs(0, cost[0], -1)

    print(*cost)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        ai = a[i]-1
        bi = b[i]-1
        ci = cost[i]
        link[ai].append((bi, ci))
        link[bi].append((ai, ci))

    def dfs(v, c, p):
        for nv in link[v]:
            nv0 = nv[0]
            if nv0 != p:
                cost[nv0] += c
                dfs(nv0, cost[nv0], v)

    dfs(0, cost[0], -1)

    print(*cost)


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

import itertools

nk = input().split()
seisuuretu = input().split()

for i in range(len(seisuuretu)):
    seisuuretu[i] = int(seisuuretu[i])

all_seisuuretu = []

for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            all_seisuuretu.append(seisuuretu[start:end])

beautiful_list = []

for pattern in all_seisuuretu:
    beautiful_list.append(sum(pattern))

select_index = []

for index in itertools.permutations(range(len(beautiful_list)), r=int(nk[1])):
    select_index.append(index)

result = []

for temp_index in select_index:
    count = 0
    for one_index in temp_index:
        if count == 0:
            temp_and = beautiful_list[one_index]
        else:
            temp_and = temp_and & beautiful_list[one_index]
        count += 1
    result.append(temp_and)

print(max(result))


### FIXED CODE ###

nk = input().split()
seisuuretu_2 = input().split()
nk1 = int(nk[1])

#seisuuretu = [int(i) for i in seisuuretu_2]
seisuuretu = list(map(int, seisuuretu_2))

list_max = set()
beautiful_list = []
for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            temp_pattern = bin(sum(seisuuretu[start:end]))[2:]
            beautiful_list.append(temp_pattern)
            list_max |= {len(temp_pattern),}

list_max = -max(list_max)

status = True
while status == True:
    temp = []
    count = 0
    for i in beautiful_list:
        try:
            if i[list_max] == "1":
                count += 1
                temp.append(i)
        except:
            continue
    if count > nk1:
        list_max += 1
        beautiful_list = temp
    elif count == nk1:
        num_count = True
        for num in temp:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    elif list_max == -1:
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    else:
        list_max += 1
### BUGGY CODE ###

from numba import jit


def solve(N, K, A):
    for _ in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            left = max(0, i-A[i])
            right = min(N-1, i+A[i])+1
            imos[left] += 1
            imos[right] += -1

        next_A = [0] * N
        next_A[0] = imos[0]
        for i in range(1, N):
            next_A[i] = next_A[i-1] + imos[i]

        if A == next_A:
            return A
        A = next_A
    return A


N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(" ".join([str(x) for x in solve(N, K, A)]))


### FIXED CODE ###

from numba import jit


@jit
def solve(N, K, A):
    for _ in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            left = max(0, i-A[i])
            right = min(N-1, i+A[i])+1
            imos[left] += 1
            imos[right] += -1

        next_A = [0] * N
        next_A[0] = imos[0]
        for i in range(1, N):
            next_A[i] = next_A[i-1] + imos[i]

        if A == next_A:
            return A
        A = next_A
    return A


N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(" ".join([str(x) for x in solve(N, K, A)]))
### BUGGY CODE ###

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

ans=1
for i in range(n):
    ans*=A[i]
if ans>10**18:
    print(-1)
else :
    print(ans)


### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
else :
    for i in range(n):
        ans*=A[i]
        if ans > 10**18:
            break

    if ans>10**18:
        print(-1)
    else :
        print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
t = 0
for i in range(n-k+1):
    t = max(t,(k+sum(p[i:i+k]))/2)
print(t)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p.append(0)
s = sum(p[:k])
t = 0
for i in range(k-1,n):
    t = max(t,(k+s)/2)
    s -= p[i-k+1]
    s += p[i+1]
print(t)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
cnt=0
for i in a:
  if b==[] or min(b)>=i:
    cnt+=1
    b.append(i)
  else:
    b.append(i)

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=2*10**5
cnt=0
for i in a:
  if b>=i:
    cnt+=1
    b=i

print(cnt)
### BUGGY CODE ###

import sys
import numpy as np

N = int(sys.stdin.readline())
A = np.array(list(map(int, sys.stdin.readline().split())))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]

for search, replace in replace_map:
    A = np.where(A==search, replace, A)
    print(np.sum(A))


### FIXED CODE ###

import sys
import numpy as np

_ = sys.stdin.readline()
A = list(map(int, sys.stdin.readline().split()))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1

previous_sum = 0
for search, replace in replace_map:
    replaced_count = 0
    if search in nums:
        replaced_count = nums[search]
        nums[replace] = nums[replace] + replaced_count if replace in nums else replaced_count
        del nums[search]
    if previous_sum == 0:
        previous_sum = np.dot(list(nums.keys()), list(nums.values()))
    else:
        previous_sum += replaced_count * (replace - search)
    print(previous_sum)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
max=-2
lim=min(n,b)
for i in range(1,lim+1):
    s=math.floor(a*i/b)-a*math.floor(i/b)
    if s>max:
        max=s
print(int(max))


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    

print(max)
### BUGGY CODE ###

n = int(input())
A = input().split()
if len(set(A)) == 1:
    for _ in range(n):
        print(((n - 1) * (n - 2)) // 2)
    exit()
elif len(set(A)) == len(A):
    for _ in range(n):
        print(0)
    exit()

dA = {}
for a in A:
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

kA = {}
for a in dA:
    kA[a] = (dA[a] - 1) * (dA[a] - 2) // 2
    dA[a] = dA[a] * (dA[a] - 1) // 2

for a in A:
    print(sum(dA.values()) - dA[a] + kA[a])


### FIXED CODE ###

n = int(input())
dA = {}
A = []
for a in input().split():
    A.append(a)
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

cA = {}
for a in dA:
    cA[a] = dA[a] * (dA[a] - 1) // 2

s = sum(cA.values())
for a in A:
    print(s - dA[a] + 1)
### BUGGY CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10**6)
    s = input().strip()
    N = len(s)
    d = np.ones(N+1, dtype=int) * -10**5
    d[0] = 0
    for i, si in enumerate(s, start=1):
        d[i//2+i%2:i+1] = np.maximum(d[i//2+i%2-1:i] - (si == 'p'), d[i//2+i%2:i+1] + (si == 'g'))
        # print('i={}, si={}'.format(i, si), d)
    print(max(d[N//2+N%2:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10**6)
    s = input().strip()
    N = len(s)
    p = sum([1 if si == 'p' else 0 for si in s])
    print(N//2-p)

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

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.5))):
    for j in range(y):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(min(k,w)):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)

### FIXED CODE ###

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.4))):
    for j in range(min(y,int(k*1.4))):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(w):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)
### BUGGY CODE ###

def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i]!=0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i]=re
    return re


kuro = 1
siro = 0
n, m = map(int, input().split())
ko = [[] for _ in range(n + 1)]
memo = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    ko[x] += [y]
    ko[y] += [x]
for start_i in range(1, n + 1):
    print(cnt(start_i, 0) % m)


### FIXED CODE ###

from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()
### BUGGY CODE ###

def solve(N,x):
    ans = []
    cnt = 0
    for i in range(N):
        if 2**i & x != 0:
            cnt += 1

    for i in range(N):
        x ^= 2**(N-i-1)
        ans.append(cal(x,0))
        x ^= 2**(N-i-1)
    return ans

def cal(x,rec):
    cnt,dig = 0,0
    while 2**dig <= x:
        if 2**dig & x != 0:
            cnt += 1
        dig += 1

    if cnt == 0:
        return rec
    else:
        amari = 0
        for i in range(dig):
            if x & 2**i != 0:
                amari += pow(2,i,cnt)
                amari %= cnt
        return cal(amari,rec+1)

def main():
    N = int(input())
    X = input()

    x = 0
    for i in range(N):
        if X[i] == "1":
            x += pow(2,N-i-1)

    ans = solve(N,x)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def solve(N,X):
    ans = []
    cnt = X.count("1")
    rem_ori = [0,0]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem_ori[0] += pow(2,N-i-1,cnt-1)
                rem_ori[0] %= (cnt-1)
            else:
                rem_ori[0] = 0
            rem_ori[1] += pow(2,N-i-1,cnt+1)
            rem_ori[1] %= (cnt+1)

    rem = [(rem_ori[0] if X[i] == "1" else rem_ori[1]) for i in range(N)]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem[i] -= pow(2,N-i-1,cnt-1)
                rem[i] %= (cnt-1)
                ans.append(cal(rem[i],1))
            else:
                ans.append(0)
        else:
            rem[i] += pow(2,N-i-1,cnt+1)
            rem[i] %= (cnt+1)
            ans.append(cal(rem[i],1))

    return ans

def cal(rem,rec):
    if rem == 0:
        return rec
    else:
        b = bin(rem)[2:]
        cnt = b.count("1")
        rem %= cnt
        return cal(rem,rec+1)

def main():
    N = int(input())
    X = input()

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

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

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

ans = [0] * n

for i in range(1, n):
    l  =min(i, k)
    ans[i] = min([abs(h[i] - h[i - j])+ans[i-j] for j in range(1, l+1)])

#print(ans)
print(ans[n-1])

### FIXED CODE ###

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

ans = [0] * n

for i in range(1, n):
    l = min(i, k)
    hs = h[i]
    ans[i] = min([abs(hs - h[i - j])+ans[i-j] for j in range(1, l+1)])
    # j : 戻り幅
#print(ans)
print(ans[-1])
### BUGGY CODE ###

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

dp=[[0]*(W+1) for _ in range(N+1)]

for w in range(W+1):
    for n in range(N):
        if wv[n][0]<=w:
            dp[n+1][w]+=max(wv[n][1]+dp[n][w-wv[n][0]],dp[n][w])
        else:
            dp[n+1][w]=dp[n][w]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for i in range(N)]
 
dp=[[0]*(W+1) for i in range(N+1)]
 
for w in range(W+1):
    for n in range(N):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w-wv[n][0]] + wv[n][1], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
 
 
print(dp[N][W])
### BUGGY CODE ###

n=int(input())
h=[0]+list(map(int,input().split()))+[0]

cnt=0
while any([i!=0 for i in h]):
    start,end=100,100
    for i in range(n+2):
        if h[i]!=0:
            start=min(start,i)
        elif h[i]==0 and start<i:
            end=min(end,i)
    l=[i-1 for i in h[start:end]]
    h=h[:start]+l+h[end:]
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
h=[0]+list(map(int,input().split()))+[0]

cnt=0
while any([i!=0 for i in h]):
    start,end=100,100
    for i in range(n+2):
        if h[i]!=0:
            start=min(start,i)
        elif h[i]==0 and start<i:
#            end=min(end,i)
            end=i
            break
    l=[i-1 for i in h[start:end]]
    h=h[:start]+l+h[end:]
    cnt+=1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

for i in range(N):
    tmp = A.pop(i)
    print(max(A))
    A.insert(i, tmp)

### FIXED CODE ###

N = int(input())
A = [0]*N

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

B = sorted(A,reverse=True)

for i in range(N):
    if A[i]==B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(n):
    b.append(a[i])
    b.reverse()

print(*b)


### FIXED CODE ###

from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = deque()

for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])

if n % 2 == 1:
    b.reverse()

print(*b)
### BUGGY CODE ###

n=int(input()) 
s=list(input())

ans=2000000
cnt=0
for i in range(n):
  for j in range(n-i):
    if s[i+j]==".":
      cnt+=1
  for k in range(i):
    if s[k]=="#":
      cnt+=1
  if cnt<=ans:
    ans=cnt
  cnt=0

for i in range(n):
  if s[i]==".":
    cnt+=1
  else:
    cnt-=1

if abs(cnt)==len(s):
  ans=0

print(ans)


### FIXED CODE ###

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