Problem:


Score : 400 points

Problem Statement

Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.

He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:

a < b + c

b < c + a

c < a + b

How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

Constraints

All values in input are integers.

3 \leq N \leq 2 \times 10^3

1 \leq L_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N
L_1 L_2 ... L_N

Constraints

Print the number of different triangles that can be formed.

Sample Input 1

4
3 4 2 1

Sample Output 1

1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23



Sample input:
4
3 4 2 1


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = sorted(list(map(int, input().split())))
ans = []
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if (d[i] < (d[j] + d[k])) & (d[j] < (d[i] + d[k])) & (d[k] < (d[j] + d[i])):
                ans.append(sorted([d[i], d[j], d[k]]))
            else:
                break
seen = []
ans = [x for x in ans if x not in seen and not seen.append(x)]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = list(map(int, input().split()))
ans = []
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if (d[i] < (d[j] + d[k])) & (d[j] < (d[i] + d[k])) & (d[k] < (d[j] + d[i])):
                ans.append(sorted([d[i], d[j], d[k]]))

seen = []
ans = [x for x in ans if x not in seen and not seen.append(x)]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
ret = 0
for i in range(0, N-2):
    for j in range(i+1, N-1):
        ret += len([k for k in L[j+1:] if L[i]+L[j]>k])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0

for i, a in enumerate(l):
    candidates = l[i+1:]
    for j, b in enumerate(candidates):
        brk = False
        #c_candidates = [c for c in candidates[j+1:] if c < a + b]
        #ans += len(c_candidates)
        for c in candidates[j+1:]:
            if c < a + b: ans += 1
            else: break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0

for i, a in enumerate(l):
    candidates = l[i+1:]
    for j, b in enumerate(candidates):
        c_candidates = [c for c in candidates[:j] + candidates[j+1:] if a <= b < c < a + b]
        ans += len(c_candidates)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i, a in enumerate(l):
    candidates = [b for b in l[:i] + l[i+1:] if a <= b]
    for j, b in enumerate(candidates):
        c_candidates = [c for c in candidates[:j] + candidates[j+1:] if a <= b < c < a + b]
        ans += len(c_candidates)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from functools import lru_cache

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0


@lru_cache()
def bisect_left_cache(x):
    return bisect_left(lll, x)


for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left_cache(li + lll[j])
        ans += k - j - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		rem = lengths[j + 1:]
		res += bisect_left(lengths, l1 + l2, j + 1) - j - 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		rem = lengths[j + 1:]
		res += bisect_left(rem, l1 + l2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from bisect import bisect_left

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

res = 0
sorted_lengths = sorted(lengths)
for i in range(n):
	l1 = sorted_lengths[i]
	for j in range(i + 1, n - 1):
		l2 = sorted_lengths[j]
		rem = sorted_lengths[j + 1:]
		res += bisect_left(rem, l1 + l2) - bisect_left(rem, l2 - l1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

res = 0
sorted_lengths = sorted(lengths)
for i in reversed(range(n)):
	l1 = sorted_lengths[i]
	for j in reversed(range(1, i)):
		l2 = sorted_lengths[j]
		rem = sorted_lengths[:j]
		res += bisect(rem, l1 + l2) - bisect(rem, l1 - l2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

res = 0
sorted_lengths = sorted(lengths)
for i in reversed(range(n)):
	l1 = sorted_lengths[i]
	for j in reversed(range(i + 1, n - 1)):
		l2 = sorted_lengths[j]
		rem = sorted_lengths[j + 1:]
		res += bisect_left(rem, l1 + l2) - bisect_left(rem, l1 - l2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
#    print("target ==",target,arr[start:last+1])
    if last - start == 1:
        if(arr[last] < target):
            return last
        elif(arr[start] < target):
            return start
        else:
            return start -1
    if last < start:
        return start -1
    if start == last:
        if arr[start] < target:
            return start
        else:
            return start -1
    mid = (last - start)//2 + start
    if arr[mid] < target:
        return search(arr,target,mid + 1,last)
    else:
        return search(arr,target,start,mid)
    return start -1


for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
 #       print("#",a,b)
        f1 = search(l,target,j+1,n-1)
  #      print("arr[f1]",l[f1])
        cnt+= f1 - j 
  #      print("cnt: ",cnt)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
 #   print("target ==",target,arr[start:last+1])
    if last - start == 1:
        if(arr[last] < target):
            return last
        elif(arr[start] < target):
            return start
        else:
            return -1
    if last < start:
        return -1
    if start == last:
        if arr[start] < target:
            return start
        else:
            return -1
    mid = (last - start)//2 + start
    if arr[mid] < target:
        return search(arr,target,mid + 1,last)
    else:
        return search(arr,target,start,mid)
    return -1


for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = search(l,target,j+1,n-1)
        if f1 == -1: 
            continue
   #     print("arr[f1]",l[f1])
        cnt+= f1 - j 
   #     print("cnt: ",cnt)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lengths = map(int, input().split())

res = 0
sorted_lengths = sorted(lengths)[::-1]
for i in range(n):
	l1 = sorted_lengths[i]
	for j in range(i+1, n):
		l2 = sorted_lengths[j]
		res += sum([l1 - l2 < _ < l1 + l2 for _ in sorted_lengths[j + 1:]])
		
print(res)

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = sorted(list(map(int, input().rstrip('\n').split())))
    cnt = 0
    for i, iv in enumerate(l[:n-2]):
        for j, jv in enumerate(l[i+1:n-1]):
            t = iv + jv
            for k, kv in enumerate(l[i+j+2:n]):
                if t > kv:
                    cnt += 1
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = collections.deque(sorted(list(map(int, input().rstrip('\n').split()))))
    cnt = 0
    for i in range(n-2):
        p = l.popleft()
        for j in range(n-i-1):
            t = p + l[j]
            for k in range(j+1, n-i-1):
                if t > l[k]:
                    cnt += 1
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = sorted(tuple(map(int, input().rstrip('\n').split())))
    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            t = l[i] + l[j]
            for k in range(j+1, n):
                if t > l[k]:
                    cnt += 1
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            t = l[i] + l[j]
            for k in range(j+1, n):
                if t > l[k]:
                    cnt += 1
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j)
        ans += ri - j - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j + 1)
        ans += ri - j - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for c in range(2,N):
    cc=L[c]
    for b in range(1,c):
        bb=L[b]
        if cc>=bb+L[b-1]: continue
        l=-1
        u=b-1
        while u-l>1:
            a=(l+u+1)//2
            aa=L[a]
            if aa+bb>cc: u=a
            else: l=a
        ans+=(b-u)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort(reverse=True)
    Ans = 0
    for i in range(N):
        for j in range(i+1,N):
            threshold = L[i] - L[j]
            for k in range(j+1,N):
                if L[k] > threshold:
                    Ans += 1
                else:
                    break
    print(Ans)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(len(l) - 2):
    a = l[i]
    for j in range(i + 1, len(l) - 1):
        b = l[j]
        r = a + b
        for k in range(j + 1, len(l)):
            c = l[k]
            if c < r:
                count += 1
            else:
                break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(len(l) - 2):
    a = l[i]
    for j in range(i + 1, len(l) - 1):
        b = l[j]
        r = a + b
        for k in range(j + 1, len(l)):
            c = l[k]
            if c < r:
                count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
L =list(map(int,input().split()))
S = []
ans = 0
for i, j, k in itertools.combinations(L,3):
  S.append([i, j, k])
for a, b, c in S:
  if a < b + c and b < c + a and c < a + b:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
L_lst=sorted(list(map(int,input().split())))
i=n-2
j=n-1
cnt=0
while j>1:
    for x in range(i-1,-1,-1):
        if x==0:#0だとout of range
            if abs(L_lst[i]-L_lst[j])<L_lst[x]<L_lst[i]+L_lst[j]:
                cnt+=1
        else:
            if L_lst[x]!=L_lst[x-1]:
                if abs(L_lst[i]-L_lst[j])<L_lst[x]<=L_lst[i]+L_lst[j]:
                    cnt+=1
    i-=1
    if i==0:
        j-=1
        i=j-1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        r = L[i] + L[j]

        ri = bisect.bisect_left(L, r, lo=j)
        for k in range(j+1, ri):
            if k == i or k == j: continue
            ans.add((L[i], L[j], L[k]))

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, L: "List[int]"):
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            from bisect import bisect_left, bisect_right
            k = bisect_left(L, L[i]+L[j])
            ans += (k-j-1)

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def generator():
    for l in input().split():
        yield int(l)

def sort(L, maxl, minl):
    counts = [0 for _ in range(maxl - minl + 1)]
    for l in L:
        counts[l - minl] += 1
    return [e for e, c in enumerate(counts, start=minl) for _ in range(c)]

def main():
    N = int(input())

    L = []
    maxl = 1
    minl = 10 ** 3
    for l in generator():
        L.append(l)
        if l > maxl:
            maxl = l
        if l < minl:
            minl = l

    count = 0
    sortL = sort(L, maxl, minl)
    for i in range(N):
        c = sortL[N - i - 1]
        for j in range(N - i):
            b = sortL[N - i - j - 2] 
            for k in range(N - i - j - 2):
                a = sortL[k]
                if a <= c - b:
                    continue
                count += 1

    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, L: "List[int]"):
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            from bisect import bisect_left, bisect_right
            k = bisect_left(L, L[i]+L[j])
            ans += (k-(j+1))

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
 
result = 0
 
for aIndex,a in enumerate(L[:N-2]):
    for bIndex,b in enumerate(L[aIndex+1:N-1]):
        for c in L[aIndex+bIndex+2:]:
            if a<b+c and b<a+c and c<a+b:
                result+=1
            else:
                break
 
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, L: "List[int]"):
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            from bisect import bisect_left, bisect_right
            k = bisect_left(L, L[i]+L[j])
            ans += max(0, k-(j+1))

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = [int(x) for x in input().split()]
count = 0
for i in range(N):
    for j in range(i+1,N-1):
            for k in range(j+1,N):
                if (data[i] + data[j] > data[k]) and (data[i] + data[k] > data[j]) and (data[j] + data[k] > data[i]):
                    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    p=list(itertools.combinations(l,3))
    c=[1 for i in p if 2*max(i)<sum(i)]
    print(sum(c))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    l.sort()
    cnt=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                if l[k]<l[i]+l[j]:
                    cnt+=1
                else:
                    break
    print(cnt)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    l.sort()
    cnt=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                if l[k]<l[i]+l[j]:
                    cnt+=1
    print(cnt)
resolve()

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = list(map(int, input().split()))
b.sort()
r = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        if b[j + 1] >= b[i] + b[j]:
            continue
        for k in range(j+1, a):
            if b[k] >= b[i] + b[j]:
                break
            r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = list(map(int, input().split()))
b.sort()
r = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        for k in range(j+1, a):
            if b[k] >= b[i] + b[j]:
                break
            r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, l):
    l = sorted(l)
    ret = [1 for i in range(0, n) for j in range(i+1, n) for k in range(j+1, n) if l[k] < l[i] + l[j]]
    return len(ret)

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

ans = solve(n, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
a = int(input())
b = list(map(int, input().split()))
r = 0
for i, j, k in combinations(b,3):
    if i < j + k and j < i + k and k < i + j:
        r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=sorted(list(map(int,input().split())))

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

  print(cnt)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(n, l):
    l = sorted(l)
    ret = [1 for i in range(0, n) for j in range(i+1, n) for k in range(j+1, n) if l[i] < l[j] + l[k] and l[j] < l[i] + l[k] and l[k] < l[i] + l[j]]
    return len(ret)

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

ans = solve(n, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    A, B = LI()
    ans = A-2*B
    if ans > 0:
        print(ans)
    else:
        print(0)
    return

# B


def B():
    N = II()
    d = LI()
    ans = 0
    for i in range(N):
        for x in range(i+1, N):
            ans += d[i]*d[x]
    print(ans)

    return

# C


def C():
    N = II()
    S = input()
    c = 0
    count = 0
    for i in S:
        if i != c:
            count += 1
        c = i
    print(count-1)

    return

# D


def D():
    N = II()
    L = LI()
    L.sort()

    count = 0
    for i in range(N-2):

        for j in range(i+1, N-1):

            p = L[i]+L[j]

            count += sum(x < p for x in L)-j-1

    print(count)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit |= 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


# Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    A, B = LI()
    ans = A-2*B
    if ans > 0:
        print(ans)
    else:
        print(0)
    return

# B


def B():
    N = II()
    d = LI()
    ans = 0
    for i in range(N):
        for x in range(i+1, N):
            ans += d[i]*d[x]
    print(ans)

    return

# C


def C():
    N = II()
    S = input()
    c = 0
    count = 0
    for i in S:
        if i != c:
            count += 1
        c = i
    print(count-1)

    return

# D


def D():
    N = II()
    L = LI()
    L.sort()

    L2 = deque(L)
    count = 0
    for i in range(N-2):
        L2.popleft()
        L3 = list(L2)
        L3 = deque(L3)

        for j in range(i+1, N-1):
            L3.popleft()
            if L3 == deque([]):
                break
            p = L[i]+L[j]

            if L3[0] >= p:
                continue
            #Lk = filter(lambda x: x % 2 == 1, L2)
            
            count += sum(x < p for x in L3)

            
        if len(L2) == 2:
            break
    print(count)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit |= 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


# Solve
if __name__ == '__main__':
    D()