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

import sys,queue,math,copy
from functools import reduce
from fractions import gcd
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]
LI_2 = lambda : [int(x) / 2 for x in input().split()]

#lcm = lambda a : reduce(lambda x, y : x * y // gcd(x,y), a)
N,M = LI()
A = LI_2()

lcm = 1
for a in A:
    lcm *= a // gcd(lcm,a)

for a in A:
    if (lcm // a) % 2 == 0:
        print (0)
        exit (0)

print (math.ceil((M//lcm) / 2))

### FIXED CODE ###

import sys,queue,math,copy
from fractions import gcd
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]
LI_2 = lambda : [int(x) / 2 for x in input().split()]

N,M = LI()
A = LI_2()

lcm = 1
for a in A:
    c = gcd(lcm,a)
    if (lcm//c) % 2 == 0:
        print (0)
        exit (0)
    lcm *= (a//c)

print (math.ceil((M//lcm) / 2))
### BUGGY CODE ###

N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[] for i in range(N)]
dp[0].append((0,0))
for i in range(N):
    if i == 0:
        dp[i].append((0,0))
        if W >= WV[i][0]:
            dp[i].append((WV[i][0],WV[i][1]))
    else:
        for e1,e2 in dp[i-1]:
            dp[i].append((e1,e2))
            if W >= e1+WV[i][0]:
                dp[i].append((e1+WV[i][0],e2+WV[i][1]))
ans = 0
for e1,e2 in dp[-1]:
    ans = max(e2,ans)
print(ans)

### FIXED CODE ###

N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[float('inf') for j in range(100001)] for i in range(N)]
dp[0][0] = 0
for i in range(N):
    w,v = WV[i]
    if i == 0:
        dp[i][v] = w
    else:
        for j in range(100001):
            if j-v >= 0:
                dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

ans = 0
for i,e in enumerate(dp[-1]):
    if W >= e:
        ans = i
print(ans)
### BUGGY CODE ###

import statistics
n = int(input())
a = list(map(int, input().split()))
l = []
m = []
for i in range(n):
    m.append(a[i]-i)
for i in range(n):
    l.append(abs(a[i]-(int(statistics.median(m))+i)))
print(sum(l))

### FIXED CODE ###

import statistics
n = int(input())
a = list(map(int, input().split()))
l = []
m = []
for i in range(n):
    m.append(a[i]-i)
med = int(statistics.median(m))
for i in range(n):
    l.append(abs(a[i]-(med+i)))
print(sum(l))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
per=LI()
for i in range(n):
    per[i]-=1
points=LI()
ans=-inf
for i in range(n):
    val=0
    #res=[0 for j in range(n+1)]
    res=[]
    pos=per[i]
    inipos=per[i]
    count=0
    while True:
        val+=points[pos]
        pos=per[pos]
        if len(res)==0:
            res.append(val)
        else:
            res.append(max(res[-1],val))
        #res[count]=max(val,res[count-1])
        count+=1
        if pos==inipos:
            break
    loop=(val,count)
    #print(loop)
    #print(res)
    for x in range(len(res)):
        if loop[0]<=0:
            ans=max(ans,res[x])
        else:
            ans=max(ans,res[x]+loop[0]*((k-x-1)//loop[1]))
print(ans)
        
        
        
        
        
        
    
    
    
        
        
        
        
        
            
            


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
per=LI()
for i in range(n):
    per[i]-=1
points=LI()
ans=-inf
for i in range(n):
    val=0
    #res=[0 for j in range(n+1)]
    res=[]
    pos=per[i]
    inipos=per[i]
    count=0
    while True:
        val+=points[pos]
        pos=per[pos]
        if len(res)==0:
            res.append(val)
        else:
            res.append(max(res[-1],val))
        #res[count]=max(val,res[count-1])
        count+=1
        if pos==inipos:
            break
    loop=(val,count)
    #print(loop)
    #print(res)
    for x in range(len(res)):
        if loop[0]<=0:
            ans=max(ans,res[x])
        else:
            ans=max(ans,res[x]+loop[0]*((k-x-1)//loop[1]))
print(ans)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
import numpy as np
dp = np.full((N+1,N+1),INF,dtype='int64') #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0,0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i,j] = min(dp[i,j], dp[i-a,j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i,j])
print(ans if ans != INF else -1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

L,R = map(int,input().split())

D = []

for i in range(L,R+1):
    D.append(i%2019)
    if len(D)>=4038:
        break

ans = 2019
for i in range(len(D)):
    for j in range(i+1,len(D)):
        a = (D[i]*D[j]) % 2019
        if ans > a:
            ans = a
            if ans==0:break
            
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())

ans = 2019
it = L
while(it<=min(R,it+2019)):
    jt = it+1
    while(jt<=min(R,jt+2019)):
        a = (it*jt)%2019
        if a < ans:
            ans = a
            if ans==0:break
        jt += 1
    if ans==0:break
    it += 1
            
print(ans)
### BUGGY CODE ###

X = input()
N = 10**10000
for i in range(N):
	if "ST" in X:
		X = X.replace("ST","")
	else:
		print(len(X))
		break
else:
	print(len(X))


### FIXED CODE ###

X = input()
stack = []
for l in X:
	if stack == []:
		stack.append(l)
	elif stack[-1] == "S" and l == "T":
		stack.pop()
	else:
		stack.append(l)
print(len(stack))
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eat = []

# 食べる
p.sort(reverse=True)
if X > A:
    eat.extend(p)
else:
    eat.extend(p[:X])

q.sort(reverse=True)
if Y > B:
    eat.extend(q)
else:
    eat.extend(q[:Y])
loss = X+Y - len(eat)

# 足りない分を補充する
while loss > 0:
    r.sort(reverse=True)
    eat.append(r.pop(0))    
    loss -= 1

# rの方が大きいものがあれば入れ替える
eat.sort()
for i in range(len(eat)):
    r.sort(reverse=True)
    if len(r) != 0 and eat[i] < r[0]:
        eat[i] = r.pop(0)
    else:
        break

print(sum(eat))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eat = []

# 食べる
p.sort(reverse=True)
if X > A:
    eat.extend(p)
else:
    eat.extend(p[:X])

q.sort(reverse=True)
if Y > B:
    eat.extend(q)
else:
    eat.extend(q[:Y])
loss = X+Y - len(eat)

# 足りない分を補充する
while loss > 0:
    r.sort(reverse=True)
    eat.append(r.pop(0))    
    loss -= 1

# rの方が大きいものがあれば入れ替える
eat.sort()
r.sort()
for i in range(len(eat)):
    if len(r) != 0 and eat[i] < r[-1]:
        eat[i] = r.pop(-1)
    else:
        break

print(sum(eat))
### BUGGY CODE ###

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

# In[13]:


N,K,Q = map(int, input().split())
point = [K]*N
for _ in range(Q):
    A = int(input())
    point = [point[i]-1 if i != A-1 else point[i] for i in range(len(point))]
ans = [print("Yes") if point[i]>0 else print("No") for i in range(len(point))]


# In[ ]:






### FIXED CODE ###

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

# In[14]:


N,K,Q = map(int, input().split())
point = [0]*N
for _ in range(Q):
    A = int(input())
    point[A-1] += 1 
ans = [print("Yes") if point[i] > Q-K else print("No") for i in range(len(point))]


# In[ ]:
### BUGGY CODE ###

def divis(l):
    seq = []
    beg, end = 0, 0
    le = len(l)
    for i in range(1,le):
        end = i
        if l[i] < l[i-1]:
            seq.append(l[beg:end])
            beg = i
    seq.append(l[beg:end+1])
    return seq

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    cost = 0
    a = divis(a)
    a.sort()
    le = len(a)
    first = [a[i][-1] for i in range(le)]
    for i in range(le):
        for j in range(len(a[i])):
            cost += max(first[0:i+1]) - a[i][j]
    print(cost)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    mi = 0
    le = len(a)
    cost = 0
    for i in range(le-1):
        if mi > a[i+1] or a[i] > a[i+1]:
            mi = max(a[i], mi)
            cost += mi - a[i+1]
    print(cost)
    return 0

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

import bisect
l=[]
for i in range(int(input())):
    n=int(input())
    x=bisect.bisect_left(l,n)
    if x==len(l):l.append(n)
    elif l[x]==n:l.remove(n)
    else:l.insert(x,n)
print(len(l))

### FIXED CODE ###

from collections import Counter
l=[int(input()) for i in range(int(input()))]
ca=Counter(l).most_common()
x=0
for i,j in ca:
    if j%2==1:x+=1
print(x)
### BUGGY CODE ###


def main():
    n = int(input().strip())
    s = input().strip()

    m = 300000
    for i in range(0, len(s)):
        c = len([x for x in s[0:i] if x == 'W'])
        c += len([x for x in s[i+1:] if x == 'E'])

        m = min(m, c)

    print(m)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    n = int(input().strip())
    s = input().strip()

    right_e = len([x for x in s if x == 'E'])
    left_w = 0

    m = right_e - 1 if s[0] == 'E' else right_e
    
    for i in range(1, len(s)):
        if s[i-1] == 'E':
            right_e -= 1
        else:
            left_w += 1

        if s[i] == 'E':
            m = min(m, right_e - 1 + left_w)
        else:
            m = min(m, right_e + left_w)


    print(m)


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

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

ans = 0
for a in range(0, N-2):
  for b in range(a+1, N-1):
    for c in range(b+1, N):
      if L[a] < (L[b]+L[c]):
        if L[b] < (L[a]+L[c]):
          if L[c] < (L[a]+L[b]):
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
from bisect import bisect_left
ans = 0

for a in range(0, N-2):
  for b in range(a+1, N-1):
    t = L[a] + L[b]
    idx = bisect_left(L,t)
    ans += max(0, idx-b-1)

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

l = (1260-540+1)
while True:
	N,M = map(int,input().split(" "))
	if N == 0 and M == 0:
		break
	T = [[0]*l for _ in range(M)]
	r = int(input())
	for i in range(r):
		t,n,m,s = map(int,input().split(" "))
		if s == 1:
			T[m-1][t-540] += 1
		else:
			T[m-1][t-540] -= 1

	T_range = [[] for _ in range(M)]
	for i in range(M):
		flg = True if T[i][0] >= 1 else False
		lb = 0
		for j in range(l-1):
			T[i][j+1] += T[i][j]
			if flg and T[i][j+1] == 0:
				T_range[i].append((lb+ 540,j+1+540))
				flg = False
			elif (not flg) and T[i][j+1] >= 1:
				flg = True
				lb = (j+1)
		if flg:
			T_range[i].append((lb+540,l+540))

	q = int(input())
	for i in range(q):
		t1,t2,m = map(int,input().split(" "))
		ans = 0
		for a,b in T_range[m-1]:
			if not (b < t1 or t2 < a):
				ans += (min(t2,b) - max(t1,a))

		print(ans)



### FIXED CODE ###

l = (1260-540)+1
while True:
	N,M = map(int,input().split(" "))
	if N == 0 and M == 0:
		break
	T = [[0]*l for _ in range(M)]
	r = int(input())
	for i in range(r):
		t,n,m,s = map(int,input().split(" "))
		if s == 1:
			T[m-1][t-540] += 1
		else:
			T[m-1][t-540] -= 1

	q = int(input())
	used = {}
	for i in range(q):
		t1,t2,m = map(int,input().split(" "))
		if not (m-1) in used:
			T_range = []
			flg = True if T[m-1][0] >= 1 else False
			lb = 0
			for j in range(l-1):
				T[m-1][j+1] += T[m-1][j]
				if flg and T[m-1][j+1] == 0:
					T_range.append((lb+540,j+1+540))
					flg = False
				elif (not flg) and T[m-1][j+1] >= 1:
					flg = True
					lb = (j+1)
			if flg:
				T_range.append((lb+540,1261))
			used[m-1] = T_range

		ans = 0
		for a,b in used[m-1]:
			if not (b < t1 or t2 < a):
				ans += (min(t2,b) - max(t1,a))

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

def main():
    N = int(input())
    A = [int(n) for n in input().split()]

    M = 10 ** 9 + 7

    ans = 0
    for i in range(N-1):
        ans += A[i] * sum([A[j] for j in range(i+1, N)]) % M
    print(ans % M)


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(n) for n in input().split()]

    M = 10 ** 9 + 7

    ans = 0
    cache = sum(A) % M
    for i in range(N-1):
        cache -= A[i]
        ans += A[i] * cache % M
    print(ans % M)


main()
### BUGGY CODE ###

N = int(input())
check = tuple(i for i in range(1, N+1))
t = [[0 for i in range(9)] for _ in range(9)]
ans = 0
for i in range(1, 10):
    for l in range(1, 10):
        for q in check:
            if int(str(q)[0]) == i and int(str(q)[-1]) == l:
                t[i-1][l-1] += 1
for i in range(1, N+1):
    if str(i)[-1] == "0":
        continue
    elif len(str(i)) == 1:
        ans += t[i-1][i-1]
    else:
        ans += t[int(str(i)[-1])-1][int(str(i)[0])-1]
print(ans)


### FIXED CODE ###

N = int(input())
t = [[0 for _ in range(9)] for l in range(9)]
ans = 0
for i in range(1, N+1):
    if len(str(i)) == 1:
        t[i-1][i-1] += 1
    elif str(i)[-1] != "0":
        t[int(str(i)[0])-1][int(str(i)[-1])-1] += 1
for i in range(1, N+1):
    a = str(i)[0]
    b = str(i)[-1]
    if b == "0":
        continue
    elif a == b:
        ans += t[(int(a)-1)][int(a)-1]
    else:
        ans += t[(int(b)-1)][int(a)-1]
print(ans)
### BUGGY CODE ###

import sys

def isprime(i):
    if i == 1:
        return False
    elif i == 2 or i == 3:
        return True
    else:
        for k in range(2, (i / 2) + 1):
            if i % k == 0:
                return False
        return True

for line in sys.stdin:
    n = int(line)
    cnt = 0
    for i in range(1, n + 1):
        if isprime(i):
            cnt += 1
    print cnt

### FIXED CODE ###

max_num = 1000000
cnt = 0
p = [1] * max_num
p[0] = p[1] = 0
for i in xrange(2, int(max_num ** 0.5) + 1):
    if p[i]:
        p[i * i::i] = [0] * len(p[i * i::i])

for i in xrange(max_num):
    cnt += p[i]
    p[i] = cnt

while True:
    try: print(p[int(raw_input())])
    except: break
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
cnt=0
num=["0","1","2","3","4","5","6","7","8","9"]

num_list=p = ["".join(i) for i in itertools.product(num,repeat=3)]
for number in num_list:
    mark = 0
    for i in range(N):
        if cnt==0 and number[0]==st[i]:
            mark=i
            cnt+=1
        if cnt==1 and number[1]==st[i] and i>mark:
            cnt+=1
            mark=i
        if cnt==2 and number[2]==st[i] and i>mark:
            cnt+=1
            break
    if cnt==3:
        count+=1
    cnt=0
print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

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

ans = 0
if n < b:
    ans = a*(n/b)

else:
    for i in range(1,int(n//b+1)):
        x = b*i-1
        ans = max(ans, a*((x-(i-1)*b)/b))

print(int(ans//1))
    

### FIXED CODE ###

def main():
    a,b,n = map(int, input().split())
    
    ans = 0
    if n < b:
        ans = a*(n/b)
    
    else:
        for i in range(1,int(n//b+1)):
            x = b*i-1
            ans = max(ans, a*((x-(i-1)*b)/b))
            break
    
    print(int(ans//1))

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

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	
	LR = []
	for _ in range(M):
		l, r = map(int, input().split(" "))
		LR.append((l, r))
		
	PQ = []
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		PQ.append((p, q))
	
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for i, val in enumerate(LR):
		l, r = val
		l -= 1
		r -= 1
		for a in range(l, N):
			for b in range(r, N):
				N_list[a][b] += 1
	
	for i, val in enumerate(PQ):
		p, q = val
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	#print("{} {}".format(p-1, q))
	#print(N_list)
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###


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

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

past = 1
now = 1


for j in range(0,K):
    past = past*A[j]

for i in range(K,N):
    for j in range(i-K+1,i+1):
        now = now*A[j]
    if now > past:
        print('Yes')
    else:
        print('No')
    
    past = now
    now = 1






### FIXED CODE ###


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

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

for i in range(K,N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = list(input())
t=len(s)-1
count = 0
for i in range(t):
    for j in range(t):
        if(s[j]=='B'):
            if(s[j + 1]=='W'):
                s[j]="W"
                s[j+1]="B"
                count += 1
print(count)

### FIXED CODE ###

s = list(input())
t=len(s)
count = 0
a = 0
for j in range(t):
    if(s[j]=='W'):
        count += j-a
        a += 1
print(count)
### BUGGY CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
array=[]
a_max=0

for n in range(N-(K-1)):
  a = sum(p[n:n+K])
  if a>a_max:
    a_max=a
    

ans=(a_max+K)/2
print(ans)
  

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
array=[]

a=sum(p[0:K])
array.append(a)

for n in range(N-K):
  a=a-p[n]+p[n+K]
  array.append(a)

ans=(max(array)+K)/2
print(ans)
### BUGGY CODE ###

N=int(input())
p=[]
count=0
for i in range (N):
  a=int(input())
  if a in p:
    p.remove(a)
    count-=1
  else:
    p.append(a)
    count+=1
print(count)

### FIXED CODE ###

N=int(input())
p=[]
count=0
for i in range (N):
  a=int(input())
  p.append(a)
list.sort(p)
flag=1
for j in range (N-1):
  if p[j]==p[j+1]:
    flag*=-1
  else:
    if flag>0:
      count+=1
    flag=1
if flag>0:
  count+=1
print(count)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a):
      from fractions import gcd
      x = a[0]
      for i in range(1, len(a)):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  z=lcm(A)
  MOD=10**9+7
  ans=0
  for i in range(N):
    ans+=z//A[i]%MOD
  print(ans%MOD)
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

from math import sqrt
I_list=[]
#input syutoku
while True:
	try:
		k=int(input())
		I_list.append(k)
	except:
		break

I_max=max(I_list)
#create list (I_max=100 -> [3,5,7,...,99])
odd_list=[x for x in range(3,I_max+1,2)]
#print(W_list)

P_list=[2]

p=0
#print(I_list)
ct=0
while p<=int(sqrt(I_max)):
	p=odd_list.pop(0)
	P_list.append(p)
	P_baisuu=[p*x for x in range(1, int(I_max/p) +1 )]
	K_list=set(odd_list)-set(P_baisuu)
	odd_list=sorted(list(K_list))
#	print("P_list=")
#	print(P_list)
#	print("odd_list=")
#	print(odd_list)

prime_list=P_list+odd_list
#print("prime_list=")
#print(prime_list)

for i in I_list:
	w=[j for j in prime_list if j<=i ]
	print(len(w)) 

### FIXED CODE ###

from math import sqrt
I_list=[]
prime_list=[]
while True:
	try:
		I_list.append(int(input()))
	except:
		break
I_max=max(I_list)
search_set={x for x in range(2,I_max+1)}


p=-1
while p<=sqrt(I_max):
	p=min(search_set)
	prime_list.append(p)
	search_set={x for x in search_set if x%p !=0 }

search_list=sorted(list(search_set))
prime_list+=search_list

#print(prime_list)


for i in I_list:
	lower_set={j for j in prime_list if j<=i } 
#	print(lower_set)
	print(len(lower_set))