Harryxun/stf_run huggingface dataset:
def gcd(a, b):
    a, b = max([a, b]), min([a, b])
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcd_from_list(num_list):
    if len(num_list) == 1:
        return num_list[0]
    else:
        return gcd(num_list[0], gcd_from_list(num_list[1:]))


def lcm_from_list(num_list):
    gcd_of_input = gcd_from_list(num_list)
    num_list = list(set(num_list))
    lcm = num_list[0]
    for i in range(len(num_list) - 1):
        lcm = lcm * num_list[i + 1] // gcd_of_input
    return lcm


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm_A = lcm_from_list(half_A)
    num_multiples = M // lcm_A
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()
X=int(input())
flagp=False
flagm=False
for A in range(-10**3,10**3):
    B5=A**5-X
    for B in range(10**3):
        if B5==B**5:
            flagp=True
            break
        elif B5==-B**5:
            flagm=True
            break
        else:
            raise Exception
    else:
        continue
    break
if flagp:
    print(A,B)
else:
    print(A,-B)

### FIXED CODE ###

X=int(input())
flagp=False
flagm=False
flage=True
for A in range(-10**3,10**3):
    B5=A**5-X
    for B in range(10**3):
        if B5==B**5:
            flagp=True
            flage=False
            break
        elif B5==-B**5:
            flagm=True
            flage=False
            break
    else:
        continue
    break
if flagp:
    print(A,B)
elif flage:
    raise Exception
else:
    print(A,-B)
N = input()

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

ans = float("inf")

for a in list:
    ans = min(ans, len(bin(a)) - bin(a).rfind("1") - 1)
print(round(ans))

### FIXED CODE ###

print(input().count("1"))
P = list(map(int, input().split()))

print(n)
print(P)

counter = 0
for i in range(1, n-1):
    buff = []
    buff = P[i-1:i+2]
    buff.sort()
    if P[i] == buff[1]:
        counter += 1


print(counter)


### FIXED CODE ###

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

counter = 0
for i in range(1, n-1):
    buff = []
    buff = P[i-1:i+2]
    buff.sort()
    if P[i] == buff[1]:
        counter += 1


print(counter)
l=[]

for x in ['S','H','C','D']:
    for y in [str(i+1) for i in range(13)]:
        l += [x+' '+y]

for n in range(input()):
  l.remove(input())
for i in l:
  print(i)

### FIXED CODE ###

l = [x+' '+y for x in['S','H','C','D']for y in[str(i+1)for i in range(13)]]
for n in range(int(input())):
  l.remove(input())
for i in l:
  print(i)
N = int(input())
A = list(map(int, input().split(" ")))
abs_list = list(map(abc, A))
sort(abs_list)
pos = list(filter(lambda x: x > 0, A))
neg = list(filter(lambda x: x < 0, A))

# A has 0
if abs_list[0] == 0:
	print(sum(abs_list))
else if len(neg) % 2 == 0:
	print(sum(abs_list))
else if abs(pos[0]) < abs(neg[-1]):
	print(sum(abs_list) - 2*pos[0] - 2*neg[-1])
else:
	print(sum(pos) - sum(neg[:-1]))



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(" ")))
abs_list = list(map(abs, A))
abs_list.sort()
pos = list(filter(lambda x: x > 0, A))
neg = list(filter(lambda x: x < 0, A))
pos.sort()
neg.sort()

# A has 0
if abs_list[0] == 0:
	print(sum(abs_list))
elif len(neg) % 2 == 0:
	print(sum(abs_list))
elif len(pos) > 0 and abs(pos[0]) < abs(neg[-1]):
	print(sum(abs_list) - 2*pos[0])
else:
	print(sum(abs_list[1:])-abs_list[0])
n=int(input())
s=input()
s=[int(i)+1 for i in s]
l=[int(i) for i in s]
l1=[0]*(n+62332) 
l2=[0]*(n+32323)
l3=[0]*(n+23333)
l2[n-1]=1 
l3[s[n-1]-1]=1 
k=3 
for i in range(n-2,-1,-1): 
    l2[i]=l2[i+1]
    if l3[s[i]-1]==0:
        l2[i]+=1 
        l3[s[i]-1]=1 
for j in range(1,k):
    l3=[0]*n 
    l1[n-1]=0 
    for i in range(n-2,-1,-1) : 
        l1[i]=l1[i+1]
        l1[i]=l1[i]+l2[i+1]
        l1[i]=l1[i]-l3[s[i]-1]
        l3[s[i]-1]=l2[i+1]
    l2=l1[:]
print(l1[0])

### FIXED CODE ###

n=int(input())
if n<3:
    print(0)
    exit()
if n==3:
    print(1)
    exit()
s=input()
s=[int(i)+1 for i in s]
l=[int(i) for i in s]
l1=[0]*(n+16) 
l2=[0]*(n+13)
l3=[0]*(n+12)
l2[n-1]=1 
l3[s[n-1]-1]=1 
k=3 
for i in range(n-2,-1,-1): 
    l2[i]=l2[i+1]
    if l3[s[i]-1]==0:
        l2[i]+=1 
        l3[s[i]-1]=1 
for j in range(1,k):
    l3=[0]*(n+18)
    l1[n-1]=0 
    for i in range(n-2,-1,-1) : 
        l1[i]=l1[i+1]
        l1[i]=l1[i]+l2[i+1]
        l1[i]=l1[i]-l3[s[i]-1]
        l3[s[i]-1]=l2[i+1]
    l2=l1[:]
print(l1[0])
n,m,x=map(int,input().split())
c=list(map(int,input().split()))
l=[]
for i in range(2**n):
    l.append(format(i,'b').zfill(n))
l1=[]
for i in range(len(l)):
    s=[0]*(m+1)
    for j in range(n):
        if l[i][j]=='1':
            for k in range(m+1):
                s[k]+=c[j][k]

    for o in range(1,m+1):
        if s[o]<x:break
        if o==m:l1.append(s[0])
if len(l1)==0:print(-1) 
else:print(min(l1))

### FIXED CODE ###

n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(n)]
l=[]
for i in range(2**n):
    l.append(format(i,'b').zfill(n))
l1=[]
for i in range(len(l)):
    s=[0]*(m+1)
    for j in range(n):
        if l[i][j]=='1':
            for k in range(m+1):
                s[k]+=c[j][k]

    for o in range(1,m+1):
        if s[o]<x:break
        if o==m:l1.append(s[0])
if len(l1)==0:print(-1) 
else:print(min(l1))
from bisect import bisect_left
import sys
input = sys.stdin.buffer.readline


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


ans = 0
for keta in range(0, 29)[::-1]:
    MOD = 1 << (keta + 1)
    T = 1 << keta
    for i in range(n):
        a[i] %= MOD
        b[i] %= MOD
    a.sort()
    b.sort()

    # i, jの組の個数が奇数だったら、xorしたときにTが残る
    if cnt % 2 == 1:
        ans += T

print(ans)

### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.buffer.readline


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


ans = 0
for keta in range(0, 29)[::-1]:
    MOD = 1 << (keta + 1)
    T = 1 << keta
    for i in range(n):
        a[i] %= MOD
        b[i] %= MOD
    a.sort(reverse=True)
    b.sort()

    # T <= a[i] + b[j] < 2T もしくは 3T <= a[i] + b[j] < 4T
    # を満たすi, jの組の個数を尺取り法で探す
    T1 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < T:
            l += 1
        T1[i] = l

    T2 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 2 * T:
            l += 1
        T2[i] = l

    T3 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 3 * T:
            l += 1
        T3[i] = l

    T4 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 4 * T:
            l += 1
        T4[i] = l

    cnt = 0  
    for i in range(n):
        cnt += (T2[i] - T1[i]) + (T4[i] - T3[i])

    # i, jの組の個数が奇数だったら、xorしたときにTが残る
    if cnt % 2 == 1:
        ans += T

print(ans)
def solve():
	s = input()
   	if s[2] == s[3] and s[4] == s[5]:
		print("Yes")
    else:
		print("No")
          
if __name__ == "__main__":
	solve()

### FIXED CODE ###

def solve():
  s = input()
  if s[2] == s[3] and s[4] == s[5]:
    print("Yes")
  else:
    print("No")

  return

if __name__ == "__main__":
  solve()
n = int(input())

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num
print(search_divisor_num_1(n) % (pow(10,9) + 7))

### FIXED CODE ###

import math
import collections

def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    factor.append(n)
    return factor

n = int(input())
c = collections.Counter([])
for num in range(2, n+1):
  prime_list = trial_division(num)
  c.update(prime_list)
res = 1
for prime, count in c.most_common():
  if(prime > 1):
    res = res * (count + 1)
print(res % (pow(10,9) + 7))
S = list(input())
S.sort()
import bisect
a_uni = ord('a')

Search = S
for i in range(26):
    char = chr(a_uni+i)
    if Search[0] == char:
        ind = bisect.bisect_right(S,char)
        Search = S[ind:]
        continue
    print(char)
    exit()
print('None')




### FIXED CODE ###

S = list(input())
S.sort()
import bisect
a_uni = ord('a')

Search = S
for i in range(26):
    char = chr(a_uni+i)

    if Search and Search[0] == char:
        ind = bisect.bisect_right(S,char)
        Search = S[ind:]
        continue
    print(char)
    exit()
print('None')
f,s=map(int,input.split())
if f==s:
    print('Yes')
else :
    print('No')


### FIXED CODE ###

N,M = (int(i) for i in input().split())
if N==M: 
    print('Yes')
else:
    print('No')
a,b,c=1,0,0
exec('a,b,c=b,c,a+c;'*int(input()))
print(a%(1e9+7))

### FIXED CODE ###

from functools import*
M=10**9+7
@lru_cache(None)
def f(s):
    if s<3:return 0
    c=1
    for i in range(s-2):
        c+=f(i)
    return(sum(map(f,range(s-2)))+1)%M
print(f(int(input())))
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    uf = list(range(N))
    n = [1] * N

    def getpar(a: int):
        if a == uf[a]:
            return a
        uf[a] = getpar(uf[a])
        return uf[a]

    def union(a: int, b: int):
        pa = getpar(a)
        pb = getpar(b)
        if pa == pb:
            return 0, 0
        ra = n[pa]
        rb = n[pb]
        n[pa] += n[pb]
        uf[pb] = uf[pa]
        return ra, rb

    k = N * (N - 1) // 2
    ans = []
    A.reverse()
    B.reverse()
    for Ai, Bi in zip(A, B):
        Ai -= 1
        Bi -= 1
        ra, rb = union(Ai, Bi)
        ans.append(k)
        k -= ra * rb

    assert k == 0, k
    for ansi in reversed(ans):
        print(ansi)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


sys.setrecursionlimit(1000000)


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    uf = list(range(N))
    n = [1] * N

    def getpar(a: int):
        if a == uf[a]:
            return a
        uf[a] = getpar(uf[a])
        return uf[a]

    def union(a: int, b: int):
        pa = getpar(a)
        pb = getpar(b)
        if pa == pb:
            return 0, 0
        ra = n[pa]
        rb = n[pb]
        n[pa] += n[pb]
        uf[pb] = uf[pa]
        return ra, rb

    k = N * (N - 1) // 2
    ans = []
    A.reverse()
    B.reverse()
    for Ai, Bi in zip(A, B):
        Ai -= 1
        Bi -= 1
        ra, rb = union(Ai, Bi)
        ans.append(k)
        k -= ra * rb

    assert k == 0, k
    for ansi in reversed(ans):
        print(ansi)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()
A = []
for _ in range(3):
  A　+= list(map(int,input().split()))
N = int(input())
B = [int(input()) for _ in range(N)]
C = [0]*9
for i in B:
  if i in A:
    x = A.index(i)
    C[x] = 1
if C[0]*C[1]*C[2] == 1 or C[3]*C[4]*C[5]==1 or C[6]*C[7]*C[8] ==1 or C[0]*C[3]*C[6] ==1 or C[1]*C[4]*C[7]==1 or C[2]*C[5]*C[8] ==1 or C[0]*C[4]*C[8] ==1 or C[2]*C[4]*C[6] ==1:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

A = []
for _ in range(3):
  A += list(map(int,input().split()))
N = int(input())
B = [int(input()) for _ in range(N)]
C = [0]*9
for i in B:
  if i in A:
    x = A.index(i)
    C[x] = 1
if C[0]*C[1]*C[2] == 1 or C[3]*C[4]*C[5]==1 or C[6]*C[7]*C[8] ==1 or C[0]*C[3]*C[6] ==1 or C[1]*C[4]*C[7]==1 or C[2]*C[5]*C[8] ==1 or C[0]*C[4]*C[8] ==1 or C[2]*C[4]*C[6] ==1:
  print("Yes")
else:
  print("No")
"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, *P = map(int, read().split())

ans = 0
for i in range(N - K + 1):
    L = P[i:i + K]
    s = (sum(L) + K) / 2
    ans = max(s, ans)
print(f'{ans:.10f}')


### FIXED CODE ###

"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

import itertools

# import math
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, *P = map(int, read().split())
R = list(itertools.accumulate(P))
ans = 0
for i in range(K - 1, N):
    if i - K >= 0:
        s = ((R[i] - R[i - K]) + K) / 2
    else:
        s = (R[i] + K) / 2
    ans = max(s, ans)
print('{:.6f}'.format(ans))
A,B = list(map(int,input().split(" ")))
c = 0
for i in range(1,A+1):
    for j in range(1,B+1):
        print(i,j)
        if i == j:
            c+=1
print(c)

### FIXED CODE ###

A = [int(input()) for i in range(2)]
B = [int(input()) for i in range(2)]
print(min(A) + min(B))
N,X=map(int,input().split())
L=list(map(int,input().split()))
x=0
ans=1
for l in L:
  x+=L
  if x>X:
    break
  ans+=1
print(ans)

### FIXED CODE ###

N,X=map(int,input().split())
L=list(map(int,input().split()))
x=0
ans=1
for l in L:
  x+=l
  if x>X:
    break
  ans+=1
print(ans)
import bisect

def ctoi(char):
  return ord(char) - 97

alphabets = [[] for _ in range(26)]

#素材
ingredients = input()
#つくりたいもの
recipe = input()

# 素材のアルファベット分布リストをつくる
for i in range(len(ingredients)):
  alpha_idx = ctoi(ingredients[i])
  alphabets[alpha_idx].append(i)

ingredients_counter = [0] * 26
for i in range(26):
  ingredients_counter[i] = len(alphabets[i])
ingredients_pointer = -1
ingredients_idx_list = []
flag = True
for i in range(len(recipe)):
  alpha_idx = ctoi(recipe[i])
  if ingredients_counter[alpha_idx] == 0:
    flag = False
    break
  #今のingredients_pointerより右側に使える素材があるか探す
  pointer_candidate_idx = \
  	bisect.bisect_right(alphabets[alpha_idx], ingredients_pointer)
  #右側に無かった。ループして先頭のを使ってどうぞ
  if pointer_candidate_idx == ingredientx_counter[alpha_idx]:
    ingredients_pointer = alphabets[alpha_idx][0]
  else:
    ingredients_pointer = alphabets[alpha_idx][pointer_candidate_idx]
  ingredients_idx_list.append(ingredients_pointer)

if flag == False:
  print(-1)
else: 
  loop = 0
  idx = ingredients_idx_list[0]
  #idxのリセット分ループを数える。左より右が小さかったらループ
  for i in range(1, len(ingredients_idx_list)):
    if ingredients_idx_list[i] < idx:
      loop += 1
    idx = ingredients_idx_list[i]
  # ループx素材の長さ + つくりたいものの最後の文字のインデックス(に、+１)
  print(loop * len(ingredients) + ingredients_idx_list[-1] + 1)

### FIXED CODE ###

import bisect

def ctoi(char):
  return ord(char) - 97


#素材
ingredients = input()
ingredients_len = len(ingredients)
#つくりたいもの
recipe = input()
recipe_len = len(recipe)

alphabets = [[] for _ in range(26)]

# 素材のアルファベット分布リストをつくる
for i in range(ingredients_len):
  alpha_idx = ctoi(ingredients[i])
  alphabets[alpha_idx].append(i)

ingredients_counter = [0] * 26
for i in range(26):
  ingredients_counter[i] = len(alphabets[i])
  
ingredients_idx_list = []
flag = True
ingredients_pointer = -1

for i in range(recipe_len):
  alpha_idx = ctoi(recipe[i])
  if ingredients_counter[alpha_idx] == 0:
    flag = False
    break
  #今のingredients_pointerより右側に使える素材があるか探す
  pointer_candidate_idx = bisect.bisect_right(alphabets[alpha_idx], ingredients_pointer)
  #右側に無かった。ループして先頭のを使ってどうぞ
  if pointer_candidate_idx == ingredients_counter[alpha_idx]:
    ingredients_pointer = alphabets[alpha_idx][0]
  else:
    ingredients_pointer = alphabets[alpha_idx][pointer_candidate_idx]
  ingredients_idx_list.append(ingredients_pointer)

if flag == False:
  print(-1)
else: 
  loop = 0
  idx = ingredients_idx_list[0]
  #idxのリセット分ループを数える。左より右が小さかったらループ
  for i in range(1, recipe_len):
    if ingredients_idx_list[i] <= idx:
      loop += 1
    idx = ingredients_idx_list[i]
  # ループx素材の長さ + つくりたいものの最後の文字のインデックス(に、+１)
  print(loop * len(ingredients) + ingredients_idx_list[-1] + 1)
n = int(input())
ans = [0 for x in range(10000)]

for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            v = i*i + j*j + k*k + i*j + i*k + j*k
            if v < 10000:
                ans[v] += 1
for i in range(n):
    print(ans[i+1])


### FIXED CODE ###

n = int(input())
ans = [0 for x in range(10001)]

for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            v = i*i + j*j + k*k + i*j + i*k + j*k
            if v < 10001:
                ans[v] += 1
for i in range(n):
    print(ans[i+1])
n = int(input())
h = input()
str_list = []
ans = "Yes"
for i in range(len(h)):
  if(i % 2 == 0):
    str_list += h[i]

for j in range (len(str_list)-1):
  if(int(str_list[j]) > int(str_list[j]) + 1):
    str_list[j] = str(int(str_list[j])-1)
  if(int(str_list[j]) > int(str_list[j]) + 1):
    ans = "No"
    break

print(ans)

### FIXED CODE ###

n = int(input())
h = input()
str_list = []
ans = "Yes"
str_list = h.split(" ")

for j in range (len(str_list)-1):

  if(int(str_list[j]) < int(str_list[j+1])):
    str_list[j+1] = str(int(str_list[j+1])-1)
  elif(int(str_list[j]) > int(str_list[j+1])):
    ans = "No"
    break

print(ans)
s=input()
if len(set((s))=2 and count(s[0])=2:
       print('Yes')
else:
       print('No')

### FIXED CODE ###

s=input()
if len(set(s))==2 and s.count(s[0])==2:
    print('Yes')
else:
    print('No')
import math


def get_min(num_step):
    res = math.inf
    for i in range(1, min(num_step, K)+1):
        cost = costs[num_step-i] + abs(steps[num_step] - steps[num_step-i])
        if cost < res:
            res = cost
    return res


N, K = map(int, input().split(" "))
steps = list(map(int, input().split(" ")))
costs = [None] * N
costs[0] = 0

for i in range(1, N):
    costs[i] = get_min(i)

print(costs[N-1])


### FIXED CODE ###

import math


def get_min(num_step):
    res = float("inf")
    for i in range(1, min(num_step, K)+1):
        cost = costs[num_step-i] + abs(steps[num_step] - steps[num_step-i])
        if cost < res:
            res = cost
    return res


N, K = map(int, input().split(" "))
steps = list(map(int, input().split(" ")))
costs = [None] * N
costs[0] = 0

for i in range(1, N):
    costs[i] = get_min(i)

print(costs[N-1])
import io,sys
sys.setrecursionlimit(10**6)

def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    from collections import Counter
    from collections import deque
    import bisect
    n = int(input())
    num = Counter([])

    primes = prime(int(n**0.5+1))+[n]
    primes = deque(primes)

    while n !=1:
        while len(primes)>0:
            p = primes.popleft()
            if n%p==0:
                num[p]+=1
                n = n//p
                primes.appendleft(p)
                break

    m = max(num.values())
    N = [i*(i+1)//2 for i in range(1,int((2*m)**0.5)+1)]
    ans = 0
    for i in num.values():
        k = bisect.bisect_right(N,i)
        ans+=k
    print(ans)
main()

### FIXED CODE ###

def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def prime_fac(n):
    fac = {}
    primes = prime(int(n**0.5)+1)
    for p in primes:
        while n%p==0:
            fac[p] = fac.get(p,0)+1
            n//=p
    if n > 1:
        fac[n] = 1
    return fac

def main():
    n = int(input())
    fac = prime_fac(n)

    ans = 0
    for i in fac.values():
        ct = 1
        while i >= ct*(ct+1)//2:
            ct += 1
            ans+=1
    print(ans)
main()
s=input()
if s[0]==s[1] and s[0]==s[2]
  print('Yes')
else
  print('No')

### FIXED CODE ###

s=input()
if s[0]==s[1] and s[0]==s[2]:
  print('No')
else:
  print('Yes')
number = int(input())
A = int(input())
B = int(input())
if number ==1:
    print('Hello Wordl')
if number ==2:
    print(A+B)

### FIXED CODE ###

n=int(input())
print("Hello World" if n%2!=0 else int(input())+int(input()))
N=input()
S=N(N+1)//2
print(S)


### FIXED CODE ###

N=int(input())
print(N*(N+1)//2)
list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input()
print(list[n])

### FIXED CODE ###

list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(list[n-1])
N=input()
N=int(input())
S=[input() for i in range(N)]
ans='Yes'
if len(set(S))!=N:
    ans='No'
for i in range(N-1):
    if S[i][len(S[i])-1]!=S[i+1][0]:
        ans='No'
print(ans)


### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
ans='Yes'
if len(set(S))!=N:
    ans='No'
for i in range(N-1):
    if S[i][len(S[i])-1]!=S[i+1][0]:
        ans='No'
print(ans)
from collections import deque
n, m = map(int, input().split())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
Edge = [[] for _ in range(n)]
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    Edge[a[i]].append(b[i])
    Edge[b[i]].append(b[i])
looked = [1 for i in range(n)]
counter = 0
for i in range(n):
    if looked[i]:
        looked[i] = 0
        counter += 1
        queue = deque([i])
        while queue:
            now = deque.popleft(queue)
            for j in Edge[now]:
                if looked[j]:
                    deque.append(queue, j)
                    looked[j] = 0
print(counter-1)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
Edge = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
looked = [1 for i in range(n)]
counter = 0
for i in range(n):
    if looked[i]:
        looked[i] = 0
        counter += 1
        queue = deque([i])
        while queue:
            now = deque.popleft(queue)
            for j in Edge[now]:
                if looked[j]:
                    deque.append(queue, j)
                    looked[j] = 0
print(counter-1)
n = int(raw_input())
s = raw_input()
x = []
cnt = 0
for i in s:
    if s[i] == 'I':
        cnt += 1
        x.append(cnt)
    elif s[i] == 'D':
        cnt -= 1
        x.append(cnt)
    else:
        x.append(cnt)
print max(x)


### FIXED CODE ###

n = int(raw_input())
s = raw_input()

cnt =0
x =[0]
for i in xrange(n):
    if s[i] == 'I':
        cnt += 1
        x.append(cnt)
    elif s[i]  == 'D':
        cnt -= 1
        x.append(cnt)

print max(x)