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

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 10:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

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

import sys
input = sys.stdin.readline

S=input()[:-1]
Q=int(input()[:-1])
f=0

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                S="".join([q[2],S])
            else:
                S="".join([S,q[2]])
        else:
            if f==0:
                S="".join([S,q[2]])
            else:
                S="".join([q[2],S])
if f==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0
back=[]
forward=[]

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                forward.append(q[2])
            else:
                back.append(q[2])
        else:
            if f==0:
                back.append(q[2])
            else:
                forward.append(q[2])

if f==0:
    print("".join(forward[::-1]+S+back))
else:
    print("".join((forward[::-1]+S+back)[::-1]))
### BUGGY CODE ###

import numpy as np
n = int(input())
p = list(map(float, input().split()))

head = [1] + [0]*(n)
for i in range(n):
  for j in range(i, -1, -1):
    head[j+1] += head[j] * (1 - p[i])
    head[j] = head[j] * p[i]

print(sum(head[:n//2+1]))


### FIXED CODE ###

import numpy as np
n = int(input())
p = np.array(list(map(float, input().split())))

head = np.zeros(n+1)
head[0] = 1
for i in range(n):
  #print(head)
  mask = np.r_[np.ones(i+1), np.zeros(n-i)]
  h1 = head * (1 - p[i]) * mask
  h2 = head * p[i] * mask
  head = h1 + np.r_[np.zeros(1), h2[:-1]]

print(sum(head[n//2+1:]))
### BUGGY CODE ###

n=int(input())
ss=input()

# Z-algorithm
# 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
#s='aaabaaaab'
def func(s):
  a=[0]*len(s)
  a[0]=len(s)
  i,j=1,0
  while i<len(s):
    while i+j<len(s) and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<len(s) and k+a[k]<j:
      a[i+k]=a[k]
      k+=1
    i+=k
    j-=k
  return a
ans=0
for i in range(n):
  a=func(ss[i:])
  for j in range(len(a)):
    ans=max(ans,min(a[j],j))
print(ans)


### FIXED CODE ###

n=int(input())
ss=input()

# Z-algorithm
# 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
#s='aaabaaaab'
def func(s):
  a=[0]*len(s)
  a[0]=len(s)
  i,j=1,0
  while i<len(s):
    while i+j<len(s) and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<len(s) and k+a[k]<j:
      a[i+k]=a[k]
      k+=1
    i+=k
    j-=k
  return a
ans=0
for i in range(n):
  a=func(ss[i:])
  for j in range(len(a)):
    ans=max(ans,min(a[j],j))
print(ans)
### BUGGY CODE ###

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

time_A = list(map(int, input().split()))
time_B = list(map(int, input().split()))
max_books = 0
change_point = 0

for i in range(1, K+1):  # 変化点は、aがもう一冊読める　or bが読める本一冊へる
    if i <= change_point-1:
        continue
    if max_books == len(time_A) + len(time_B):
        break
    num_books = 0
    change_point_a = 10000000000
    change_point_b = 10000000000
    allot_to_A = i
    allot_to_B = K-i

    for j in range(len(time_A)):
        if time_A[j] <= allot_to_A:
            allot_to_A -= time_A[j]
            num_books += 1
        else:
            change_point_a = time_A[j] - allot_to_A  # Aで読める本が+1される時間
            break
    for k in range(len(time_B)):
        if time_B[k] <= allot_to_B:
            allot_to_B -= time_B[k]
            num_books += 1
        else:
            change_point_b = allot_to_B + time_B[k-1]  # Bで読める本が-1される時間
            break
    change_point = min(change_point_a, change_point_b) + i  # 次の変化点
    max_books = max(max_books, num_books)

print(max_books)


### FIXED CODE ###

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

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(input())
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
ans = base*P.fac[k]
for i in range(k):
    for j in range(1, n-1-i):
        ans += left[j]*(x[i+j+1]-x[i+j])
        ans %= mod
print(ans)


### FIXED CODE ###

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(input())
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
left[0] = 0
for i in range(1, k):
    left[i] += left[i-1]

ans = base*P.fac[k]
for i in range(1, n-1):
    tmp = x[i+1]-x[i]
    ans += tmp*left[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort(reverse = True)
# print(a)
ans = 0

def C(n, k, mod):
    x,y = 1,1
    while k > 0:
        x *= n ; y *= k
        n, k = n-1, k-1
    return x * pow(y, mod-2, mod) % mod


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1, mod)
    ans %= mod

a.reverse()
for i in range(0, n - k + 1):
    ans -= a[i] * C(n - i - 1, k - 1, mod)
    ans %= mod

ans %= mod

print(ans)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
p = mod
a.sort(reverse = True)
# print(a)
ans = 0

#
# def C(n, k):
#     if k == 0:
#         return 1
#     elif n < k or k < 0:
#         return 0
#     else:
#         x,y = 1,1
#         while k > 0:
#             x *= n
#             y *= k
#             n, k = n-1, k-1
#
#         return x * pow(y, mod-2, mod) % mod
#

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % mod


def C(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1)
    ans %= mod



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

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
ans = a[1]-a[0]
for i in range(n-1):
  for j in range(i+1,n):
    if a[j] - a[i] > ans:
      ans = a[j] - a[i]
print(ans)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
nowmax = max(a[1:])
ans = nowmax - nowmin
for i in range(n-1):
  if a[i] == nowmax:
    nowmax = max(a[i+1:])
  if a[i] < nowmin:
    k = nowmax - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]


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

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    print(s.count("AC"))

### FIXED CODE ###

#import re
N, Q = map(int, input().split())
S = input()
#iter = re.finditer("AC", S)
#indices_C = [m.start(0)+1 for m in iter]
#total = len(indices_C)
#
#dec_l_list = []
#dec_l = 0
#dec_r_list = []
#dec_r = total
#for i in range(N):
#    if i in indices_C:
#        dec_l += 1
#        dec_r -= 1
#    dec_l_list.append(dec_l)
#    dec_r_list.append(dec_r)

flag = False
dec_l_list = []
total = 0
for i in range(N):
    if flag and S[i] == "C":
        total += 1
    dec_l_list.append(total)
    flag = True if S[i] == "A" else False
dec_r_list = [total - x for x in dec_l_list]

for i in range(Q):
    l, r = map(int, input().split())
    print(total - dec_l_list[l-1] - dec_r_list[r-1])
### BUGGY CODE ###

n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=l[i][0]*l[i][1]*pow(2,i,mod)
    ans=ans%mod
print(ans)







### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=l[i][0]*l[i][1]*pow(2,i,mod)
    ans=ans%mod
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
an = 0
if K == 1:
  ans = (max(p)+1)/2
  print(ans)
else:
  for i in range(N-K+1):
    su = sum(p[i:i+K])
    if su > an:
      an = su
    if i+K+1 <= N-1:
      su -= p[i] - p[i+K+1]
  ans = an/2 + K/2

  print(ans)
  

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
an = 0
if K == 1:
  ans = (max(p)+1)/2
  print(ans)
else:
  ans = sum(p[0:K])
  an = ans
  for i in range(0,N-K):
    an = an +p[i+K] -p[i]
    ans = max(ans,an)
  num = ans/2 + K/2    
  print(num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
a0 = a[0]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
ma = N
mi = N//2
for i in range(len(bin(N))-2):
    for j in range(ma,mi,-1):
        if a[j-1]%2==1:
            tg_list = make_divisors(j)
            for k in tg_list:
                if k!=j:
                    a[k-1] += 1
    #a[mi//2:mi] %= 2
    #print(a)
    ma = mi
    mi = mi//2
if sum(a)%2 == a0:
    #print(a)
    res = [str(i+1) for i in range(N) if a[i]%2==1]
    M = len(res)
    print(M)
    if M!=0:
        print(' '.join(res))
else:
    print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
a0 = a[0]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
ma = N
mi = N//2
for i in range(len(bin(N))-2):
    for j in range(ma,mi,-1):
        if a[j-1]%2==1:
            tg_list = make_divisors(j)
            for k in tg_list:
                if k!=j:
                    a[k-1] += 1
    #a[mi//2:mi] %= 2
    #print(a)
    ma = mi
    mi = mi//2
if sum(a)%2 == a0:
    #print(a)
    res = [str(i+1) for i in range(N) if a[i]%2==1]
    M = len(res)
    print(M)
    if M!=0:
        print(' '.join(res))
else:
    print(-1)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
m=0;s=0;
for i in range(n-k+1):
    s=0;
    for j in range(k):
        s += sum(range(p[i+j]+1))/p[i+j]
    if(m<s):m=s
print(m)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
m=0
s=[0]
for i in range(n):
    s.append((p[i])*(p[i]+1)/2/p[i])
    s[i+1] += s[i]

for i in range(n-k+1):
    a=s[k+i]-s[i]
    if(m<a):m=a
print(m)
### BUGGY CODE ###

import sys
import math
N = int(input())
d = list(map(int, input().split()))


ans = 0

for i in range(min(d),max(d) + 1):
    ARC = 0
    ABC = 0
    for j in range(N):
        if d[j] < i:
            ARC = ARC + 1
        else:
            ABC = ABC + 1
    if ABC == ARC:
        ans = ans + 1 

print(ans)
             

### FIXED CODE ###

N = int(input())
d = sorted(list(map(int, input().split())))
print(d[N // 2] - d[N // 2 - 1])
### BUGGY CODE ###

C=10**100
S=input()
SL=list(S[i] for i in range(len(S)))#床の情報
BL=list(1 for i in range(len(S)))
CL=list(i for i in range(len(S))) #子供の座標

for j in range(len(S)):
  i=j
  hozon=j
  if SL[i]=="R":
   
    while True:
      if SL[i]=="L":
        index=i
        #print(index)
        break
      i=i+1
    idou=index-hozon
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index-1
  else:
  
    while True:
      if SL[i]=="R":
        index=i
        #print(index)
        break
      i=i-1
    idou=hozon-index
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index+1
for i in range(len(S)):
  BL[i]=CL.count(i)
print(*BL)

### FIXED CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=[0]*TL
ans=[0]*TL #子供の座標
cnt=0
for j in range(2):
  for i in range(TL):
    
    if SL[i]=="R":
      cnt=cnt+1
    else:
      ans[i]=ans[i]+cnt//2
      ans[i-1]=ans[i-1]+(cnt+1)//2
      cnt=0
    
  SL.reverse()
  ans.reverse()
  for i in range(TL):
    if SL[i]=="R":
      SL[i]="L"
    else:
      SL[i]="R" 
for i in range(TL):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
S = [str(input()) for i in range(N)]
count = 0
output = 0

for i in range(N):
  for j in range(N):
    if S[i] == S[j]:
      count += 1
      
if count == N**2:
  output = 1
else:
  count -= N
  count //= 2
  output = N - count
  
print(output)

### FIXED CODE ###

N = int(input())
list=[]
for _ in range(N):
  S = input()
  list.append(S)
print(len(set(list)))
### BUGGY CODE ###

import copy

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

if M == 1:
    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]
    print(len(l))
else:
    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]
    l_tmp = copy.deepcopy(l)

    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]

    l_set = list(set(l) & set(l_tmp))
    l_tmp = copy.deepcopy(l)
    
    for i in range(M-2):
        L, R = map(int,input().split())
        l = [k+L for k in range(R-L+1)]

        l_set = list(set(l) & set(l_set))
        l_tmp = copy.deepcopy(l)

    print(len(l_set))

### FIXED CODE ###

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

Ls, Rs = [0 for _ in range(M)],  [0 for _ in range(M)]

for i in range(M):
    L, R = map(int,input().split())
    Ls[i] = L
    Rs[i] = R
    
L_prime = max(Ls)
R_peime = min(Rs)

if L_prime > R_peime:
    print(0)
else:
    print(R_peime - L_prime + 1)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

ans = 0
visited = set([0])
next_visit_idx = 0
while True:
  next_visit_idx = a[next_visit_idx] -1
  ans += 1
  if next_visit_idx == 1:
    print(ans)
    break
  if next_visit_idx in visited:
    print(-1)
    break

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

ans = 0
visited = set([0])
next_visit_idx = 0
while True:
  next_visit_idx = a[next_visit_idx] -1
  ans += 1
  if next_visit_idx == 1:
    print(ans)
    break
  if next_visit_idx in visited:
    print(-1)
    break
    
  visited.add(next_visit_idx)
### BUGGY CODE ###

N = [int(i) for i in input().split()]
A = N[0]
B = N[1]
C = N[2]
K = N[3]

if A == B == C:
    print(0)
else:
    for i in range(K):
        NA = B + C
        NB = A + C
        NC = A + B
        A = NA
        B = NB
        C = NC
    if abs(A-B) > 10 ** 18:
        print('Unfair')
    else:
        print(A-B)

### FIXED CODE ###

N = [int(i) for i in input().split()]
A = N[0]
B = N[1]
C = N[2]
K = N[3]

if K % 2 == 0:
    if abs(A - B) > 10 ** 18:
        print('Unfair')
    else:
        print(A - B)
else :
    if abs(A - B) > 10 ** 18:
        print('Unfair')
    else:
        print(B - A)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import time

def bfs(graph,N,s,t):
    start=time.time()
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        if time.time()-start==1.9:
            return False,-1
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq

def dijkstra(graph,N,s):
    distance = {(i + 1, j): 1e7 for i in range(N) for j in range(3)}
    distance[s]=0
    q=[]
    heapq.heappush(q,(distance[s],s))
    while len(q)>0:
        cost,v=heapq.heappop(q)
        if cost>distance[v]:
            continue
        else:
            for w in graph[v]:
                if distance[w]>distance[v]+1:
                    distance[w]=distance[v]+1
                    heapq.heappush(q,(distance[w],w))
    return distance


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    distance=dijkstra(graph,N,(S,0))
    d=distance[(T,0)]
    if d%3==0:
        print(d//3)
    else:
        print(-1)
### BUGGY CODE ###

import numpy as np

N,M,V,P = map(int,input().split())
A = [int(i) for i in input().split()]

#A = [[int(i),x]for x,i in enumerate(input().split())]

#順位を得るため重複をなくし降順

target = P

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  Y = [k for k in A if k < x]
  y = len(Y)

  #振り分け範囲より、xの上限を下回る数が多い場合
  ##…xがAのなかでP番目に入れればカウントする
  if y > V - 1:
    bigger = len([b for b in (A) if b > x])
    if target > bigger:
      con += 1
  #そうでなければ
  ##xの上限数を下回るYの数y個分振り分けた後
  ##xの上限数を同等または上回る値の個数zが、
  ##入っているべき順位より小さければカウントする
  else:
    Z = [j for j in A if j >= x]
    z = len(Z)

    if V - y - 1 < z and target - 1 > z:
      con += 1


print(con)

### FIXED CODE ###

N,M,V,P = map(int,input().split())
A = sorted([int(i) for i in input().split()],reverse = True)

pps = 0
con = P

for i in range(P,N):
  #P以降でi番目に大きい数を加算
  pps += A[i - 1]

  #xの上限が順位に入らない
  if A[i] + M < A[P - 1]:
    break
  #点数をいくら振り分けてもいいスコアの数
  fv = min(P - 1 + N - i, V)
  #左辺第二項は、P以降とi以前の、点数の振り分け可能数に上限がある数
  #左辺は振り分けた後にA[i]がP入りを果たせる区間の総和の上限を示す
  #右辺第一項は、振り分け可能数に上限がある数の総和
  #右辺第二項は、振り分けないといけない数の残り
  #右辺は、点数を振り分けた後の値の区間の総和を示すため、
  #右辺が左辺を上回った場合、ループは終了となる
  if (A[i] + M) * (i - P + 1) < pps + M * (V - fv):
    break
  con += 1
  
print(con)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n=int(input())
	s=input().rstrip().decode('utf-8')
	
	cnt=0
	ans=0
	l2=1
	for l1 in range(n-1):
		l2=l1+1
		while l2<n:
			if s[l1]!=s[l2]:
				l2+=1
			else:
				cnt=1
				x=l1+1
				y=l2+1
				while x<l2 and y<n:
					if s[x]==s[y]:
						cnt+=1
						x+=1
						y+=1
					else:
						break
				l2=y
				ans=max(ans,cnt)
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7

#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)

#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

if __name__ == '__main__':
	main()