Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            try:
                ans[i] = c[k]
            except:
                flag = True
                return 0
            k += 1
            visited[i] = 1
            dfs(neighbor,i)



m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn)
"""
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

soinsu = [0 for _ in range(1001)]
for i in range(n):
    lst = factorization(a[i])
    for ind, jousu in lst:
        soinsu[ind] = max(soinsu[ind], jousu)

ans = 0
for i in range(n):
    lst = factorization(a[i])
    copied_soinsu = soinsu[:]
    for ind, jousu in lst:
        copied_soinsu[ind] -= jousu
    bi = 1
    for j in range(1001):
        bi = bi * (j**copied_soinsu[j]) % mod
    ans = (ans + bi) % mod

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

mod = 10**9 + 7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

print(ans)
i = int(input())
seen = set()
seen.add(i)
temp = i
for x in range(0,1000000):
  if(temp%2 == 0):
    temp = temp/2
  else:
    temp = 3temp+1
  if(temp in seen):
    print(x)
    break
  else:
    seen.add(temp)

### FIXED CODE ###

i = int(input())
seen = set()
seen.add(i)
temp = i
for x in range(2,1000000):
    if(temp%2 == 0):
        temp = temp/2
    else:
        temp = 3*temp+1
    if(temp in seen):
        print(x)
        break
    else:
        seen.add(temp)
N, Y = list(map(int, input().split()))
final_ans = None
for i in range(N + 1):
    for j in range(N + 1):
        # print(i, j, N - i - j)
        ans = i * 10000 + j * 5000 + (N - i - j) * 1000
        if ans == Y:
            final_ans = f"{i} {j} {N - i - j} "
            break

if final_ans is None:
    print('-1 -1 -1 ')
else:
    print(final_ans)

### FIXED CODE ###

N, Y = list(map(int, input().split()))
final_ans = None
for i in range(N + 1):
    for j in range(N + 1):
        if i + j > N:
            continue
        ans = i * 10000 + j * 5000 + (N - i - j) * 1000
        if ans == Y:
            final_ans = " ".join([str(i), str(j), str(N - i - j)])
            break

if final_ans is None:
    print('-1 -1 -1')
else:
    print(final_ans)
import sys

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

sys.setrecursionlimit(10000)

num = [0,2,5,5,4,5,6,3,7,6]

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

def solve(d, amari):
    if amari < 0:
        return None
    elif amari == 0:
        if d == 0:
            return ""
        else:
            return None
    if amari < d*min_num:
        return None
    elif amari == d*min_num:
        return str(min_A) * d
    elif amari < d*(min_num+1):
        new_d = amari - d*min_num
        temp1 = str(min_A) * (d-new_d) + solve(new_d, amari-(d-new_d)*min_num)
        temp2 = solve(new_d, amari-(d-new_d)*min_num) + str(min_A) * (d-new_d)
        if temp1 and temp2:
            if int(temp1) >= int(temp2):
                return temp1
            else:
                return temp2
        else:
            return None
    for a in A:
        temp = solve(d-1, amari-num[a])
        if temp != None:
            return str(a) + temp
    return None
    

for keta in range(keta_max, 0, -1):
    ans = solve(keta, N)
    if ans:
        break
print(ans)

### FIXED CODE ###

import sys

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

num = [0,2,5,5,4,5,6,3,7,6]

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

DP = [-1] * (N+1)
DP[0] = 0

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0 and DP[i-n] != -1:
            DP[i] = max(DP[i], DP[i-n] * 10 + A[j])

print(DP[N])
N,M=map(int,input().split()) 
L=[list(input().split()) for i in range(M)]
W=[0]*N
A=[0]*N
a=0
w=0
for i in range(M):
  if L[i][1]=="AC":
    A[int(L[i][0])-1]=1
    
  elif L[i][1]=="WA" and A[int(L[i][0])-1]==0:
    W[int(L[i][0])-1]+=1
#for i in A:
  #a+=i
#for i in W:
  #w+=i
for i in range(n):
  if A[i]>0:
    a+=1
    w+=W[i]
print(a,w)



### FIXED CODE ###

import sys
nm=input().rstrip().split(" ")
n=int(nm[0])
m=int(nm[1])
answers=[[] for i in range(n)]
for i in range(m):
    line=input().rstrip().split(" ")
    if line[1]=="AC":
        answers[int(line[0])-1].append(1)
    if line[1]=="WA":
        answers[int(line[0])-1].append(0)
#print(answers)
ac=0
i=0
was=[]
while i<n:
    sums=0
    j=0
    while j<len(answers[i]):
        sums=sums+answers[i][j]
        if sums>0:
            ac+=1
            was.append(j)
            break
        j=j+1
    i=i+1
print(ac,end=" ")
#print(was)
wacount=0
for j in was:
    wacount=wacount+j
print(wacount)
import math
d = float(raw_input())
res = math.sqrt(2) * d
for x in xrange(1, 11):
    if x * x <= d * d <= x * 2 + 1:
        ans = max(ans, d + 1.0)
print "%.10f" % ans

### FIXED CODE ###

import math
d = float(raw_input())
ans = math.sqrt(2) * d
for x in xrange(1, 11):
    if x * x <= d * d <= x * 2 + 1:
        ans = max(ans, x + 1)
print "%.10f" % ans
kuti = 1
k = 0
for i in range(100):
    if kuti>=B:
        print(k)
        break
    elif B == 1:
        print(0)
    else:
        kuti += A-1
        k += 1

### FIXED CODE ###

A,B = map(int,input().split())
kuti = 1
k = 0
for i in range(100):
    if kuti>=B:
        print(k)
        break
    elif B == 1:
        print(0)
    else:
        kuti += A-1
        k += 1
from itertools import product
n, *AB = map(int, open(0).read().split())
A, B = map(sorted, [AB[::2], AB[1::2]])
mid = n//2
if n % 2 == 0:
    a, b = A[mid-1], B[mid-1]
    X = range(a, b+1)
    a, b = A[mid], B[mid]
    Y = range(a, b+1)
    Z = {a+b for a, b in product(X, Y)}
    print(len(Z))
else:
    print(B[mid] - A[mid] + 1)


### FIXED CODE ###

n, *AB = map(int, open(0).read().split())
A, B = map(sorted, [AB[::2], AB[1::2]])
mid = n//2
if n % 2 == 0:
    a0, a1 = A[mid-1], A[mid]
    b0, b1 = B[mid-1], B[mid]
    print(b0+b1 - (a0+a1) + 1)
else:
    print(B[mid] - A[mid] + 1)
def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        elif n>N:return -1
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  if i==1:continue
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1

ansMax=max(primes.values())
ansMin=min(primes.values())

if ansMax==1:
  print('pairwise coprime')
elif ansMax==N:
  print('not coprime')
else:
  print('setwise coprime')

### FIXED CODE ###


def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return {1:1}
        elif n<0:n=abs(n)
        if n>N:return "error"
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1
primes[1]=1
ansMax=max(primes.values())

if ansMax==1:
  print('pairwise coprime')
elif ansMax==N:
  print('not coprime')
else:
  print('setwise coprime')
s = input()
cnt = 0
cnt_set = 0
for x in S:
    if x == 'S':
        cnt += 1
    else:
        if cnt > 0:
            cnt_set += 1
            cnt -= 1
print(len(s)-2*cnt_set)

### FIXED CODE ###

s = input()
cnt = 0
cnt_set = 0
for x in s:
    if x == 'S':
        cnt += 1
    else:
        if cnt > 0:
            cnt_set += 1
            cnt -= 1
print(len(s)-2*cnt_set)
from collections import defaultdict

friend_dict = defaultdict(list)

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

for m in range(M):
  x, y = map(int, input().split())
  friend_dict[x].append(y)
  friend_dict[y].append(x)
  
max_num_group = max([len(set(v)) for v in friend_dict.values()])

print(max_num_group + 1)
  


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class UnionFind():
    """ UnionFindはグループの分割はできないことに注意 """
    def __init__(self, n):
        """
            n: 要素数
            parents: 親を示す、-1の場合、自身の親がいない(頂点)であることを示す
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親の要素が何かを調べる
        同じ要素であれば、同じグループに所属することを示す
        探索しながら、親を頂点につなぎ直すことで、効率的にまとめることができる
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        xとyの所属するグループをまとめる
        """
        x = self.find(x)
        y = self.find(y)

        # 同じ親だった場合、既にグループはまとまっているので処理を終了する
        if x == y:
            return

        # 浅い方を深い方に繋ぐようにする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def most_depth_root(self):
        return -min(self.parents)


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

union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)

print(union_find.most_depth_root())
from sys import stdin
W,H,x,y = [int(x) for x in stdin.readline().rstrip().split()]
if W == H and x == y == (W/2):
    print((W*H) / 2,1)

elif W == H and x == y and x != (W/2):
    print(min(x,W-x) * float(H),1)
    
elif (W/2) == x and (H/2) == y:
    print((W*H)/2,1)

elif x == W and y == 0:
    print((W*H)/2,0)
    
elif x == 0 and y == H:
    print((W*H)/2,0)

elif x == W and y == H:
    print((W*H)/2,0)
    
elif x == 0 and y == 0:
    print((W*H)/2,0)

elif W%x == 0 and H%y == 0:
    print((W*H)/2,0)
    
else:
    squ1 = min(x,W-x) * float(H)
    squ2 = min(y,H-y) * float(W)
    print(max(squ1,squ2),0)

### FIXED CODE ###

from sys import stdin
W,H,x,y = [int(x) for x in stdin.readline().rstrip().split()]
if (W / 2) == x and (H / 2) == y:
    print((W * H) / 2, 1)
else:
    print((W * H) / 2 ,0)
n, k = map(int,input().split())
a = list(map(int,input().split()))

route = []
i = 0

while True:
    ne = a[i]

    if i not in route and len(route) <= k:
        route.append(i)
    else:
        temp = len(route) - len(route[i:])
        if k <= temp:
            print(route[k] + 1)
            # print([i+1 for i in route])
        else:
            print(a[(k-temp)%len(route[i:])])
        break

    i = ne - 1

### FIXED CODE ###

from collections import defaultdict

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

route = defaultdict(int)
i = 0
loop = []
tail = []

while route[i] < 2:

    if route[i] == 0:
        tail.append(i)
    else:
        loop.append(i)
    
    route[i] += 1
    i = a[i] - 1

if len(tail) > k:
    print(tail[k] + 1)
else:
    temp = len(tail) - len(loop)
    print(loop[(k-temp) % len(loop)] + 1)
N=input()
print(N*N*N)

### FIXED CODE ###

N = int(input())
print(N**3)
N = int(input())
M_Dict = {"M":0,"A":0,"R":0,"C":0,"H":0}
for i in range(N):
    moji = str(input())
    if moji[0] in M_Dict.keys():
        M_Dict[moji[0]] += 1
M_Dict = {k: v for k, v in M_Dict.items() if v != 0}    
if len(M_Dict) < 3:
    ans = 0
else:
    ans = 0
    for k in itertools.combinations(list(M_Dict.keys()),3):
        ans += M_Dict[k[0]]*M_Dict[k[1]]*M_Dict[[2]]
    
print(ans)    

### FIXED CODE ###

import itertools
N = int(input())
M_Dict = {"M":0,"A":0,"R":0,"C":0,"H":0}
for i in range(N):
    moji = str(input())
    if moji[0] in M_Dict.keys():
        M_Dict[moji[0]] += 1
M_Dict = {k: v for k, v in M_Dict.items() if v != 0}    
if len(M_Dict) < 3:
    ans = 0
else:
    ans = 0
    for k in itertools.combinations(list(M_Dict.keys()),3):
        ans += int(M_Dict[k[0]]) * int(M_Dict[k[1]]) * int(M_Dict[k[2]])
    
print(ans)
n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]

li.sort(key=lambda x: x[2])
a, b, c = li[-1]

for x in range(101):
    for y in range(101):
        h=c+abs(a-x)+abs(b-y)
        if all(k==max(h-abs(i-x)-abs(j-y),0) for i,j,k in li):
        print(x,y,h)
        exit()

### FIXED CODE ###

n = int(input())
li = [list(map(int,input().split())) for i in range(n)]
 
li.sort(key=lambda x: x[2])
a,b,c = li[-1]
for x in range(101):
    for y in range(101):
        h = abs(x-a) + abs(y-b) + c
        if all(k == max(h-abs(x-i)-abs(y-j),0) for i,j,k in li):
            print(x,y,h)
            exit()
n,k=map(int,input().split())
x=list(map(int,input().split()))

if x[n-1]<=0 :
    t=x[-k]
    print(t)

elif x[0]>=0:
    t=x[k]
    print(t)

else:
    for i in range(n):
        if x[i]<0 and x[i+1]>=0 :
            i0=i+1
            break
#    print(i0)
    tmin=10**9
    for i in range(i0,k):
        kt=i
        t=x[kt]*2-x[kt-k+1]
#        print("1",kt,kt-k+1,t,x[kt],x[kt-k+1])
        if t<tmin:
            tmin=t
    for i in range(i0-1,i0+1-k-1,-1):
        kt=i
        t=-x[kt]*2+x[kt+k-1]
#        print("2",kt,kt+k-1,t,x[kt],x[kt+k-1])
        if t<tmin:
            tmin=t
    print(tmin)

### FIXED CODE ###

from bisect import bisect_right
from bisect import bisect_left

n,k=map(int,input().split())
#n=100000
#k=100000

#n=100000
#k=100000
x=list(map(int,input().split()))

if x[n-1]<0 :
    t=-x[-k]
#    print(1)
    print(t)
elif x[n-1]==0 :
    t=-x[-k+1]
#    print(2)
    print(t)

elif x[0]>0:
    t=x[k-1]
#    print(3)
    print(t)
elif x[0]==0:
    t=x[k-1-1]
#    print(4)
    print(t)

else:
    iz=bisect_left(x,0)
    if x[iz+1]==0:
        k=k-1
        tmin=10**9
#        print((iz-(k-1)+1),iz,n-1-(k-1))
        for i in range(max(0,iz-(k-1)+1),min(iz,n-1-(k-1)+1)):
            kt=i
            t1=-x[kt]+x[kt+(k-1)]*2
            t2=-x[kt]*2+x[kt+(k-1)]
#        print("2",kt,kt+k-1,t,x[kt],x[kt+k-1])
#            print(tmin,t1,t2)
            if t1<tmin:
                tmin=t1
            if t2<tmin:
                tmin=t2
    else:
        tmin=10**9
#        print((iz-(k-1)+1),iz,n-1-(k-1))
        for i in range(max(0,iz-(k-1)+1),min(iz,n-1-(k-1)+1)):
            kt=i
            t1=-x[kt]+x[kt+(k-1)]*2
            t2=-x[kt]*2+x[kt+(k-1)]
#        print("2",kt,kt+k-1,t,x[kt],x[kt+k-1])
#            print(tmin,t1,t2)
            if t1<tmin:
                tmin=t1
            if t2<tmin:
                tmin=t2
    print(tmin)
    
#  299993628 
# 1000000000        
#   99990701
N = int(input())
A = N.split(" ")
A = list(map(int, A))
result = A[0]
for i in range(1,N):
  result = result*A[i]
  if result*A[i] > 10**18:
    print("-1")
    exit()
print(result)

### FIXED CODE ###

N = int(input())
A = input()
A = A.split(" ")
A = list(map(int, A))
result = 1
for i in range(N):
  result = result*A[i]
  if result > 10**18:
    result = 10**18 + 1
if result == 10**18 + 1:
   result = -1
print(result)
n=int(input())
counter=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n-i*k):
            if((i*j+k)==n):
                counter=counter+1
print(counter)

### FIXED CODE ###

n=int(input())
counter=0
for i in range(1,n+1):
    counter=counter+(n-1)//i
print(counter)
import math
def main():

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

    A = [v for v in A if v != 1]
    if len(set(A)) < len(A): return "not coprime"
    A = list(set(A))

    def eratosthenes(limit):
        B = [i for i in range(2, limit+1)]
        primes = []
        while True:
            prime = min(B)
            if prime > math.sqrt(limit):
                break
            primes.append(prime)
            i = 0
            while i < len(B):
                if B[i] % prime == 0:
                    B.pop(i)
                    continue
                i += 1
        for a in B:
            primes.append(a)
        return primes

    primes = eratosthenes(max(A))

    d = dict()
    ispair = True
    isset = True

    for v in A:
        for p in primes:
            if p <= v:
                if v % p == 0:
                    d[p] = d.get(p, 0) + 1
            else:
                break
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"
    return "not coprime"

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

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

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in set(prime_factorize(v)):
            d[u] = d.get(u, 0) + 1
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

if __name__ == '__main__':
    print(main())
a =list(map(int,input().split(' ')))
[print('Yes') if a[0] == a[1] print('No')]

### FIXED CODE ###

a =list(map(int,input().split(' ')))
[print('Yes') if a[0] == a[1] else print('No')]
n,x = map(int,input().split())
l=[0]
for _ in range(n):
  l.append(int(input()))
cnt=0
sum=0
for i in range(n):
  sum+=l[i]
  if sum<=x:
    cnt+=1
print(cnt)

### FIXED CODE ###

n,x = map(int,input().split())
l=list(map(int,input().split()))
cnt=1
suml=0
for i in range(n):
  suml+=l[i]
  if suml<=x:
    cnt+=1
print(cnt)
N = int(raw_input())
S = str(raw_input())
opt_cnt = N
for i in range(N):
    first = S[:i]
    second = S[i+1:]
    cnt = 0
    for f in first:
        if f is not 'E':
            cnt = cnt + 1
        if cnt >= opt_cnt
            break
    for s in second:
        if s is not 'W':
            cnt = cnt + 1
        if cnt >= opt_cnt
            break
    if opt_cnt > cnt:
        opt_cnt = cnt
print(opt_cnt)


### FIXED CODE ###

def opt(N, S):
    if N == 1:
        return 0
    else:
        split = int(N/2)
        return min(opt(split,S[:split])+S[split:].count('E'),S[:split].count('W')+opt(N - split,S[split:]))

Num = int(raw_input())
Str = str(raw_input())
print(opt(Num, Str))
n, x=[int(i) for i in input().split()]

m = [None for i in range(n)]

for i in range(n):
    m[i] = int(input())

# print(n, x, m)

# print(sum(m), min(m))

cnt = n

x -= sum(m)

cnt += x // min(m)

print(cnt)
n, x=[int(i) for i in input().split()]

m = [None for i in range(n)]

for i in range(n):
    m[i] = int(input())

# print(n, x, m)

# print(sum(m), min(m))

cnt = n

x -= sum(m)

cnt += x // min(m)

print(cnt)


### FIXED CODE ###

n, x=[int(i) for i in input().split()]

m = [None for i in range(n)]

for i in range(n):
    m[i] = int(input())

cnt = n
x -= sum(m)
cnt += x // min(m)

print(cnt)
print x**3

### FIXED CODE ###

x = input()
print x ** 3
import sys
read = lambda: sys.stdin.readline().rstrip()
 
def main():
    INF = 10 ** 20
 
    n,k = map(int,input().split())
    height = tuple(map(int,read().split()))
    dp = [INF]*(n+1)
    dp[0] = 0
 
    
    for step in range(1, k + 1):
    	for target in range(n, 0, -1):
            if target-step >= 0: dp[target] = min(dp[target], dp[target - step] + abs(height[target] - height[target - step]))
 
    print(dp[n-1])
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
 
dp = [INF]*N
dp[0] = 0
 
for i,hi in enumerate(h):
    if i == 0:
        continue
    s = i-K if i-K >= 0 else 0
    dp[i] = min([dpk + abs(hi-hk) for dpk,hk in zip(dp[s:i],h[s:i])])
 
print(dp[-1])
n = input()
s = input()
flag = 0
for i in range(1,n-1):
	if s[i-1]+s[i]+[i+1] = "ABC"
    	flag=flag+1
print(flag)      

### FIXED CODE ###

N = int(input())
S = input()
print(S.count("ABC"))
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
print(sum(list(map(int, list(a)))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
s = str(a)
print(sum(list(map(int, list(s)))))
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]#偶数だけ
C=[]#奇数だけ
if N%2==0:
  for i in range(0,int(N/2)):
    B+=[2*i,2*i]
    C+=[2*i+1,2*i+1]
  if A==B or A==C:
    ans=2**(N/2)%(10**9+7)
    print(int(ans))
  else:
    print(0)
else:
  B+=[0]
  C+=[1]
  for i in range(0,int(N/2)):
    B+=[2*i+2,2*i+2]
    C+=[2*i+3,2*i+3]
  if A==B or A==C:
    ans=2**((N-1)/2)%(10**9+7)
    print(int(ans))
  else: 
    print(0)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]#偶数だけ
C=[]#奇数だけ

if N%2==0:
  for i in range(0,int(N/2)):
    B+=[2*i,2*i]
    C+=[2*i+1,2*i+1]
  if A==B or A==C:
    n=int(N/2)
    ans=2**n
    print(ans%(10**9+7))
  else:
    print(0)
else:
  B+=[0]
  C+=[1]
  for i in range(0,int(N/2)):
    B+=[2*i+2,2*i+2]
    C+=[2*i+3,2*i+3]
  if A==B or A==C:
    n=int((N-1)/2)
    ans=2**n
#    ans=2**((N-1)/2)
    print(ans%(10**9+7))
  else: 
    print(0)