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

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
tf = [True] * (m+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(ai, m+1, ai):
      tf[j] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################

if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, n-i-1, p) % p
    temp2 = comb(n, i, p) % p
    temp = temp * temp2 % p
    ans = (ans + temp) % p
    
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10**9 +7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret *= kaijo(n)
  ret %= MOD;
  ret *= gyaku_kaijo(r)
  ret %= MOD;
  ret *= gyaku_kaijo(n-r)
  ret %= MOD;
  return ret




 
n,k = map(int, input().split())
 
################
#p = 10**9 + 7
#def comb(n,k,p):
#  ans = 1
#  for i in range(1,k+1):
#    ans = ans * (n - (i-1)) % p
#    ans = ans * pow(i, p-2, p)
#  return ans
################
 
if k >= n:
  ans = nCr(2*n-1, n) % MOD
else:
  ans = 0
  for i in range(0,k+1):
    temp = (nCr(n-1, i) % MOD) * (nCr(n, i) % MOD) % MOD
    ans = (ans + temp) % MOD
    
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
from  bisect import bisect_right
inf = float("inf")
A = sorted(list(map(int, input().split())))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: -x[1])
cnt = 0
L, R = 0, N
I = []
for b, c in BC:
    idx = bisect_right(A[L:R], c)

    if idx == 0:
        I.append((L, R, 0, c))
        break
    elif idx < b:
        I.append((L+idx, R, idx, c))
        break
    elif idx >= b:
        I.append((L+idx, R, b, c))
        tmp = L
        L += b
        R = tmp + idx

    cnt += 1
    if cnt == M:
        I.append((L, R, 0, c))

S = [0]
for a in A:
    S.append(a+S[-1])

ans = 0
for L, R, x, c in I:
    ans += S[R] - S[L] + x*c

print(ans)




### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
P = [(A[i], 1) for i in range(N)]
for j in range(M):
    B, C = map(int, input().split())
    P.append((C, B))
P.sort(reverse=True)
ans, cnt = 0, N
for v, c in P:
    use = min(c, cnt)
    ans += use*v
    cnt -= use
print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
#ab = []
aida = []
#start = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        if x in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(x)
    if x == 1:
        if y in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(y)
    #ab.append((x, y))

"""
for i in range(len(start)):
    if start[i] in aida:
        print("POSSIBLE")
        exit()
"""
print("IMPOSSIBLE")


### FIXED CODE ###

n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
to = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
# print(to)
for i in range(len(to[0])):
    if n-1 in to[to[0][i]]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

N = int(input())
S =list(str(input()))
a=[]
for i in range(10):
    for k in range(N-2):
        if str(i)==S[k]:
            for u in range(10):
                for j in range(k+1,N-1):
                    if str(u)==S[j]:
                        for y in range(10):
                            for h in range(j+1,N):
                                if str(y)==S[h]:
                                    a.append(S[k]+S[j]+S[h])
print(len(set(a)))

### FIXED CODE ###

N = int(input())
S =list(str(input()))
a=[]
ans=0
for i in range(10):
    for u in range(10):
        for y in range(10):
            moji=[str(i),str(u),str(y)]
            ti=0
            for t in range(N):
                if S[t]==moji[ti]:
                    ti+=1
                    if ti==3:
                        break
            if ti==3:
                ans+=1
                            
                
print(ans)
### BUGGY CODE ###

N=int(input())
alist=list(map(int, input().split()))
alist.sort()
aa=alist[0]
anslist=[0]*N
for i in range(1,N+1):
    anslist[i-1]=alist.count(i)
for ans in anslist:
    print(ans)


### FIXED CODE ###

N=int(input())
alist=list(map(int, input().split()))
anslist=[0]*N
for a in alist:
    anslist[a-1]+=1
for ans in anslist:
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-      

s = input()
dstx, dsty = list(map(int,input().split()))
x = []
y = []
tmp = 0
xy = 0
for i in range(len(s)):
    if(s[i]=='F'):
        tmp += 1
    elif(s[i]=='T' and xy==0):
        x.append(tmp)
        tmp = 0
        xy = 1
    elif(s[i]=='T' and xy==1):
        y.append(tmp)
        tmp = 0
        xy = 0
else:
    if(xy==0):
        x.append(tmp)
    else:
        y.append(tmp)
        
dpx = [{} for i in range(len(x))]
dpy = [{} for i in range(len(y)+1)]
dpx[0][x[0]] = True
dpy[0][0] = True
for i, dx in enumerate(x[1:]):
    for j in dpx[i]:
        dpx[i+1][j+dx] = True
        dpx[i+1][j-dx] = True
for i, dy in enumerate(y):
    for j in dpy[i]:
        dpy[i+1][j+dy] = True
        dpy[i+1][j-dy] = True
    
if(dstx not in dpx[-1] or dsty not in dpy[-1]):
    print('No')
else:
    print('Yes')

### FIXED CODE ###

# -*- coding: utf-8 -*-     
import sys

s = input()
dstx, dsty = list(map(int,input().split()))
x = []
y = []
tmp = 0
xy = 0
for i in range(len(s)):
    if(s[i]=='F'):
        tmp += 1
    elif(s[i]=='T' and xy==0):
        x.append(tmp)
        tmp = 0
        xy = 1
    elif(s[i]=='T' and xy==1):
        y.append(tmp)
        tmp = 0
        xy = 0
else:
    if(xy==0):
        x.append(tmp)
    else:
        y.append(tmp)
dpx = [{} for i in range(len(x))]
dpy = [{} for i in range(len(y)+1)]
dpx[0][x[0]] = True
dpy[0][0] = True
for i, dx in enumerate(x[1:]):
    for j in dpx[i]:
        dpx[i+1][j+dx] = True
        dpx[i+1][j-dx] = True
if(dstx not in dpx[-1]):
    print('No')
    sys.exit()
for i, dy in enumerate(y):
    for j in dpy[i]:
        dpy[i+1][j+dy] = True
        dpy[i+1][j-dy] = True
    
if(dstx not in dpx[-1] or dsty not in dpy[-1]):
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = []

    for use in range(n, 1, -1):
        rest = ans
        nex = now_a[0]
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, max(-1, start-1-rest), -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
        while cnt >= use:
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                for i in range(start, min(end, start+rest)):
                    if now_a[i] > val:
                        break
                    elif now_a[i] == 1:
                        cnt -= 1
                    now_a[i] -= 1
                    rest -= 1
                end = start
        ans_list.append(ans)
    print(n)
    for i in ans_list[::-1]:
        print(i)


main()

### FIXED CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = []

    for use in range(n, 0, -1):
        rest = ans
        nex = now_a[0]
        # restの分だけ戻す
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, -1, -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
                if rest == 0:
                    break
        # 大きい方から使っていく
        while True:
            if cnt < use:
                ans_list.append(ans)
                break
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                for i in range(start, end):
                    if now_a[i] > val:
                        break
                    elif now_a[i] == 1:
                        cnt -= 1
                    now_a[i] -= 1
                    rest -= 1
                    if rest == 0:
                        break
                end = start
    for i in ans_list[::-1]:
        print(i)


main()
### BUGGY CODE ###

N = int(input())
M = N
result = []
i = 2
while True:
    if N % i == 0:
        N = N / i
        result.append(i)
        if N == 1:
            break
    else:
        i += 1
print(str(M) + ": " + " ".join(map(str, result)))



### FIXED CODE ###

N = int(input())
M = N
result = []
i = 2
while i * i <= N:
    while N % i == 0:
        N //= i
        result.append(i)
    i += 1
if N > 1:
    result.append(N)
print(str(M) + ": " + " ".join(map(str, result)))
### BUGGY CODE ###

N=int(input())
x=y=z=1

for i in range(1, N+1, 1):
    print(len([[x,y,z] for x in range(1,i+1,1) for y in range(1,i-x,1) for z in range(1,i-x-y,1) if x*x+y*y+z*z+x*y+y*z+z*x == i]))
  

### FIXED CODE ###

n = int(input())
 
ans = [0] * (n+1)
for x in range(1,110):
    for y in range(1,110):
        for z in range(1,110):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp <= n:
                ans[tmp] += 1
 
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**9] * (lim + 1)
dp[0] = 0

for h in range(lim + 1):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]
        if 0 < rem:
            cns += dp[rem]

        dp[h] = min(cns, dp[h])

print(min(dp[H:lim+1]))


### FIXED CODE ###

H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))
### BUGGY CODE ###

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7

def C(n,m):
    arr = np.zeros((n+1,m+1),int)
    arr[0][0] = 1 
    i = 1 
    while(i < n+1):
        arr[i][0] = 1 
        j = 1 
        while(j< m+1):
            arr[i][j] = (arr[i-1][j] + arr[i-1][j-1]) % MAX 
            j+=1 
        i+=1 
    return(arr[n][m])  

n,k = input().split()
n,k = int(n),int(k) 

for i in range(k):
    ans = (C(n-k+1,i+1) * C(k-1,i) ) % MAX 
    print(ans) 



### FIXED CODE ###

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7

def fact(n):
    ls = [1] 
    for i in range(1,n+1):
        ls.append(ls[i-1]*i) 
    return(ls) 

n,k = input().split()
n,k = int(n),int(k) 

ls = fact(2000)

def C(n,m):
    return ((ls[n]//(ls[m]*ls[n-m])) % MAX)

for i in range(k):
    ans = ( C(n-k+1,i+1) * C(k-1,i) ) % MAX 
    print (ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
result = [max(A[:i] + A[i+1:]) for i in range(N)]
for item in result:
    print(item)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

max_num = max(A)
a = sorted(A)
second = a[-2]

for i in range(N):
    if A[i] == max_num:
        print(second)
    else:
        print(max_num)
### BUGGY CODE ###

import math
from collections import Counter

from scipy.misc import comb


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :return:
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    ret = []
    i = 2
    while 2 <= i <= n:
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 1
    return ret


n, m = map(int, input().split())
MOD = 10 ** 9 + 7

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v, exact=True)
    ans %= MOD
print(ans)


### FIXED CODE ###

import math
from collections import Counter
from functools import reduce
from operator import mul


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


n, m = map(int, input().split())
MOD = 10 ** 9 + 7

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math

N,M=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

alog0=math.log2(alist[0])
alist_log=[]
diff_list=[]
for i in range(N):
  a=alist[i]
  alogi=math.log2(a)  
  alist_log.append(alogi)

#print(alist)
#print(alist_log)

tlist=[0]*N
while(M>0):
  max_value=max(alist_log)
  max_index=alist_log.index(max_value)
  
  alist_log[max_index]-=1
  tlist[max_index]+=1
  M-=1
#print(tlist)

answer=0
for i in range(N):
  answer+=alist[i]//(2**tlist[i])

print(answer)

### FIXED CODE ###

#from heapq import heappush, heappop
import heapq

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

hq=[]
for a in alist:
  heapq.heappush(hq,-a)
  
while(M>0):
  target=-1*heapq.heappop(hq)
  target//=2
  heapq.heappush(hq,-target)
  M-=1

answer_list=[heapq.heappop(hq) for i in range(len(hq))]
#print(answer_list)
print(-sum(answer_list))
### BUGGY CODE ###

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

from fractions import gcd
# def gcd(x, y):
#     if x < y: x, y = y, x
#     while y != 0:
#         x, y = y, x % y
#     return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = {}
    if n % 2 == 0:
        divisor[2] = 1
        # if 2 in divisor:
        #     divisor[2] += 1
        # else:
        #     divisor[2] = 1
        # n //= 2

    i = 3
    while i <= n:
        while n % i == 0:
            try:
                divisor[i] += 1
            except:
                divisor[i] = 1
            n //= i
        i += 2
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)




### FIXED CODE ###

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

from fractions import gcd
from collections import Counter
# def gcd(x, y):
#     if x < y: x, y = y, x
#     while y != 0:
#         x, y = y, x % y
#     return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = Counter()
    while n % 2 == 0:
        divisor[2] += 1
        n //= 2
        
    i = 3
    while i*i <= n:
        while n % i == 0:
            divisor[i] += 1
            n //= i
        i += 2
    if n > 1:
        divisor[n] += 1
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)
### BUGGY CODE ###

from bisect import bisect_right

n = int(input())

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

ans = 0

for x in a:
  i = bisect_right(b, x)
  for y in b[i:]:
    j = bisect_right(c, y)
    for z in c[j:]:
      ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

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

ans = 0
for x in b:
  ans += bisect_left(a, x) * (n - bisect_right(c, x))

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

N,A = map(int, input().split())
X = [int(x) for x in input().split()]

M = sum(X)
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
    
for i in range(N+1):
    dp[i][0][0] = 1
    
for i in range(N):
    for j in range(M+1):
        for k in range(1, N+1):
            if j >= X[i]:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-X[i]][k-1]
            else:
                dp[i+1][j][k] = dp[i][j][k]
        
ans = 0
for k in range(1, N+1):
    if k*A <= M:
        ans += dp[N][k*A][k]
            
print(ans)

### FIXED CODE ###

N,A = map(int, input().split())
X = [int(x) for x in input().split()]

M = sum(X)
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
    
for i in range(N+1):
    dp[i][0][0] = 1
    
for i in range(N):
    for j in range(M+1):
        for k in range(1, N+1):
            if j >= X[i]:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-X[i]][k-1]
            else:
                dp[i+1][j][k] = dp[i][j][k]
        
ans = 0
for k in range(1, N+1):
    if k*A <= M:
        ans += dp[N][k*A][k]
            
print(ans)
### BUGGY CODE ###

import math

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

def pf(x):
  x2=x
  y=int(x/2)
  l=[1]
  sq_x=math.sqrt(x)
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x==x2:
    if x!=1:
      l.append(x)
  return(l)

count=0
if b>a:
  a,b=b,a

l=pf(b)

for i in range(len(l)):
  if l[i]!=0:
    if  a%l[i]==0:
        count+=1
print(count)

### FIXED CODE ###

import math
from fractions import gcd

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

def pf(x):
  x2=x
  y = int(math.sqrt(x))+1
  l=[1]
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x>=y:
    if x!=1:
      l.append(x)
  return(l)

count=0
n=gcd(a,b)

l=pf(n)

len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

cnt = 0
for i in range(n):
  for j in range(i+1,n):
    tgt = l[i] - l[j]
    for k in range(j+1, n):
      if l[k] > tgt:
        cnt += 1
      else:
        break

print(cnt)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

lptr = [-1] * 1001
lptr[0] = n - 1
for i in range(1, 1001):
  maxptr = n -1
  minptr = 0
  fixed = [-1] * n
  cptr = (maxptr + minptr + 1) // 2

  while fixed[cptr] == -1:

#    print(str(cptr)+','+str(l[cptr]))
    if l[cptr] > i:
      fixed[cptr] = 0
      minptr = cptr
    else:
      fixed[cptr] = 1
      maxptr = cptr
    cptr = (maxptr + minptr + 1) // 2
      
  lptr[i] = cptr - fixed[cptr]

#print(lptr)

    
cnt = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    tgt = l[i] - l[j]
    if lptr[tgt] > j:
      cnt += lptr[tgt] - j

print(cnt)
### BUGGY CODE ###

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

L.sort(reverse=True)

#print(L)
for i in range(N):
    L[i] *= -1
count = 0
for i in range(N-2):
    #print(i)
    for j in range(i+1, N-1):
        if -L[i] >= -L[j] * 2:
            break
        data = L[i] - L[j]
        #print(data, L[j + 1 : N])
        #print(bisect.bisect_left(L[j + 1 : N], data))
        count += bisect.bisect_left(L[j + 1 : N], data)

print(count)

### FIXED CODE ###

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

L.sort(reverse=True)

#print(L)
for i in range(N):
    L[i] *= -1
count = 0
for i in range(N-2):
    #print(i)
    for j in range(i+1, N-1):
        if -L[i] >= -L[j] * 2:
            break
        data = L[i] - L[j]
        #print(data, L[j + 1 : N])
        #print(bisect.bisect_left(L[j + 1 : N], data))
        count += bisect.bisect_left(L, data) - (j+1)

print(count)
### BUGGY CODE ###

n = int(input())
a = list(input().split())

a_dict = dict()
for x in a:
    if x not in a_dict:
        a_dict[x] = 1
    else:
        a_dict[x] += 1

sum = 0

for i in a:
    for k, v in a_dict.items():
        if k == i:
            v -= 1
        if v > 1:
            sum += v*(v-1)//2

    print(sum)
    sum = 0


### FIXED CODE ###

n = int(input())
a = list(input().split())

a_dict = dict()
for x in a:
    if x not in a_dict:
        a_dict[x] = 1
    else:
        a_dict[x] += 1

sum = 0
for k, v in a_dict.items():
    sum += v*(v-1)//2
    a_dict[k] = (v*(v-1)//2)-((v-1)*(v-2)//2)

for i in a:
    print(int(sum-a_dict[i]))
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

b = [0] * 60
for x in a:
    for i, temp in enumerate(list(map(int, reversed(bin(x)[2:])))):
        b[i] += temp

ans = 0
d = 1
for x in b:
    ans = (ans + ((x * (n-x)) % MOD) * d) % MOD
    d = d * 2 % MOD

print(ans)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] //= 2
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)