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

import math
import collections


k = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
s = 0
for i in c.values():
  if i == 1:
    s += 0
    continue
  s += math.factorial(i) // (math.factorial(i - 2) * math.factorial(2))

for i in a:
  j = c[i] - 1
  if j == 1:
    print(s - 1)
    continue
  elif j == 0:
    print(s)
    continue
  b = math.factorial(j) // (math.factorial(j - 2) * math.factorial(2))
  y = math.factorial(c[i]) // (math.factorial(c[i] - 2) * math.factorial(2))
  d = y - b
  print(s - d)

### FIXED CODE ###

import collections


k = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
s = 0
for i in c.values():
  s += i * (i - 1) / 2

for i in a:
  j = c[i] - 1
  b = j * (j - 1) // 2
  y = (j + 1) * j // 2
  d = y - b
  print(int(s - d))
### BUGGY CODE ###

s=input()
q=int(input())
query = [input().split() for i in range(q)]

for query_list in query:
    if query_list[0] == '1':
        s = s[::-1]
    else:
        if query_list[1] == '1':
            s = query_list[2] + s
        else:
            s = s + query_list[2]

print(s)

### FIXED CODE ###

s=input()
q=int(input())
query = [input().split() for i in range(q)]

Inv = False #反転しているか
front_str = [] #末尾側
back_str = [] #先頭側

for query_list in query:
    if query_list[0] == '1':
        Inv = not Inv
    else:
        if query_list[1] == '1': #先頭に追加
            if Inv:
                front_str.append(query_list[2])
            else:
                back_str.append(query_list[2])
        else:
            if Inv:
                back_str.append(query_list[2])
            else:
                front_str.append(query_list[2])

answer = "".join(back_str[::-1] + [s] + front_str)

if Inv:
    answer = answer[::-1]

print(answer)
### BUGGY CODE ###

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

ans = 0
A.sort(reverse=True)
#print(A)
for i in range(1,N):
    if i == 1:
        ans += A.pop(0)
        continue
    if i % 2 == 0:
        ans += A[0]
    else:
        ans += A.pop(0)
#print(A)
print(ans)



### FIXED CODE ###

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

ans = 0
A.sort(reverse=True)
#print(A)
from collections import deque
d = deque(A)
for i in range(1,N):
    if i == 1:
        ans += d.popleft()
        continue
    if i % 2 == 0:
        ans += d[0]
    else:
        ans += d.popleft()
#print(A)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
l=[1]+[0 for _ in range(n+5)]

for x in range(n):
    if not x in a:
        l[x+1]+=l[x]
        l[x+2]+=l[x]
print(l[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
l=[1]+[0 for _ in range(n+5)]
if m==0:a=[200000]
for x in range(n):
    if x<a[0]:
        l[x+1]+=l[x]
        l[x+2]+=l[x]
    if x==a[0]:
        if len(a)>=2:a.pop(0)
        else:a[0]=200000
print(l[n]%(10**9+7))
### BUGGY CODE ###



def main():
    import sys
    sys.setrecursionlimit(10 ** 8)

    MAXN = 1005
    MAXV = (MAXN * (MAXN - 1)) // 2
    to = [[] for _ in range(MAXV)]
    ID = [[-1] * MAXN for _ in range(MAXN)]

    def toID(i, j):
        if i > j:
            i, j = j, i
        return ID[i][j]

    visited = [False] * MAXV
    calculated = [False] * MAXV
    dp = [0] * MAXV
    def dfs(v): #DAGの最長経路を求める
        if visited[v]: #すでに訪れたことがある時
            if not calculated[v]: #計算されたことがない時 = ループがある
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            res = dfs(u)
            if res == -1:
                return -1
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

    N = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            ID[i][j] = V
            V += 1
    
    for i in range(N):
        for j in range(N - 1):
            a[i][j] = toID(i, a[i][j]) #対戦相手で管理していたのを試合番号に変える
        for j in range(N - 2):
            to[a[i][j + 1]].append(a[i][j])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

def f(point):
    k = K
    for i in range(N):
        a = A[i]
        f = F[i]
        if a*f > point:
            k -= a - point//f
        if k < 0:
            return False
    return True

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10**12+1
while (r-l) > 1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid
print(r)


### FIXED CODE ###

def f(point):
    k = K
    for i in range(N):
        a = A[i]
        f = F[i]
        if a*f > point:
            k -= a - point//f
        if k < 0:
            return False
    # print(point, k)
    return True

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10**18+1
while (r-l) > 1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

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

X = M // N
for x in range(X, 1, -1):
    r = M - x * (N - 1)
    if r % x == 0:
        print(x)
        exit()
print(1)

### FIXED CODE ###

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

X = M // N
for x in range(X, 1, -1):
    r = M - x * (N - 1)
    if r % x == 0:
        print(x)
        exit()
print(1)
### BUGGY CODE ###

N=int(input())

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

ans=[]
for i in range(4**len(str(N))):
    num=Base_10_to_n(i,4).zfill(len(str(N))+1).replace('0','').replace('1','7').replace('2','5').replace('3','3')
    # print(num)
    if set(list(num))==set(['3','5','7']) and int(num)<=N:
        ans.append(num)
print(len(set(ans)))




### FIXED CODE ###

N=int(input())
N_num=len(str(N))
ans=0

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

for i in range(3,N_num+1):#i桁についての3進数演算
    for j in range(3**i):
        num=Base_10_to_n(j,3).zfill(i).replace('0','3').replace('1','5').replace('2','7')
        if set(list(num))==set(['3','5','7']) and int(num)<=N:
            ans+=1
print(ans)
### BUGGY CODE ###

# 文字列の操作だけでできるか

S = input()
Q = int(input())

T = 0
for i in range(Q):
    Query = list(input().split())
    if len(Query) == 1:
        # T = T ^ 1 (排他的論理和; 0 XOR 1 = 1, 1 XOR 1 = 0)
        T ^= 1
    elif T == 0:
        s = Query[2]
        if Query[1] == '1':
            S = s + S
        else:
            S = S + s
    else:
        s = Query[2]
        if Query[1] == '1':
            S = S + s
        else:
            S = s + S

if T == 1:
    S = S[::-1]

print(S)


### FIXED CODE ###

# キューを使ったアプローチ

from collections import deque

S = deque(input())
Q = int(input())

T = 0
for _ in range(Q):
    Query = list(input().split())
    if len(Query) == 1:
        T ^= 1
    elif T == 0:
        m = Query[2]
        if Query[1] == '1':
            S.appendleft(m)
        else:
            S.append(m)
    else:
        m = Query[2]
        if Query[1] == '2':
            S.appendleft(m)
        else:
            S.append(m)

if T==1:
    S.reverse()

print(''.join(S))
### BUGGY CODE ###

from collections import defaultdict,deque
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=set()
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.add(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)

### FIXED CODE ###

import sys
from collections import defaultdict, deque
 
readline = sys.stdin.readline
n, m, k = map(int, readline().split())
# ab = [list(map(int, readline().split())) for i in range(m)]
# cd = [list(map(int, readline().split())) for i in range(k)]
 
friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
 
suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    # friend[b].append(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    # not_friend[d].append(c)
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)
 
for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)
### BUGGY CODE ###

import sys
from collections import defaultdict
d = defaultdict(int)
input = sys.stdin.readline


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

for i in polls:
    d[i] += 1

max_k_list = sorted([kv[0] for kv in d.items() if kv[1] == max(d.values())])
# max_k_list.sort()

for ans in max_k_list:
    print(ans)


### FIXED CODE ###

import collections

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

c = collections.Counter(polls)
maxval = c.most_common()[0][1]

values, counts = zip(*c.most_common())

ans = []

for i in c.most_common():
    if i[1] == maxval:
        ans.append(i[0])
    else:
        break

ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

h = int(input())
n = 0
import math
while True:
    h = math.floor(h/2)
    n += 1
    if h == 1:
        break
        
print(2**(n+1)-1)

### FIXED CODE ###

h = int(input())
n = 0
import math
while h > 0:
    h = math.floor(h/2)
    n += 1
        
print(2**(n)-1)
### BUGGY CODE ###

n=int(input())
s=input()
R=[]
G=[]
B=[]

for i in range(n):
    if s[i]=="R":
        R.append(i)
    elif s[i]=="G":
        G.append(i)
    else:
        B.append(i)

b=len(B)
ans=0

for j in R:
    for k in G:
        cnt=b
        if 2*j-k in B:cnt-=1
        if 2*k-j in B:cnt-=1
        if (j+k)/2 in B:cnt-=1
        ans+=cnt

print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=list(input())
C=Counter(s)
r,g,b=C["R"],C["G"],C["B"]
ans=r*g*b

for i in range(n-2):
    for j in range(i+1,n-1):
        k=2*j-i
        if k<=n-1 and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                ans-=1

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

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

A = []
B = []
for i in range(a):
    c, d = map(int, input().split())
    A.append(c)
    B.append(d)

ans = 0

for i in range(a*b + 1):
    j = A.index(min(A))
    if(b - B[j] >=0):
        ans += A[j] * B[j]
        b -= B[j]
        A[j] = 1000000
    else:
        ans += A[j] * b
        b = 0
    if(b == 0):
        break
    
print(ans)

### FIXED CODE ###

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

A = []

for i in range(a):
    c= list(map(int, input().split()))
    A.append(c)

ans = 0

A.sort(key=lambda x:x[0])


for j in range(a+1):
    if(b - A[j][1] >=0):
        ans += A[j][0] * A[j][1]
        b -= A[j][1]
    else:
        ans += A[j][0] * b
        b = 0
    if(b == 0):
        break
    
print(ans)
### BUGGY CODE ###


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

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        for k in range(n + 1 - i - j):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n and not flg:
                flg = True
                print(i, j, k)

if not flg:
    print(-1, -1, -1)


### FIXED CODE ###


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

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        k = (y - 10000 * i - 5000 * j) // 1000
        if i + j + k == n and not flg:
            flg = True
            print(i, j, k)
            break
    else:
        continue
    break

if not flg:
    print(-1, -1, -1)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

fact = [1 for _ in range(N*M+1)]
for i in range(1, N*M+1):
    fact[i] = fact[i-1] * i

def inv(val):
    return pow(val, MOD-2, MOD)

def combination(n, m):
    return fact[n] * inv(fact[n-m]*fact[m]) % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c = c * (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)
### BUGGY CODE ###

n = int(input())

cnt = 0

for c in range(n) :
    cnt += c
print(cnt)

### FIXED CODE ###

n = int(input())

cnt = 0

if (n-1)%2 == 0 :
    cnt = ((n-1)//2) * (n)
else :
    cnt = ((n-1)//2) * (n) + n//2

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

import sys
from collections import deque


def main():
    n, m = map(int, input().split())
    lines = sys.stdin.readlines()

    cities = {}
    mem_city = deque()
    for i in range(m):
        p, y = map(int, lines[i].split())
        mem_city.append((p, y))
        if p in cities:
            cities[p].append(y)
        else:
            cities[p] = [y]
    # print(cities)
    for key in cities:
        cities[key].sort()
    # print(cities)

    outputs = [None] * m
    for iter, p in enumerate(mem_city):
        idx = cities[p[0]].index(p[1]) + 1
        outputs[iter] = "{:06d}{:06d}".format(p[0], idx)

    for output in outputs:
        print(output)
    return


main()

### FIXED CODE ###

import sys

def main():
    n, m = map(int, input().split())
    lines = sys.stdin.readlines()

    cities = {}
    for i in range(m):
        p, y = map(int, lines[i].split())
        if p in cities:
            cities[p].append((i, y))
        else:
            cities[p] = [(i, y)]

    outputs = [None] * m
    for pref, city_list in cities.items():
        city_list.sort(key=lambda x: x[1])
        #print(pref, city_list)
        city_no = 1
        for city in city_list:
            outputs[city[0]] = "{:06d}{:06d}".format(pref, city_no)
            city_no += 1

    for output in outputs:
        print(output)
    return


main()
### BUGGY CODE ###

import bisect

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

ans = 0

d = []

for i in range(n):
	for j in range(i+1,n):
		index = bisect.bisect_left(l,l[i]+l[j])
		for k in range(index):
			if k == i or k == j:
				continue
			if l[j] < l[k] + l[i]:
				tmp = []
				tmp.append(i)
				tmp.append(j)
				tmp.append(k)
				tmp.sort()
				if tmp not in d:
					d.append(tmp)
					ans += 1

print(ans)


### FIXED CODE ###

import bisect

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

l.sort()
#print(l)
ans = 0
for i in range(n-1):
	a = l[i]
	for j in range(i+2,n):
		b = l[j]
		c = bisect.bisect_left(l,b-a+1)
		if j - c > 0:
			if i >= c:
				ans += j-i-1
			else:
				ans += j-c
		#print(i,j,c,ans)

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

a = input()
s = input()
n = int(s, 2)

for i in range(len(s)):
    x = n ^ (1 << len(s) - 1 - i)
    cnt = 0
    while x != 0:
        ss = bin(x)[2:]
        cnt += 1
        num1 = ss.count("1")
        rs = ss[::-1]
        res = 0
        for j in range(len(rs)):
            if rs[j] == "1":
                res += pow(2, j, num1)
                res %= num1
        x = res
    print(cnt)

### FIXED CODE ###

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
memo = [None] * 300000
def do2(x):
    if memo[x] is not None:
        return memo[x]
    cnt = 0
    while x != 0:
        x = x % popcount(x)
        cnt += 1
    memo[x] = cnt
    return cnt

def do():
    ll = int(input())
    s = input()
    n = int(s, 2)

    x = n
    cnt = 0
    ss = bin(x)[2:]
    cnt += 1
    num1 = ss.count("1")
    num1m = num1 - 1
    num1p = num1 + 1
    rs = ss[::-1]
    res1m = 0
    res1p = 0
    for j in range(len(rs)):
        if rs[j] == "1":
            if num1m != 0 and num1m != -1:
                res1m += pow(2, j, num1m)
                res1m %= num1m
            res1p += pow(2, j, num1p)
            res1p %= num1p

    #print(res1m, res1p, num1m, num1p)
    for i in range(len(s)):
        #print("i", i)
        if s[i] == "1": # 0になるから
            #print("down")
            #print(res1m, pow(2, ll - i -1, num1m))
            if num1m == 0 or num1m == -1:
                print(0)
                continue
            x = res1m - pow(2, ll - i -1, num1m)
            x %= num1m
        elif s[i] == "0": # 1になるから
            #print("up")
            #print(res1p, pow(2, ll - i -1, num1p))
            x = res1p + pow(2, ll - i-1, num1p)
            x %= num1p

        if x == 0:
            print(1)
            continue
        print(do2(x) + 1)
do()
### BUGGY CODE ###

def n_ary_notation(N, n):
  if N == 0:
    return '0'
  else:
    s = ''
    while N:
      s = str(N % abs(n)) + s
      N -= N % abs(n)
      N //= n
    return s
strL = input()
N = 21
M = 61
K = 2
sl = int(strL) - 1
while True:
  K += 1
  L = n_ary_notation(sl, K)
  N = len(L) * 2
  M = K * (len(L) - 1)
  for l in L:
    M += int(l) + 1
  if N < 21 and M < 61:
    break
print(N, M)
for i, l in enumerate(L[:-1]):
  k = len(L) - 1 - i
  print(2 * i + 1, 2 * i + 3, int(l) * K ** k)
  for j in range(int(l)):
    print(2 * i + 1, 2 * i + 2, j * K ** k)
for i in range(int(L[-1]) + 1):
  print(2 * len(L) - 1, 2 * len(L), i)
for k in range(len(L) - 1):
  s = 2 * (len(L) - k)
  for i in range(K):
    print(2 * (len(L) - k - 1), 2 * (len(L) - k), i * K ** k)

### FIXED CODE ###

L = int(input())
R = 0
while True:
  R += 1
  if 2 ** R > L:
    R -= 1
    break
N = R + 1
M = 2 * R
_L = L
for r in range(R, 0, -1):
  if _L - 2 ** (r - 1) >= 2 ** R:
    M += 1
    _L -= 2 ** (r - 1)
print(N, M)
for i in range(R):
  print(i + 1, i + 2, 2 ** i)
  print(i + 1, i + 2, 0)
for r in range(R, 0, -1):
  if L - 2 ** (r - 1) >= 2 ** R:
    print(r, N, L - 2 ** (r - 1))
    L -= 2 ** (r - 1)
### BUGGY CODE ###

a, b = map(int,input().split())
if a < b:
    buf = a
    a = b
    b = buf
while b != 0:
    a, b = b, a % b
gcd = a
count = 1
if gcd % 2 == 0:
    count += 1
if gcd % 3 == 0:
    count += 1


def hantei(num):
    flag = True
    for i in range(2, int(num**0.5+1)):
        if num % i == 0:
            flag = False
    return flag


if gcd < 5:
    print(count)
else:
    for i in range(5, gcd + 1):
        if gcd % i == 0 and hantei(i) == True:
            count += 1
    print(count)

### FIXED CODE ###

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

a, b = map(int,input().split())
g = gcd(a,b)
count = 0
for i in range(2, int(g**0.5)+2):
    if g % i == 0:
        count += 1
        while g % i == 0:
            g //= i
if g != 1:
    count += 1
print(count+1)
### BUGGY CODE ###

from statistics import median

N = int(input())
num_lis = [int(_) for _ in input().split()]

for i in range(N):
    print(median(num_lis[:i] + num_lis[i + 1:]))

### FIXED CODE ###


N = int(input())
X = [int(_) for _ in input().split()]
tmp = sorted(X)

one = N // 2 - 1
two = N // 2

for x in X:
    if x <= tmp[one]:
        print(tmp[two])
    else:
        print(tmp[one])
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf') for i in range(N)]
dp[0]=0
for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]  = min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf') for i in range(N)]
dp[0]=0
for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]  = min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[N-1])
### BUGGY CODE ###

import math
import numpy as np
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)
ma=sorted(ma,key=lambda x:x[1])
ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
for i in range(n):
    dp[i][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(1,h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print(dp[-1][-1])

### FIXED CODE ###

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print(dp[-1][-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo


def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = bisect_left(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


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

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


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

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


if __name__ == "__main__":
    main()