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

import sys
input = sys.stdin.readline

import math
import collections

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n = int(input())
    a_li = list(map(int, input().rstrip().split()))

    for i in range(n):
        li = a_li.copy()
        li.pop(i)
        c = collections.Counter(li)
        ans = 0
        for k, v in c.items():
            if v > 1:
                ans += combinations_count(v, 2)

        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

import collections

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def main():
    n = int(input())
    a_li = list(map(int, input().rstrip().split()))
    c = collections.Counter(a_li)
    total = 0
    dict_1 = {}
    dict_2 = {}
    for k, v in c.items():
        if v > 1:
            num = combinations_count(v, 2)
            total += num
            dict_1[k] = num
            if v - 1 > 1:
                dict_2[k] = combinations_count(v-1, 2)
            else:
                dict_2[k] = 0
        else:
            dict_1[k] = 0
            dict_2[k] = 0

    for a in a_li:
        ans = total - dict_1[a] + dict_2[a]
        print(ans)

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

s = list(input())
q = int(input())

rev = False
for _ in range(q):
    query = input().split()

    if query[0] == '1' and not(rev):
        rev = True
    elif query[0] == '1' and rev:
        rev = False

    elif query[0] == '2' and query[1] == '1' and not(rev):
        #s = query[2] + s
        s.insert(0, query[2])
    elif query[0] == '2' and query[1] == '1' and rev:
        #s += query[2]
        s.append(query[2])

    elif query[0] == '2' and query[1] == '2' and not(rev):
        #s += query[2]
        s.append(query[2])
    elif query[0] == '2' and query[1] == '2' and rev:
        #s = query[2]+s
        s.insert(0, query[2])

ans = ''
if rev:
    s.reverse()
    ans = ''.join(s)
else:
    ans = ''.join(s)

print(ans)


### FIXED CODE ###

s = input()
q = int(input())

sl = ['']*(q*2+2)
sl[q] = s
m = q-1
u = q+1
rev = False
for _ in range(q):
    query = input().split()

    if query[0] == '1' and not(rev):
        rev = True
    elif query[0] == '1' and rev:
        rev = False

    elif query[0] == '2' and query[1] == '1' and not(rev):
        sl[m] = query[2]
        m -= 1

    elif query[0] == '2' and query[1] == '1' and rev:
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and not(rev):
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and rev:
        sl[m] = query[2]
        m -= 1

if rev:
    sl[q] = s[::-1]
    sl.reverse()
    print(''.join(sl))
else:
    print(''.join(sl))
### BUGGY CODE ###

def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
while next_place not in places:
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)

### FIXED CODE ###

def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
virgin = [True] * n
virgin[0] = False
while virgin[next_place]:
  virgin[next_place] = False
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)
### BUGGY CODE ###

def euclidean(a, b):
    r = a % b
    if r == 0:
        return b
    return euclidean(b,r)


N = int(input())

s = 0

for i in range(N):
    for j in range(N):
        ss = euclidean(i+1,j+1)
        for k in range(N):
            s +=euclidean(ss,k+1)

print(s)

### FIXED CODE ###

import math


N = int(input())

s = 0

for i in range(N):
    for j in range(N):
        ss = math.gcd(i+1,j+1)
        for k in range(N):
            s +=math.gcd(ss,k+1)

print(s)
### BUGGY CODE ###

n = int(input())

ans = 10**10
for a in range(6):
    for b in range(3):
        for c in range(6):
            for d in range(6):
                for e in range(6):
                    for f in range(6):
                        for g in range(2):
                            for h in range(4):
                                for i in range(8):
                                    for k in range(9):
                                        for l in range(9):
                                            for m in range(2):
                                                if 1*a + 6*b + 36*c + 6**3*d + 6**4*e + 6**5*f + 6**6*g + 9*h + 9**2*i + 9**3*k + 9**4*l + 9**5*m == n:
                                                    ans = min(ans, a+b+c+d+e+f+g+h+i+k+l+m)
print(ans)

### FIXED CODE ###

n = int(input())

dp = [10**7 for i in range(n+1)]
dp[0] = 0
for i in range(n+1):
    for j in range(7):
        if i >= 6**j:
            dp[i] = min(dp[i], dp[i-6**j]+1)
    for k in range(6):
        if i >= 9**k:
            dp[i] = min(dp[i], dp[i-9**k]+1)
print(dp[n])
### BUGGY CODE ###

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

if a == b:
    print(a)

elif b <=10:
    ans = a
    for i in range(a+1, b+1):
        ans = ans ^ i
    print(ans)

else:
    tmpa = ""
    min_len = len(bin(a).split("b")[1])
    for i in range(min_len):
        tmpa += str(0)
    final_a = str(1) + tmpa
    final_a = int(final_a,2)
    
    tmpb = "1"
    min_len = len(bin(a).split("b")[1])
    for i in range(min_len-1):
        tmpb += str(0)
    final_b = int(tmpb,2)

    ans1 = a
    for i in range(a+1, final_a):
        ans1 = ans1 ^ i
    
    ans2 = final_b
    for i in range(final_b+1,b+1):
        ans2 = ans2 ^ i

    print(ans1 ^ans2)

### FIXED CODE ###

import numpy as np
a, b= map(int, input().split())
if a % 2 ==0:
    start = a
    remain_before = 0
else:
    start = a+1
    remain_before = a

if b % 2 ==0:
    end = b-1
    remain_after = b
else:
    end = b
    remain_after = 0

if ((end+1-start) /2) %2 == 0:
    num = 0
else:
    num = 1

print(remain_before ^ num ^ remain_after)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    target = str(i).zfill(3)
    char_idx = 0
    for c in S:
        if c == target[char_idx]:
            char_idx += 1

        if char_idx == 3:
            ans += 1
            break

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    target = str(i).zfill(3)
    char_idx = 0
    for c in S:
        if c == target[char_idx]:
            char_idx += 1

        if char_idx == 3:
            ans += 1
            break

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

S = input()
K = int(input())
N = len(S)

s = sorted(S)
s = s[0:4]

L = []
c = 0
for x in s:
    for i in range(N):
        if S[i] == x:
            for j in range(i+1,N+1):
                a = S[i:j]
                if a not in L:
                    L.append(a)
                    c += 1
    if c >= K:
        break
L.sort()
print(L[K-1])

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)

l = []
for i in range(N):
    for j in range(i+1,min(i+K+1,N+1)):
        s = S[i:j]
        l.append(s)
l = list(set(l))
l.sort()
print(l[K-1])
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N,K = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

pn1 = p - 1

ans = 0
for i in range(N-K+1):
    sp = sum(pn1[i:i+K])
    ans = max(sp,ans)
print(ans/2+K)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N,K = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

pn1 = p - 1

ans = sum(pn1[:K])
spb = ans
for i in range(N-K):
    sp = spb -pn1[i] + pn1[i+K]
    #print(sp,spb,pn1[i],pn1[i+K])
    ans = max(sp,ans)
    spb = sp
print(ans/2+K)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=0
m=len(a)

def todo(i,b):
    c=list(set(b))
    sum=0
    for i in range(len(c)):
        if b.count(c[i])>1:
            k=b.count(c[i])
            sum+=k*(k-1)//2
    print(sum)

for i in range(m):
    d=a.copy()
    d.pop(i)
    todo(i,d)

### FIXED CODE ###

import collections
from collections import defaultdict

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

dict = defaultdict(int)
for i in l:
    dict[i]+=1

ans = 0
for v in dict.values():
    ans += int((v*(v-1)) // 2)

for k in l:
    print(ans - (dict[k] - 1))
### BUGGY CODE ###

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

for _ in range(m):
    b, c = map(int, input().split())
    for i in range(n):
        if a[i] < c:
            a[i] = c
            b -= 1
            if b == 0:
                a = sorted(a)
                break
print(sum(a))
        



### FIXED CODE ###

import sys
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = []

for _ in range(m):
    b += [list(map(int, input().split()))]
b = sorted(b, key=lambda x: x[1], reverse=True)

for i in range(m):
    for j in range(b[i][0]):
        if a[0] < b[i][1]:
            a.pop(0)
            a.append(b[i][1])
        else:
            print(sum(a))
            sys.exit()
print(sum(a))
### BUGGY CODE ###

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


import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
ab2 = [[0]] * (N+1)
for j in range(M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
for i in ab2[1][1:]:
    q.put(i)
    cnt += 1
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')        
    
    

### FIXED CODE ###

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

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

import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
for i in range(M):
    if ab[i][0] == 1:
        q.put(ab[i][1])
        cnt += 1
    else :break
ab2 = [[0]] * (N+1)
for j in range(i,M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')
### BUGGY CODE ###

import itertools
import _pickle

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    for x in range(N):
        tmp = _pickle.loads(_pickle.dumps(A, -1))
        del tmp[x]
        result = list(filter(lambda t: t[0] == t[1], list(itertools.combinations(tmp, 2))))
        print(len(result))


### FIXED CODE ###

import sys
import itertools
from collections import Counter
sys.setrecursionlimit(10**8)
if __name__ == "__main__":
    N = int(input())
    A = input().split()
    counter = Counter(A)
    result = 0
    for c in counter.values():
        result += c*(c-1)//2
    for a in A:
        k = counter[a]
        print(result - k*(k-1)//2 + (k-1)*(k-2)//2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

print(ans)






### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
    mul %= mod
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

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

import numpy as np

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
dp = np.zeros(K + 1, np.bool)

for i in range(1, K + 1):
    for j in range(N):
        if i >= A[j]:
            dp[i] |= dp[i - A[j]] ^ True
# print(dp)
print('First' if dp[K] else 'Second')


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
dp = [False] * (K + 1)

for i in range(1, K + 1):
    for a in A:
        if i >= a:
            dp[i] |= dp[i - a] ^ True
print('First' if dp[K] else 'Second')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
print(dp[N][W])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
print(dp[N][W])
### BUGGY CODE ###

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

start = M // N
for i in range(start, 0, -1):
    if M % i == 0:
        print(i)
        break


### FIXED CODE ###

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

start = M // N
for i in range(start, 0, -1):
    if M % i == 0:
        print(i)
        break
### BUGGY CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
BC = sorted(BC, key=lambda x: x[1], reverse=True)


def f(a, n, v):
    count = 0
    for i in range(min(n, len(a))):
        if a[i] < v:
            count += 1
        else:
            break
    return v * count, a[count:]


sum__ = 0
for num, val in BC:
    if len(As) == 0 or As[0] >= val:
        break
    sum_, As = f(As, num, val)
    sum__ += sum_

print(sum__ + sum(As))


### FIXED CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
now = 0
for val, num in BC_:
    if now >= len(As) or As[now] >= val:
        break

    if As[min(num - 1 + now, len(As) - 1)] < val:
        sum_ = val * min(num, len(As) - now)
        now += min(num, len(As) - now)
    else:
        count = 0
        for i in range(min(num, len(As)-now)):
            if As[i + now] < val:
                count += 1
            else:
                break
        sum_ = val * count
        now += count
    sum__ += sum_

print(sum__ + sum(As[now:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
c = a.copy()
for i in a:
    print(a.index(min(c))+1,end= " ")
    c.remove(min(c))

### FIXED CODE ###

n = int(input())
a = []
li = [0] * n
a = list(map(int,input().split()))
for i in range(n):
    li[a[i]-1] = i+1
for i in range(n):
    print(li[i], end = " ")
### BUGGY CODE ###

from collections import deque

N , M = map(int, input().split())
room = [-1 for k in range(N)]
L = [[] for k in range(M)]
for k in range(M):
    L[k] = list(map(int, input().split()))
nextvisit =[[1]]
visited =[0 for k in range(N)]
visited[0]=1
not_used = [k for k in range(M)]
for j in range(M-1):
    nextvisit.append([])
    for visit in nextvisit[0]:

        """
        print("L=",L)
        print("next=",nextvisit[j])
        print("not_used", not_used)
        """
        erase = []
        for k in not_used:
            if visit == L[k][1]:
                if visited[L[k][0]-1] == 0:
                    nextvisit[1].append(L[k][0])
                    visited[L[k][1]-1] = 1
                    visited[L[k][0]-1] = 1
                    room[L[k][0]-1] = L[k][1]
                erase.append(k)
                
            if visit == L[k][0]:
                if visited[L[k][1]-1] == 0:
                    nextvisit[1].append(L[k][1])
                    visited[L[k][0]-1] = 1
                    visited[L[k][1]-1] = 1
                    room[L[k][1]-1] = L[k][0]  
                erase.append(k)

        not_used = list(set(not_used)-set(erase))
    del nextvisit[0]
    
    if len(not_used) == 0:
        break
print("Yes")
if N >2:
    for k in range(1, N):
        print(room[k])
if N ==2:
    print(1)

### FIXED CODE ###

N, M = map(int, input().split())
nextroom = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  nextroom[A-1].append(B-1)
  nextroom[B-1].append(A-1)

sgn = [-1 for _ in range(N)]
sgn[0] = 0

depth = [float('inf') for _ in range(N)]
depth[0] = 0

now = [0]
nextvisit = []
for j in range(1, M+1):
  for n in now:
    for i in nextroom[n]: 
      if depth[i] > j:
        nextvisit.append(i)
        sgn[i] = n
        depth[i] = j
  now = [] + nextvisit
  nextvisit = []

if -1 in sgn:
  print('No')
else:
  print('Yes')
  for k in range(1, len(sgn)):
    print(sgn[k]+1)
### BUGGY CODE ###

N = int(input())
 
ans = 1
for val in input().split():
    ans = ans * int(val)
 
if(ans > 10 **18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

N = int(input())

An = [int(_) for _ in input().split()]
An.sort()

ans = 1

for val in An:
    # 0がきたらすぐに抜ける
    if(int(val) == 0):
        print(0)
        sys.exit()
    ans *= val
    # ansが10^18を超えた時点で-1にする
    if(ans > 10 **18):
        print(-1)
        sys.exit()

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

import sys
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
ans = [[-1,-1] for i in range(n)]
ans[ne] = [0,0]
def dfs(x,y,z):
        for i in g[x]:
                if i == y:
                        continue
                if ans[i][1] < z+1:
                        ans[i] = [x+1,z+1]
                        dfs(i,x,z+1)
dfs(ne,-1,0)
for i,j in ans:
        print(i)

### FIXED CODE ###

import sys
import heapq
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
kazu = [0]*n
for i in range(n):
        kazu[i] = len(g2[i])
ans = [0] * n
def dfs(x):
        z = []
        for i in g[x]:
                kazu[i]-=1
                if kazu[i] == 0:
                        z.append(i)
                        ans[i] = x+1
        for i in z:
                dfs(i)
dfs(ne)
for i in ans:
        print(i)
### BUGGY CODE ###

from itertools import combinations

n, k = map(int, input().split())
xlist, ylist, xy = [], [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)
  xy.append((x, y))

xlist.sort()
ylist.sort()
ans = (xlist[-1] - xlist[0]) * (ylist[-1] - ylist[0])
for x1, x2 in combinations(xlist, r=2):
  for y1, y2 in combinations(ylist, r=2):
    tmpk = 0
    for i in range(n):
      if x1 <= xy[i][0] <= x2 and y1 <= xy[i][1] <= y2:
        tmpk += 1

      if tmpk >= k:
        tmp_ans = (x2 - x1) * (y2 - y1)
        if ans > tmp_ans:
          ans = tmp_ans

print(ans)


### FIXED CODE ###

from itertools import combinations

n, k = map(int, input().split())
xlist, ylist, xy = [], [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)
  xy.append((x, y))

xlist.sort()
ylist.sort()
ans = (xlist[-1] - xlist[0]) * (ylist[-1] - ylist[0])
for x1, x2 in combinations(xlist, r=2):
  for y1, y2 in combinations(ylist, r=2):
    tmpk = 0
    for i in range(n):
      if x1 <= xy[i][0] <= x2 and y1 <= xy[i][1] <= y2:
        tmpk += 1

      if tmpk >= k:
        tmp_ans = (x2 - x1) * (y2 - y1)
        if ans > tmp_ans:
          ans = tmp_ans

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

n=int(input()) 
L=list(map(int, input().split())) 
L.sort()
 
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    
    while low <= high:
        if item > list[high]:
          return high+1
          break
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
          return mid
        elif guess > item:
          high = mid -1
          if list[mid-1] < item:
            return mid-1
            break
        elif guess < item:
          low = mid + 1
          if list[mid+1] > item:
            return mid+1
            break
        else:
          print('error')
 
    return 0
 
 
count = 0        
for i in range(n-1):
  a = L[i]
  for k in range(i+1,n-1):
    b = L[k]
    L_temp = L[k+1:]
    binary_search(L_temp, a+b)
    count = count + binary_search(L_temp, a+b)
    
print(count)

### FIXED CODE ###

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

count = 0        
for i in range(n-2):
  a = L[i]
  for k in range(i+1,n-1):
    b = L[k]

    count += bisect.bisect_left(L, a + b) - k -1
print(count)
### BUGGY CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
p=min(a*n,sum(x))
dp=[[[0]*(n+1)for _ in range(p+1)]for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
	for j in range(p+1):
		for k in range(n+1):
			dp[i][j][k]+=dp[i-1][j][k]
			if j-x[i-1]>=0 and k>=1:
				dp[i][j][k]+=dp[i-1][j-x[i-1]][k-1]
ans=0
for i in range(1,n+1):
	if i*a>p:
		break
	ans+=dp[-1][i*a][i]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
p=min(a*n,sum(x))
dp=[[[0]*(n+1)for _ in range(p+1)]for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
	for j in range(p+1):
		for k in range(n+1):
			dp[i][j][k]+=dp[i-1][j][k]
			if j-x[i-1]>=0 and k>=1:
				dp[i][j][k]+=dp[i-1][j-x[i-1]][k-1]
ans=0
for i in range(1,n+1):
	if i*a>p:
		break
	ans+=dp[-1][i*a][i]
print(ans)