Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()

ans = [v+1 for v in g[g.index(g[-1]):-1]]
print(len(ans))
print(*ans, sep="\n")


### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10000)
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()
print(0)
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")
a,b=map(int,input().split())
if a==1 or a==3 or a==5 or a==7 or a==8 or a==10 or a==12:
  if b==1 or b==3 or b==5 or b==7 or b==8 or b==10 or b==12:
    print("Yes")
  else:
    print("No")
if a==4 or a==6 or a==9 or a=11:
  if b==2 or b==6 or b==9 or b==11
    print("Yes")
  else:
    print("No")
if a==2:
  if b==2:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

x, y = map(int, input().split())
a = [1,3,5,7,8,10,12]
b = [4,6,9,11]
if (x in a and y in a) or (x in b and y in b):
    print('Yes')
else:
    print('No')
N, A, B = map(int, input().split())

if A > B:
    print(0)
    sys.exit(0)
if N == 1:
    if A == B:
        print(1)
    else:
        print(0)
    sys.exit(0)

x = B*(N-1)+A
n = A*(N-1)+B
print(x-n+1)

### FIXED CODE ###

import sys
N, A, B = map(int, input().split())

if A > B:
    print(0)
    sys.exit(0)
if N == 1:
    if A == B:
        print(1)
    else:
        print(0)
    sys.exit(0)

x = B*(N-1)+A
n = A*(N-1)+B
print(x-n+1)
N, K, S =  map(int, input().split())

if S = 10**9:
    print(' '.join(map(str, ([S]*K + [1]*(N-K)))))
else:
    print(' '.join(map(str, ([S]*K + [S+1]*(N-K)))))

### FIXED CODE ###

N, K, S =  map(int, input().split())

if S == 10**9:
    print(' '.join(map(str, ([S]*K + [1]*(N-K)))))
else:
    print(' '.join(map(str, ([S]*K + [S+1]*(N-K)))))
N=int(input())

A1 = list(int, input().split())
A2 = list(int, input().split())

SA1 = [0]*N
SA2 = [0]*N

SA1[0] = A1[0]
SA2[N-1] = A2[N-1]

for i in range(N-1):
    SA1[i+1] = SA1[i]+A1[i+1]
    SA2[N-2-i] = SA1[N-1-i]+A1[N-2-i]
    
ans = [0]*N

for i in range(N):
    ans[i] = SA1[i]+SA2[i]

print(max(ans))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 17 23:38:43 2018

@author: ashida
"""

N=int(input())

A1 = list( map(int, input().split()))
A2 = list( map(int, input().split()))

SA1 = [0]*N
SA2 = [0]*N

SA1[0] = A1[0]
SA2[N-1] = A2[N-1]

for i in range(N-1):
    SA1[i+1] = SA1[i]+A1[i+1]
    SA2[N-2-i] = SA2[N-1-i]+A2[N-2-i]
    
ans = [0]*N

for i in range(N):
    ans[i] = SA1[i]+SA2[i]

print(max(ans))
a=int(input())
b=int(input())
if a > b:
 print("a > b")
elif a < b:
 print("a < b")
else:
    print("a == b")  


### FIXED CODE ###

n=input().split()
a=int(n[0])
b=int(n[1])
if a > b:
    print("a > b")
elif a < b:
    print("a < b")
else:
    print("a == b")
S = input()
if s[0] == s[1] and s[2] == s[1] and s[3] == s[2]:
  print(Bad)
else:
  print(Good)

### FIXED CODE ###

s = input()
if s[0] == s[1]:
  print('Bad')
elif s[2] == s[1]:
  print('Bad')
elif s[3] == s[2]:
  print('Bad')
else:
  print('Good')
[a.b]=map(int,input().split( ))
if a>b:
 print("a>b")
elif a<b:
 print("a<b")
else:
 print("a=b")

### FIXED CODE ###

a,b=[int(x) for x in input().split()]
op = ">" if a > b else "<" if a < b else "=="
print("a",op,"b")
40
ferelibenterhominesidquodvoluntcredunt

### FIXED CODE ###

K = int(input())
S = input()

if len(S) > K:
  print(S[:K] + "...")
else:
  print(S)
n= int(input())
if n = 1:
  print("Hello World")
elif n = 2:
  a = int(input())
  b = int(input())
  print(a+b)

### FIXED CODE ###

n= int(input())
if n == 1:
  print("Hello World")
  exit()
else:
  a = int(input())
  b = int(input())
  print(a+b)
k = list(input())
a, b =  map(int, input().split())
if a % k == 0 or b % k == 0:
    print('OK')
else:
    if (b-a) // k == 0:
        print('NG')
    else:
        print('OK')

### FIXED CODE ###

k = int(input())
a, b =  map(int, input().split())
l = 0
for i in range(b // k):
    if a <= k*(i+1) <= b:
        l = 1
        print('OK')
        break
if l == 0:
    print('NG')
import math
n,d = map(int,input().split())
print(math.ceil(n/(2d+1)))

### FIXED CODE ###

import math
n,d = map(int,input().split())
print(math.ceil(n/(2*d+1)))
[N,Z,W]=map(int,raw_input().split())
A=map(int,raw_input().split())

if abs(A[-1]-W)>abs(A[-1]-A[-2]):
    print abs(A[-1]-W)
else:
    print abs(A[-1]-A[-2])


### FIXED CODE ###

[N,Z,W]=map(int,raw_input().split())
A=map(int,raw_input().split())

if len(A)==1:
    print abs(A[-1]-W)
else:
    if abs(A[-1]-W)>abs(A[-1]-A[-2]):
        print abs(A[-1]-W)
    else:
        print abs(A[-1]-A[-2])
# coding: utf-8
n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))
#
dp = [0] * 100010
for i in range(1, n):
    for j in range(1, k + 1):
        if j > i:
            break
        else:
            c_ = dp[i - j] + abs(h[i - j] - h[i])
            if c_ < c:
                c = c_
    dp[i] = c
print(dp[i])


### FIXED CODE ###

# coding: utf-8

def f(n, k, h):
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
        # print(dp)
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))
n=int(input())
l=list(map(int,input().split()))
x=[0 for i in range(10)]
d=0
for i in l:
  if i in range(400):
    l[0]+=1
  elif i in range(400,800):
    l[1]+=1
  elif i in range(800,1200):
    l[2]+=1
  elif i in range(1200,1600):
    l[3]+=1
  elif i in range(1600,2000):
    l[4]+=1
  elif i in range(2000,2400):
    l[5]+=1
  elif i in range(2400,2800):
    l[6]+=1
  elif i in range(2800,3200):
    l[7]+=1
  else:
    d+=1
p=[i for i in x if i>0]
print(min(p),max(p)+d)
   

### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
sumList = [0]*8
mid = 0
for i in range(N):
  if 1<=List[i]<=399:
    sumList[0] += 1
  elif 400<= List[i] <=799:
    sumList[1] += 1
  elif 800 <= List[i] <= 1199:
    sumList[2] += 1
  elif 1200<= List[i] <=1599:
    sumList[3] += 1
  elif 1600<= List[i] <=1999:
    sumList[4] += 1
  elif 2000 <= List[i] <= 2399:
    sumList[5] += 1
  elif 2400 <= List[i] <= 2799:
    sumList[6] += 1
  elif 2800 <= List[i] <= 3199:
    sumList[7] += 1
  elif 3200 <= List[i]:
    mid += 1
res1 = 8 - sumList.count(0)
res2 = res1 + mid
if res1 == 0 and mid > 0:
  res1 = 1
print(res1,res2)
n = int(input())
if(n%2==0):
  print(1/2)
else:
  print(((n+1)/2n))

### FIXED CODE ###

n = int(input())
if(n%2==0):
  print(1/2)
else:
  print((n+1)/2/n)
if (a * b)%2 == 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a,b = map(int,input().split())

if a*b%2 ==0:
  print('Even')
else:
  print('Odd')
import fractions
def resolve():

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

    print(abs(dict_num(P) - dict_num(Q)))


def dict_num(a):
    rank = 0
    for i in range(len(a)-1, 0, -1):
        rank += a[i] - 1 * fractions.factorial(i) 
resolve()

### FIXED CODE ###

from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

dict_order = permutations(range(1, N + 1))

for n, i in enumerate(dict_order):
    if P == i:
        a = n
    if Q == i:
        b = n

print(abs(a - b))
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**10

INF = 10**10

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    #if ans[par] <= idx:
    #    ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    #else:
    #    ans[now] = ans[par]
    ans[now] = bisect.bisect_left(dp, INF)

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
#dp = [-INF] + [INF] * n
dp = [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

### FIXED CODE ###

# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)
n = list(map(int,input().split()))
if 5 in n :
    n.remove(5)
    elif 5 in n :
        elif 7 in n :
            print("YES")
else :
    print("NO")

### FIXED CODE ###

n = list(map(int,input().split()))
if 5 in n:
    n.remove(5)
    if 5 in n and 7 in n :
        print("YES")
    else:
        print("NO")
else:
    print("NO")
a,b,c,k=map(int,input().split())

if k<=a:
  print(a)
elif a<k and k<=a+b:
  print(a)
else:
  print(2a+b-k)

### FIXED CODE ###

a,b,c,k=map(int,input().split())

if k<=a:
  print(k)
elif a<k and k<=a+b:
  print(a)
else:
  print(2*a+b-k)
N = int(input())
S = input()
import numpy as np
ans = 0
for i in range(0, N):
    for j in range(i, N):
        if i ==j or S[i] == S[j]:
            continue
        s = ['R', 'G', 'B']
        s.remove(S[i])
        s.remove(S[j])
        k_s = np.where(np.array(list(S[j:])) == s[0])[0] + j
        for k in k_s:
            if j == k or S[j] == S[k]:
                continue
            elif j-i != k-j and S[i] != S[k]:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i + 1, N):
        k = j - i + j
        if k < N:
            if {S[i], S[j], S[k]} == {"R", "G", "B"}:
                ans -= 1
print(ans)
Number = int(input())
tresure_value = list(map(int , input().split()))
cost = list(map(int , input().split()))
 
count = 0
 
for i in range(Number):
  benefit = tresure_value(i) - cost(i)
  if benefit  > 0:
    count = count + benefit 
    
print(count)


### FIXED CODE ###

Number = int(input())
tresure_value = list(map(int , input().split()))
cost = list(map(int , input().split()))
cnt = 0
 
for i in range(len(tresure_value)):
  benefit = tresure_value[i] - cost[i]
  if benefit  > 0:
    cnt = cnt + benefit 
    
print(cnt)
a,b,c,k=map(int,input().split())
if a-b>10**8:
  print("Unfair")
else:
  print(a-b if k%2=1 else b-a)
  


### FIXED CODE ###

a,b,c,k=map(int,input().split())
if a-b>10**18:
  print("Unfair")
else:
  if k%2==0:
    print(a-b)
  else:
    print(b-a)
N = int(input())
li = list(map(int,input().split()))

counter = 0

for i in range(0,N):
    if li[i+1]>li[i]:
        counter += 1
    else:
        pass
print(counter)

### FIXED CODE ###

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

total = 0
minl = l[0]

for i in l:
    if i <= minl:
        total += 1
        minl = i

print(total)
N, K = map(int, input().split())
x = list(map(int, input().split()))

ans = float('inf')
for l in range(K):
    r = l + K - 1
    if r>N:
        continue
    ans = min(ans, min(abs(x[l]), abs(x[r])) + x[r] - x[l])
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
x=list(map(int,input().split()))
a=[]
for i in range(n-k+1):
    l=x[i]
    r=x[i+k-1]
    a.append(min(abs(l)+abs(r-l),abs(r)+abs(l-r)))
print(min(a))
n = int(input())
a = []
b = []
for _ in range(n):
    a.append(list(map(int,input().split())))
    d.append([0,0,0])
d[0]=a[0]
for i in range(1,n):
    for j in range(3):
        d[i][j]=max(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j]
print(max(d[n-1]))


### FIXED CODE ###

n = int(input())
a = []
d = []
for _ in range(n):
    a.append(list(map(int,input().split())))
    d.append([0,0,0])
d[0]=a[0]
for i in range(1,n):
    for j in range(3):
        d[i][j]=max(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j]
print(max(d[-1]))
N = int(input())
A = list(map(int, input().split()))

tar = reduce(lambda x, y: x*y, A)

if tar > 10 ** 18:
    print(-1)
else:
    print(tar)


### FIXED CODE ###


import sys
N = int(input())
A = list(map(int, input().split()))
A.sort()
tar = 1
for i in A:
    tar *= i
    if tar > 10 ** 18:
        print('-1')
        sys.exit()

print(tar)
a=input()
b=map(int,input().split())
c=list(b)
i=0
j=1

for k in c:
  if j%2==1 and int(k)%2==1:
    i +=1
  j +=1
print(i)

### FIXED CODE ###


l,r,d=map(int,input().split())
i=1
j=0
result=0
while result<=r:
  if result>=l:
    j +=1
  result=d*i
  i+=1
print(j)
s = input()
n = len(s)

left = 0
right = 5
ok = True
while left <n:
    if s[left:right] == "dream":
        
        if s[right:right+2] == "er" and s[right:right+5] != "erase" and s[right:right+6] != "eraser": 
            left = right+2
            right = min(left+5,n)
        else:
            left = right
            right = min(n,left+5)
    
    elif s[left:right] == "erase":
        
        if s[right] == 'r':
         
            left = right+1
            right = min(n,left+5)
        else:
            left = right
            right = min(n,left+5)
    else:
        ok = False
        break
if ok:print("YES")
else:print("NO")

### FIXED CODE ###

s = input()
n = len(s)

left = 0
right = 5
ok = True
while left <n:
    if left >n-1 or right > n:break
    if s[left:right] == "dream":
        
        if s[right:right+2] == "er" and s[right:right+5] != "erase" and s[right:right+6] != "eraser": 
            left = right+2
            right = min(left+5,n)
        else:
            left = right
            right = min(n,left+5)
    
    elif s[left:right] == "erase":
        
        if right < n and s[right] == 'r':
         
            left = right+1
            right = min(n,left+5)
        else:
            left = right
            right = min(n,left+5)
    else:
        ok = False
        break
if ok:print("YES")
else:print("NO")
from heapq import heappush, heappop
V, E, r = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))

INF = 10**10
dist = [INF]*V
que = [(0,r)]
dist[r] = 0
while que:
    c, v = heappop(que)
    if dist[v] < c:
        continue
    for t, cost in g[v]:
        if dist[v] + cost < dist[t]:
            dist[t] = dist[v] + cost
            heappush(que, (t, dist[t]))
for i in xrange(V):
    print dist[i] if dist[i]<INF else "INF"

### FIXED CODE ###

class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    # (max_key - min_key) <= C
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1)]
        self.last = self.siz = 0
        self.used = [0]*N

    def push(self, x, key):
        #assert self.last <= x
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        #assert self.siz > 0
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, M, s = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, readline().split())
    G[a].append((b, c))

INF = 10**18
def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [INF]*N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist

dist = dijkstra(N, G, s)
for c in dist:
    write("INF\n" if c == INF else "%d\n" % c)
import numpy as np

n = int(input())
arrA = np.array(input().split(),dtype=np.int64)

filter = (arrA % 2 == 0)
for i in arrA[filter]:
    if i%3==0 or i%5==0:
        ans = "APPROVED"
    else:
        ans = "DENIED"
        break

# APPROVED or DENIED
print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
arrA = np.array(input().split(),dtype=np.int64)

filter = (arrA % 2 == 0)
if len(arrA[filter])==0:
    ans = "APPROVED"
else:
    for i in arrA[filter]:
        if i%3==0 or i%5==0:
            ans = "APPROVED"
        else:
            ans = "DENIED"
            break

# APPROVED or DENIED
print(ans)
while 1:
 a,op,b=map(int,raw_input().split())
 if op == "?":
   break
 elif op == "+":
   print a+b
 elif op == "-":
   print a-b
 elif op == "/":
   print a/b
 elif op == "*":
   print a*b
  

### FIXED CODE ###

while True:
    a, op, b = raw_input().split()
    ai = int(a)
    bi = int(b)
    if op == '?':
        break
    elif op == '+':
        print(ai + bi)
    elif op == '-':
        print(ai - bi)
    elif op == '*':
        print(ai * bi)
    elif op == '/':
        print(ai / bi)
sA =[]
sA += input()
print("{}{}{}".format(sA[0],len(sA)-2,sA[len(sA-1)]))

### FIXED CODE ###

sA =[]
sA += input()
print("{}{}{}".format(sA[0],len(sA)-2,sA[len(sA)-1]))
N, M, X = map(int, input().split())
A = map(int, input().split())


def ssum(A, l, r):
    ssum = 0
    for i in range(l, r):
        ssum += A[i]
    return ssum


print(min(ssum(A, 0, X), ssum(A, X, N+1)))


### FIXED CODE ###

N, M, X = map(int, input().split())
A = sorted(list(map(int, input().split())))

l = 0
r = 0
for a in A:
    if(a < X):
        l += 1
    else:
        r += 1

print(min(l, r))
N = int(input())
A = int(input())
print(N**2-a)

### FIXED CODE ###

N = int(input())
A = int(input())
print(N**2-A)
n,a=map(int,input().split())
x=list(map(int,input().split()))
# dp[j][k][s]=(x1,...,xjからk枚選んでx[i]の合計をsにするような選び方の総数)
dp=[[[0]*2500 for i in range(51)] for j in range(51)]
dp[0][0][0]=1
for i in range(n):
    for j in range(n+1):
        for k in range(2500):
            if k<x[i]:
                dp[i+1][j][k]=dp[i][j][k]
            else:
                dp[i+1][j][k]=dp[i][j][k]+dp[i][j-1][k-x[i]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
for i in range(n):
    x[i]-=a
# dp[i][j] = i番目までで(j-2500)を何個作れるか
dp=[[0]*5001 for i in range(n)]
dp[0][x[0]+2500]=1
for i in range(1,n):
    dp[i][x[i]+2500]=1
    for j in range(5000):
        for k in range(2):
            if 0<=j-k*x[i]<=5000:
                dp[i][j]+=dp[i-1][j-k*x[i]]
print(dp[n-1][2500])
from sys import stdin

sides = stdin.read().split()

if sides[0] == sides[1] == sides[2]:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

import sys

sides = sys.stdin.readlines()

a, b, c = sides[0].split()

if a == b == c:
  print("Yes")
else:
  print("No")
n = int(input())
s = input()
#white
i=0
num=0
while s[i]==".":
    num+=1
    i+=1
    if i == n:
        break
#  ..##.#..
n = s.count(".")
answ = n-num

#black
j=-1
numb
while s[j]=="#":
    numb+=1
    j-=1
    if j*(-1) == n:
        break
m = s.count('#')
ansb=m-numb

if ansb<=answ:
    print(ansb)
else:
    print(answ)


### FIXED CODE ###

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

a = []
#  .##..#.##.
w = s.count(".")
b = s.count("#")
m = min(w,b)

bb=0

for i in range(n):
    if s[i]=='.':
        w-=1
        a.append(bb+w)
    if s[i]=='#':
        bb += 1
        a.append(bb+w)
if len(a)>0:
    I = min(a)
    print(min(m,I))
else:
    print(m)
import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.flip(-A_neg)
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
def Judgement(x,y,z):
    if z-x-y-2*(x*y)**(1/2)<=0:
        return -1
    elif z-x-y<=0:
        return -1
    elif (z-x-y)**2-4*x*y<=0
        return -1
    else:
        return 0

a,b,c=map(int,input().split())
ans=Judgement(a,b,c)
if ans=-1:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

import math
a,b,c = map(int, input().split())
x=a**2+b**2+c**2+2*a*b-2*b*c-2*a*c
y=4*a*b

if c-b-a>0 and x-y>0 :
    print("Yes")
else:
    print("No")
import math

def main():
    data = []
    while 1:
        try:
            n = input().split()
            a = int(n[0])
            b = int(n[1])
            ans = int(math.log10(a+b)+1)
            data.append(ans)
        except IndexError:
            #EOF
            break
            
    for i in data:
        print(i)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math

def main():
    data = []
    while 1:
        try:
            n = input().split()
            a = int(n[0])
            b = int(n[1])
            ans = int(math.log10(a+b)+1)
            data.append(ans)
        except EOFError:
            break

    for i in data:
        print(i)

if __name__ == "__main__":
    main()
n = int(input())
ans = 0
for _ in range(n):
  x,u = input().split()
  if u == 'BTC':
    x *= 380000
  ans += x

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for _ in range(n):
  x,u = input().split()
  x = float(x)
  if u == 'BTC':
    x *= 380000
  ans += x

print(ans)