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

import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
d = {}
ln = len(s)
for i in range(ln):
    for j in range(i, min(ln, i+1+ln//2)):
        tx = s[i:j+1]
        if tx not in d.keys():
            d[tx] = [i]
        else:
            d[tx].append(i)
ans = 0
for k, v in d.items():
    if len(v) >= 2:
        l = len(k)
        if max(v) - min(v) >= l:
            if ans < l:
                ans = l
print(ans)





### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
rs = [0]*n
gs = [0]*n
bs = [0]*n
for i in reversed(range(n)):
    if s[i] == 'R':
        rs[i] += 1
    elif s[i] == 'G':
        gs[i] += 1
    else:
        bs[i] += 1
for i in reversed(range(n-1)):
    rs[i] += rs[i+1]
    gs[i] += gs[i+1]
    bs[i] += bs[i+1]
res = 0
for i in range(n):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        if s[i]!='B' and s[j]!='B':
            res += bs[j+1]
            if j-i+j < n:
                if s[j-i+j] == 'B':
                    res -=1
        elif s[i]!='G' and s[j]!='G':
            res += gs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'G':
                    res -=1
        else:
            res += rs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'R':
                    res -= 1
print(res)

### FIXED CODE ###

n = int(input())
s = input()
rs = [0]*n
gs = [0]*n
bs = [0]*n
for i in reversed(range(n)):
    if s[i] == 'R':
        rs[i] += 1
    elif s[i] == 'G':
        gs[i] += 1
    else:
        bs[i] += 1
for i in reversed(range(n-1)):
    rs[i] += rs[i+1]
    gs[i] += gs[i+1]
    bs[i] += bs[i+1]
res = 0
for i in range(n):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        if s[i]!='B' and s[j]!='B':
            res += bs[j+1]
            if j-i+j < n:
                if s[j-i+j] == 'B':
                    res -=1
        elif s[i]!='G' and s[j]!='G':
            res += gs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'G':
                    res -=1
        else:
            res += rs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'R':
                    res -= 1
print(res)
### BUGGY CODE ###

N = int(input())
S = []

for i in range(N):
  S.append(input())

dict = {i : 0 for i in S}
for i in S:
  dict[i] += 1
for k in sorted([i for i, j in dict.items() if j == max(dict.values())]):
  print(k)

### FIXED CODE ###

from collections import Counter

N, *S = open(0).read().split()
count = Counter(S)
max_value = max(count.values())
ans_list = [i for i, j in count.items() if j == max_value]
ans_list.sort()
print("\n".join(ans_list))
### BUGGY CODE ###

n = int(input())
s = list(input())
 
cnt = [0] * 1000
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            S = ''.join([s[i], s[j], s[k]])
            cnt[int(S)] += 1
 
ans = 0
for i in range(len(cnt)):
    if cnt[i] > 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

from scipy.misc import comb

N = int(input())
A = input().split()
B = {}
for i in range(0, N):
    if not(A[i] in B.keys()):
        B[A[i]] = 1
    else:
        B[A[i]] += 1 

for i in range(0, N):
    B[A[i]] -= 1
    S = 0    
    for value2 in B.values():
        S = S + comb(int(value2), 2, exact=True)
    print(S)
    B[A[i]] += 1

### FIXED CODE ###

from scipy.misc import comb

N = int(input())
A = input().split()

B = {}
for i in range(0, N):
    if not(A[i] in B.keys()):
        B[A[i]] = 1
    else:
        B[A[i]] += 1 

S = 0
for value2 in B.values():
    S = S + comb(int(value2), 2, exact=True)

S0 = 0
for i in range(0, N):
    S0 = S - (comb(int(B[A[i]]), 2, exact=True) - comb(int(B[A[i]])-1, 2, exact=True))
    print(S0)
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,u,v=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

dic=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)
itta=[0]*(n+1)
ta=deque([u])
ao=deque([v])
itta[v]=1
cnt=0
while 1:
    for i in range(len(ta)):
        tmp=ta.popleft()
        if itta[tmp]==1:
            continue
        for i in dic[tmp]:
            if itta[i]==0:
                ta.append(i)
    if len(ta)==0:
        print(cnt)
        break
    cnt+=1
    for i in range(len(ao)):
        tmp=ao.popleft()
        for i in dic[tmp]:
            if itta[i]==0:
                itta[i]=1
                ao.append(i)
    # print(ta)
    # print(ao)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,u,v=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

dic=defaultdict(list)
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)
# print(dic)

taka=[-1]*(n+1)
aoki=[-1]*(n+1)

d=deque([[u,0]])
if len(dic[u])==1:
    taka[u]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if taka[dic[now][i]]==-1:
            taka[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        taka[now]=cnt
# print(taka)

d=deque([[v,0]])
if len(dic[v])==1:
    aoki[v]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if aoki[dic[now][i]]==-1:
            aoki[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        aoki[now]=cnt
# print(aoki)

ans=0
for i in range(n+1):
    if taka[i]<aoki[i]:
        ans=max(ans, aoki[i]-1)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
array=[]
for i in range(M):
    P,Y = list(map(int,input().split()))
    array.append([P,Y])
array2 = sorted(array)
arraysorted1 = []
j = 1
k = 0
while j != N+1:
    array3=[]
    while k <= M-1:
        if array2[k][0] == j:
            array3.append(array2[k][1])
        k += 1
    array3= sorted(array3)
    arraysorted1.append(array3)
    k = len(arraysorted1[j-1])
    j += 1
for n in range(M):
    for m in range(len(arraysorted1[array[n][0]-1])):
        if array[n] == [array[n][0], arraysorted1[array[n][0]-1][m]]:
            lenf = 6-len(str(array[n][0]))
            lenl = 6-len(str(m+1))
            
            print('0'*lenf +str(array[n][0])+'0'*lenl + str(m+1))


### FIXED CODE ###

N,M = map(int,input().split())
PY = []
for i in range(M):
    P,Y = map(int,input().split())
    PY.append([P,Y,i])

PY.sort()
ans = [0 for i in range(M)]
count = 0
old = 0
for j in range(M):
    p,y,inum = PY[j]
    if old == p:
        pnum = p
        cnum = count
    else:
        old = p
        count = 1
        pnum = p
        cnum = 1

    count += 1
    pnum = str(pnum)
    cnum = str(cnum)
    ans[inum] = '0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum

for i in range(M):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = [-x for x in A[-N:]]
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(-sum(tail))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))


### FIXED CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0
cnt_box = list(range(0,k+1))
for i in range(0,k+1):
  for j in range(0, k+1):
    z = s - i - j
    if z in cnt_box:
      cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(0,k+1):
  for j in range(0, k+1):
    z = s - i - j
    if 0<=z<=k:
      cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
read = sys.stdin.read

def main():
    n, k, *p = map(int, read().split())
    p2 = [(1 + pe) /2 for pe in p]
    r = 0
    for i1 in range(n - k + 1):
        r = max(r, sum(p2[i1:i1+k]))

    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

n, k = map(int,input().split())
p = [int(i) for i in input().split()]

psum = [0] * (n - k + 1)
psum[0] = sum(p[0:k])
for i in range(1, n - k + 1):
  psum[i] = psum[i-1] - p[i-1] + p[i + k - 1]
res = (max(psum)+k) / 2
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
flag=0
for i in range(n):
  if a.count(a[i])!=1:
    flag=1
if flag==0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=len(a)
a=set(a)
n=len(a)
if m==n:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

n=int(input())
##s=[i for i in map(str,input().split())]
list=[]
for i in range(n):
    s=input()
    if(s not in list):
        list.append(s)

print(len(list))


### FIXED CODE ###

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

s.sort()
ans=1
for i in range(1,n):
    
    if s[i-1]==s[i]:
        ans=ans-1
    ans+=1

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

N, Q = map(int, input().split())
S = input()
flag = False
AClist = [0] * N
for i in range(N):
    if S[i] == "A":
        flag = True
    elif S[i] == "C" and flag:
        AClist[i] = -1
        AClist[i-1] = 2
        flag = False
ansList = [0] * Q
for i in range(Q):
    l , r = map(int, input().split())
    l -= 1
    ans = sum(AClist[l:r])
    if AClist[r-1] == 2:
        ans -= 2
    if AClist[l] == -1:
        ans += 1
    print(ans)    

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AClist = [0] 
for i in range(N-1):
    if S[i+1] == "C" and S[i] == "A":
        AClist.append(AClist[-1] + 1)
    else:
        AClist.append(AClist[-1])
for i in range(Q):
    l , r = map(int, input().split())
    print(AClist[r-1] - AClist[l-1])
### BUGGY CODE ###

N=int(input())
s= list(map(int,input().split()))
s.insert(0,0)
s.append(0)
for i in range(len(s)-2):
    tmp=s[:]
    del tmp[i+1]
    tmp_sum=0
    for i in range(len(tmp)-1):
        tmp_sum+=abs(tmp[i]-tmp[i+1])
    if i ==(len(tmp)-2):
        print(tmp_sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = []
for i in range(n - 1):
  d.append(abs(a[i + 1] - a[i]))
s = sum(d)
print(s - d[0] + abs(a[1]) + abs(a[-1]))
for i in range(n - 2):
  print(s - d[i] - d[i + 1] + abs(a[i + 2] - a[i]) + abs(a[0]) + abs(a[-1]))
print(s - d[-1] + abs(a[0]) + abs(a[-2]))
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(list(map(int, input().split())))
ans=0
while len(A)>1:
  al = A.popleft()
  for i,a in enumerate(A):
    if i+1 == al + a:
      ans +=1
        
print(ans)
        
  
  

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans=0
cnt = defaultdict(int)
for i in range(N):
  x = i - A[i]
  y = i + A[i]
  cnt[y] += 1
  ans += cnt[x]
        
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.sort()

ans=0
while AB:
  a=AB[-1][0]
  AB=list(filter(lambda x:x[1]<=a,AB))
  ans+=1
  
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.sort()

ar=N+1
ans=0
for i in reversed(range(M)):
  a,b=AB[i]
  if b<=ar:
    ans+=1
    ar=a
  
print(ans)
### BUGGY CODE ###

from fractions import gcd
# 工夫せずにやって通るか確認

N = int(input())
A = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7


lcm = A[0]
for i in range(1, N):
    lcm = (lcm * A[i] // (gcd(lcm, A[i])))
ans = 0

for a in A:
    ans = (ans + lcm // a) % MOD

print(ans)

### FIXED CODE ###

from fractions import gcd

N = int(input())
A = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7


def modinv(a, mod=10 ** 9 + 7):
    return pow(a, mod - 2, mod)

lcm = A[0]
for i in range(1, N):
    lcm = (lcm * A[i] // (gcd(lcm, A[i])))
ans = 0
lcm %= MOD

for a in A:
    ans = (ans + lcm * modinv(a)) % MOD

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

from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])
#print(b)

ans = float("inf")
for i in range(2, n - 1):
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b[i:], (b[-1] + b[i-1]) / 2) + i
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

### FIXED CODE ###

from bisect import bisect, bisect_left

n = int(input())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append(b[-1] + a[i])

ans = float("inf")
for j in range(2, n-1):
	c = []
	f = bisect(b, b[j]/2)
	f -= 1
	if f == 0 or j == 2:
		c += [b[1]-b[0], b[j]-b[1]]
	elif f == j-1:
		c += [b[j-1]-b[0], b[j]-b[j-1]]
	else:
		if abs(b[f]-b[0] - (b[j]-b[f])) <= abs(b[f+1]-b[0] - (b[j]-b[f+1])):
			c += [b[f]-b[0], b[j]-b[f]]
		else:
			c += [b[f+1]-b[0], b[j]-b[f+1]]

	l = bisect(b, b[j]+((b[n]-b[j])/2))
	l -= 1
	#print(l)
	if l == j or j == n-2:
		c += [b[j+1]-b[j], b[n]-b[j+1]]
	elif l == n-1:
		c += [b[n-1]-b[j], b[n]-b[n-1]]
	else:
		if abs(b[l]-b[j] - (b[n]-b[l])) <= abs(b[l+1]-b[j] - (b[n]-b[l+1])):
			c += [b[l]-b[j], b[n]-b[l]]
		else:
			c += [b[l+1]-b[j], b[n]-b[l+1]]

	ans = min(ans, max(c)-min(c))

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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

lst = get_sieve_of_eratosthenes(10**6+1)
x = I()
for i in lst:
    if x <= i:
        print(i)
        quit()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

lst = get_sieve_of_eratosthenes(2*10**5)
x = I()
for i in lst:
    if x <= i:
        print(i)
        quit()
### BUGGY CODE ###

# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    res=[i]
    for i in range(3):
        tmpF=set([])
        for r in res:
            for node in G[r]:
                if node in tmpF:
                    continue
                tmpF.add(node)
        res=list(tmpF)
    return res

# KKP=[[]]+[check(i+1) for i in range(N)]

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in check(node):
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

### FIXED CODE ###

# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]

for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
S=(S,0)
T=(T,0)

q=deque()
q.append(S)
F=set()
res=-1
while q:
    node,r=q.popleft()
    if (node,r%3) in F:
        continue
    if (node,r%3) == T:
        res=r//3
        break
    F.add((node,r%3))
    for next_node in G[node]:
        if (next_node,(r+1)%3) in F:
            continue
        q.append((next_node,r+1))
print(res)
### BUGGY CODE ###

from operator import itemgetter

H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [[float("inf") for _ in range(H + 1)] for _ in range(N + 1)]

for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    for h in range(H):
        dp[i + 1][min(H, h + A[i])] = min(
            dp[i + 1][min(H, h + A[i])], dp[i][min(H, h + A[i])]
        )
        dp[i + 1][min(H, h + A[i])] = min(
            dp[i + 1][min(H, h + A[i])], dp[i + 1][h] + B[i]
        )

print(dp[N][H])


### FIXED CODE ###

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

A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float("inf") for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for i in range(N):
        dp[h] = min(dp[h], dp[max(0, h - A[i])] + B[i])

print(dp[H])
### BUGGY CODE ###

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

#N=len(sticks)
sticks.sort(reverse = True)
count = 0
fj = True
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if not fj:
            fj=True
            break
        else:
            for k in range(j+1,N):
                #stick[i]>j>k
                if sticks[i]<sticks[j]+sticks[k]:
                    count += 1
                else:
                    if j+1 == k :
                        fj = False
                    break
        
print(count)


### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

import heapq
[N,M]=[int(x) for x in input().split()]
work=[[int(x) for x in input().split()] for _ in range(N)]
work.sort() #日付の短い順にsortしておく　これいる？

tank=[] #候補を入れる
res=0 #回答
indexlist=[] #バイトは重複不可なので決定済の労働をindexで管理

for i in range(M+1): #日付を後ろから見ていく
  
  for n,item in enumerate(work): #（日付的に働けるかをみて）候補たりうるものを探しheapqに突っ込む
    if item[0]<=i and n not in indexlist:
      heapq.heappush(tank,-item[1])
      indexlist.append(n)
  #print("tank1:",tank)
  
  if len(tank)==0: #候補がなければ次の日へ
    #print("continue.")
    continue

  else: #候補があればもっとも良いのを回答に足す
    res -= heapq.heappop(tank)
    #print("res=",res)
    
  #print("tank2:",tank)
    
print(res)



### FIXED CODE ###

import heapq
#listから複数index削除するやつ
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

[N,M]=[int(x) for x in input().split()]
work=[[int(x) for x in input().split()] for _ in range(N)]

work.sort() #日付の短い順にsortしておく　これいる？いる！！！！
tank=[] #候補を入れる
res=0 #回答
j=0

for i in range(M+1): #日付を後ろから見ていく
  while j<=N-1 and work[j][0]<=i: #forじゃないのはheapqに入れた分はずっと候補なのでもうみなくていいため
    heapq.heappush(tank,-work[j][1])
    j+=1
  #print("tank1:",tank)
  
  if len(tank)==0: #候補がなければ次の日へ
    #print("continue.")
    continue

  else: #候補があればもっとも良いのを回答に足す
    res -= heapq.heappop(tank)
    #print("res=",res)
    
  #print("tank2:",tank)
    
print(res)
### BUGGY CODE ###

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

l = []
ans = 0

for i, item in enumerate(P):
  if i==0:
    ans = 1
    l.append(item)
  else :
    if (item <= min(l)):
      ans += 1
    l.append(item)
      
print(ans)

### FIXED CODE ###

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

m = -1
ans = 0

for i, item in enumerate(P):
  if i==0:
    m = item
    ans += 1
  else :
    if (m >= item):
      m = item
      ans += 1
      
print(ans)
### BUGGY CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
count = 0
s_set = list(set(s))
for i in range(len(s_set)):
    s_count = s.count(s_set[i])
    if s_count > 1:
        count += (s_count * (s_count - 1)) // 2
print(count)


### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
s.sort()
count = 0
num = 1
for i in range(N-1):
    if s[i] == s[i+1]:
        num += 1
    else:
        count += num * (num - 1) // 2
        num = 1
print(count + num * (num - 1) // 2)