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

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1):
        tmp = num * i
        if dp[tmp]: dp[tmp] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)
#amax = 10**6

cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)
### BUGGY CODE ###

from collections import Counter
from copy import deepcopy

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  copy_a = deepcopy(a)
  copy_a.pop(i)
  cnt = Counter(copy_a)
  ans = 0
  for _,c in cnt.items():
    if c >= 2:
      ans += c*(c-1)//2
  print(ans)



### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int,input().split()))
cnt = dict(Counter(a))
ans = 0
for _,c in cnt.items():
  if c >= 2:
    ans += c*(c-1)//2
    
for i in range(n):
  pop_i = a[i]
  # n(n-1)/2 - (n-1)(n-2)/2 = n-1
  dif = cnt[pop_i]-1
  print(ans-dif)
### BUGGY CODE ###

def main():
    S = input()

    tmp = [[0] * len(S)] * (10 ** 6)
    tmp[0] = [1] * len(S)

    for i in range(10**6):
        for j, s in enumerate(S):
            if s == 'R':
                tmp[i+1][j+1] += tmp[i][j]
            if s == 'L':
                tmp[i+1][j-1] += tmp[i][j]
        tmp[i+2] = [0] * len(S)
        if i >= 2:
            if tmp[i] == tmp[i-2]:
                if i % 2 == 0:
                    print(*tmp[i])
                    exit()
                else:
                    print(*tmp[i-1])
                    exit()
main()

### FIXED CODE ###

def runlength(S):
    d = []
    cnt = 1
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            d.append(cnt)
            cnt = 1
        else:
            cnt += 1
    else:
        d.append(cnt)
    return d


def main():
    S = input()

    d = runlength(S)
    ans = [0] * len(S)
    pre = 0
    for i in range(0,len(d),2):
        tmp = d[i] + d[i+1]
        if d[i] % 2 == 0:
            ans[pre+d[i]-1] = tmp // 2
            ans[pre+d[i]] = tmp - ans[pre+d[i]-1]
        else:
            ans[pre+d[i]] = tmp // 2
            ans[pre+d[i]-1] = tmp - ans[pre+d[i]]

        pre += tmp

    print(*ans)






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

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)


for i in lis[-1]:
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
queue = []
while True:
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if not [i,j] in queue and a[i][j]=='#':
                queue += [[i,j]]
                l += [[i,j]]
    if len(queue)==h*w:
        break
    ans += 1
    for l_ in l:
        a[l_[0]-1] = a[l_[0]-1][:l_[1]]+'#'+a[l_[0]-1][l_[1]+1:]
        a[l_[0]] = a[l_[0]][:l_[1]-1]+'###'+a[l_[0]][l_[1]+2:]
        a[l_[0]+1] = a[l_[0]+1][:l_[1]]+'#'+a[l_[0]+1][l_[1]+1:]
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[-1 for _ in range(W)] for _ in range(H)]

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return max([max(item) for item in footprint])

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                res = max(res, bfs(i,j))
    
    print(res)
        


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':

                que = deque([[i,j]])
                footprint = [[-1 for _ in range(W)] for _ in range(H)]
                footprint[i][j] = 0

                while que:
                    a, b = que.popleft()
                    c = footprint[a][b]
                    if c > res:
                        res = c

                    if a != 0 and footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                        que.append([a-1, b])
                        footprint[a-1][b] = c + 1
                    if a != H-1 and footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                        que.append([a+1, b])
                        footprint[a+1][b] = c + 1
                    if b != 0 and footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                        que.append([a, b-1])
                        footprint[a][b-1] = c + 1
                    if b != W-1 and footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                        que.append([a, b+1])
                        footprint[a][b+1] = c + 1

    print(res)
        


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

n = int(input())
s = [input() for i in range(n)]
from collections import Counter
s1 = Counter(s)
s2 = list(set(s))
s2.sort()
for i in range(len(s2)):
    if s1[s2[i]] == max(s1.values()):
        print(s2[i])

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
from collections import Counter
s1 = Counter(s)
max_s = max(s1.values())
ans = []
for k,v in s1.items(): 
    if v == max_s:
        ans.append(k)
ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

from sys import stdin
s = (stdin.readline().rstrip())
ans = 0
while s.count("ABC") != 0:
    ans += s.count("ABC")
    s = s.replace("ABC","BCA")
print(ans)

### FIXED CODE ###

from sys import stdin
s = (stdin.readline().rstrip())
s = s.replace("BC","D")
ans = 0
acc = 0

for i in s:
    if i == "B" or i == "C":
        acc = 0
        continue
        
    if i == "A":
        acc += 1
    
    if i == "D":
        ans += acc

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

def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

def lcm(x,y): return x*y//gcd(x,y)

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

for i in range(n):
    ans += l//a[i]
    ans %= mod

print(ans)

### FIXED CODE ###

def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

def lcm(x,y): return x*y//gcd(x,y)

n = int(input())
a = [int(i) for i in input().split()]

ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

for i in range(n):
    ans += l//a[i]

print(ans%mod)
### BUGGY CODE ###

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

K=II()
S=input()
L=len(S)
FACT=FLIST(K+L)
def NCR(n, r):
    res = FACT[n-r]
    res *= FACT[r]
    res %= DVSR
    res = INV(res)
    res *= FACT[n]
    res %= DVSR
    return res

ans = 0
for i in range(K+1):
    v = NCR(L+K-i-1, L-1)
    v *= POW(25, K-i)
    v %= DVSR
    v *= POW(26, i)
    v %= DVSR
    ans += v
    ans %= DVSR

print(ans)


### FIXED CODE ###

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

K=II()
S=input()
L=len(S)
FACT=FLIST(K+L)
def NCR(n, r):
    res = FACT[n-r]
    res *= FACT[r]
    res %= DVSR
    res = INV(res)
    res *= FACT[n]
    res %= DVSR
    return res

ans = 0
for i in range(K+1):
    v = NCR(L+K-i-1, L-1)
    v *= POW(25, K-i)
    v %= DVSR
    v *= POW(26, i)
    v %= DVSR
    ans += v

print(ans % DVSR)
### BUGGY CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

### FIXED CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
AM = []
AP = []

for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)
  minus = i+1 - A[i]
  AM.append(minus)
  
ans = 0 

for j in range(N):
  ans += AP.count(j) * AM.count(j)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
AM = []
AP = []
AMlist = [0] * N
APlist = [0] * N

for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)  
  if AP[i] <= N:
    APlist[AP[i]-1] += 1
  minus = i+1 - A[i]
  AM.append(minus)
  if AM[i] > 0 and AM[i] <= N:
    AMlist[AM[i]-1] += 1
    
ans = 0

for j in range(N):
  ans += APlist[j] * AMlist[j]

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

mod = 10**9 + 7

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i

print(ans%mod)

### FIXED CODE ###

mod = 10**9 + 7

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i % mod

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

n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[2*n*[0]for _ in range(n+1)]
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  dp[i][0]=0
  for k in range(i):
    a=0
    ind=2*n
    while ind:
      a+=bit[i][ind-1]
      ind-=ind&-ind
    if w[k]!=0:
      ind=w[k]
      while ind:
        a-=bit[i][ind-1]
        ind-=ind&-ind
    dp[i][0]+=w[k]+a-k
    ind=w[k]+1
    while ind<=2*n:
      bit[i][ind-1]+=1
      ind+=ind&-ind
for j in range(n):
  for i in range(n+1):
    ba=0
    ind=2*n
    while ind:
      ba+=bit[i][ind-1]
      ind-=ind&-ind
    if b[j]!=0:
      ind=b[j]
      while ind:
        ba-=bit[i][ind-1]
        ind-=ind&-ind
    if i==0:
      dp[i][j+1]=dp[i][j]+b[j]+ba-(i+j)
    else:
      dp[i][j+1]=dp[i][j]+(b[j]+ba-(i+j))
      wa=0
      ind=2*n
      while ind:
        wa+=bit[i-1][ind-1]
        ind-=ind&-ind
      if w[i-1]!=0:
        ind=w[i-1]
        while ind:
          wa-=bit[i-1][ind-1]
          ind-=ind&-ind
      dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+wa-(i+j)))
    ind=b[j]+1
    while ind<=2*n:
      bit[i][ind-1]+=1
      ind+=ind&-ind
print(dp[n][n])

### FIXED CODE ###

n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[0]*2*n
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  bitt=bit[:]
  for j in range(n):
    a=0
    k=2*n
    while k:
      a+=bitt[k-1]
      k-=k&-k
    if w[j]!=0:
      k=w[j]
      while k:
        a-=bitt[k-1]
        k-=k&-k
    dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a+w[j]-(i+j))
    k=w[j]+1
    while k<=2*n:
      bitt[k-1]+=1
      k+=k&-k
    if i!=n:
      a=0
      k=2*n
      while k:
        a+=bitt[k-1]
        k-=k&-k
      if b[i]!=0:
        k=b[i]
        while k:
          a-=bitt[k-1]
          k-=k&-k
      dp[i+1][j+1]=dp[i][j+1]+a+b[i]-(i+j+1)
  if i!=n:
    a=b[i]-i
    k=2*n
    while k:
      a+=bit[k-1]
      k-=k&-k
    if b[i]!=0:
      k=b[i]
      while k:
        a-=bit[k-1]
        k-=k&-k
    dp[i+1][0]=dp[i][0]+a
    k=b[i]+1
    while k<=2*n:
      bit[k-1]+=1
      k+=k&-k
print(dp[n][n])
### BUGGY CODE ###

B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
for i in range(2,B+W+1):
   inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
inv = 1
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  inv *= magick
  p += consts_B[i]*inv
  q += consts_W[i]*inv

### FIXED CODE ###

B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
inv_2 = [0]+[magick]
for i in range(2,B+W+1):
  inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]
  inv_2 += [inv_2[-1]*magick % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  p += consts_B[i]*inv_2[i+1]
  q += consts_W[i]*inv_2[i+1]
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
_a = set(a)
for x in _a:
    y = a.count(x)
    if y < x:
        ans += y
    elif y > x:
        ans += y - x
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
c = Counter(a)
for key in c:
    if c[key] < key:
        ans += c[key]
    elif c[key] > key:
        ans += c[key] - key
print(ans)
### BUGGY CODE ###

n= int(input())
a=[]
k=0
for _ in range(n):
  a.append(int(input()))
h=max(a)
for i in range(n):
  if a[i]==h:
    a.pop(i)
    print(max(a))
    a.insert(i,h)
  else:
    print(h)

### FIXED CODE ###

n=int(input())
d=[]
for i in range(n):
  d.append(int(input()))
x=sorted(d)
for j in range(n):
  if d[j]==x[-1]:
    print(x[-2])
  else:
    print(x[-1])
### BUGGY CODE ###

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

def is_triangle(a,b,c):
    if a < b + c and b < a + c:
        return True
    else:
        return False

l.sort(reverse=True)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if is_triangle(l[i], l[j], l[k]):
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

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

l.sort(reverse=True)

ans = 0

#1番長い辺(a)は固定する
for i in range(n - 2):
    #2番目に長い辺(b)＝次に長い辺とする
    j = i + 1
    #3番目の長さの辺(c)＝リストの中で最短の辺からスタート
    k = n - 1

    while j < k:
        #b<a+c,c<a+b は自明。a<b+cを判定する。
        #満たす場合、このbにおいて、cまでの全ての要素は条件を満たす(cが小さいほうから攻めているから)
        if l[i] < l[j] + l[k]:
            ans += k - j
            j += 1
        #満たさない場合、cを次に長い辺として再度判定。
        else:
            k -= 1

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

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
A_sum_of_combination_minus1={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        A_sum_of_combination[k] = len(list(combinations( range(v), 2)))
    else:
        A_sum_of_combination[k] = 0
    
    if (v-1) >= 2:
        A_sum_of_combination_minus1[k] = len(list(combinations( range(v-1), 2)))
    else:
        A_sum_of_combination_minus1[k] = 0

sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        ans = sum_all - A_sum_of_combination[i] + A_sum_of_combination_minus1[i]
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
A_sum_of_combination_minus1={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= (v-i)/(i+1)
        
        A_sum_of_combination[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination[k] = 0
    
    if (v-1) >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= ((v-1)-i)/(i+1)
        
        A_sum_of_combination_minus1[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination_minus1[k] = 0

sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        ans = sum_all - A_sum_of_combination[i] + A_sum_of_combination_minus1[i]
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)
### BUGGY CODE ###

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

#output
import math

A1 = []
for k in range(2, int(math.sqrt(A))+1):
    l = 1
    for i in range(2, math.floor(math.sqrt(k))+1):
        l *= k % i
    if l != 0 and A % k == 0:
        A1.append(k)
    else:
        pass
B1 = []
for k in range(2, int(math.sqrt(B))+1):
    l = 1
    for i in range(2, math.floor(math.sqrt(k))+1):
        l *= k % i
    if l != 0 and B % k == 0:
        B1.append(k)
    else:
        pass
        
C = set(A1) & set(B1)

print(len(C)+1)

### FIXED CODE ###

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

#output
import math

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
A1 = prime_factors(A)
B1 = prime_factors(B)        
C = set(A1) & set(B1)

print(len(C)+1)