AtCoder Beginner Contest 143 - Triangles

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-----
4
3 4 2 1

-----Sample Output-----
1

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

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
c = 0
for i in range(len(l) - 2):
	for j in range(i + 1, len(l) - 1):
		c += bisect.bisect(l[j + 1:], l[i] + l[j] - 1)
print(c)


import bisect
n = int(input())
l = sorted(map(int, input().split()))
t = 0
for i in range(n):
	for j in range(i + 1, n):
		t += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(t)


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		a = bisect.bisect_left(L, L[i] + L[j])
		ans += a - j - 1
print(ans)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for b in range(n - 2):
	for c in range(b + 1, n - 1):
		count += max(0, bisect.bisect_left(l, l[b] + l[c]) - c - 1)
print(count)


from bisect import *
(n, *l) = map(int, open(0).read().split())
l.sort()
ans = 0
for i in range(1, n):
	for j in range(i + 1, n):
		ans += max(i - bisect_right(l, l[j] - l[i]), 0)
print(ans)


n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
c = 0
import bisect
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		c += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(c)


from bisect import *
n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n):
	a = l[i]
	for j in range(i + 1, n):
		b = l[j]
		k = bisect_left(l, a + b)
		cnt += k - (j + 1)
print(cnt)


import bisect as bs
N = int(input())
y = list(map(int, input().split()))
y.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		tmp = y[i] + y[j]
		ans += bs.bisect_left(y[j + 1:], tmp)
print(ans)


n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
import bisect
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		ab = l[i] + l[j]
		idx = bisect.bisect_left(l, ab)
		ans += max(0, idx - j - 1)
print(ans)


import bisect
n = int(input())
li = list(map(int, input().split()))
ans = 0
li.sort()
for k in range(0, n - 2):
	for i in range(k + 1, n - 1):
		ans += bisect.bisect_left(li, li[k] + li[i]) - i - 1
print(ans)


from bisect import bisect
n = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		cnt += bisect(L, L[i] + L[j] - 1) - j - 1
print(cnt)


from bisect import bisect_left, bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
icnt = 0
for a in range(n - 2):
	for b in range(a + 1, n - 1):
		nc = bisect(l, l[a] + l[b] - 1)
		if nc > b + 1:
			icnt += nc - (b + 1)
print(icnt)


import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		k = bisect.bisect_left(L, L[i] + L[j])
		ans += k - j - 1
print(ans)


import bisect
n = int(input())
L = [int(i) for i in input().split()]
L.sort()
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		ans += bisect.bisect_left(L, L[i] + L[j]) - j - 1
print(ans)


import bisect
n = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		idx = bisect.bisect_left(L, L[j] + L[i])
		ans += max(0, idx - j - 1)
print(ans)


import bisect

def LI():
	return list(map(int, input().split()))
N = int(input())
L = LI()
L.sort()
ans = 0
for i in range(N - 1, 1, -1):
	for j in range(i - 1, 0, -1):
		ind = bisect.bisect_right(L, L[i] - L[j])
		if ind < j:
			ans += j - ind
print(ans)


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N - 2):
	for b in range(a + 1, N - 1):
		c = bisect.bisect_left(L, L[a] + L[b])
		ans += c - (b + 1)
print(ans)


from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		tmp = bisect_left(L, L[i] + L[j])
		cnt += tmp - j - 1
print(cnt)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		maxk = bisect.bisect_left(l, l[i] + l[j], j + 1, n) - 1
		count += maxk - j
print(count)


import bisect
N = int(input())
L = list(map(int, input().split()))
ll = len(L)
L.sort()
s = 0
for i in range(ll):
	for j in range(i + 1, ll):
		s += bisect.bisect_right(L, L[i] + L[j] - 1) - j - 1
print(s)


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(1, n - 1):
	for j in range(0, i):
		k = bisect_left(a, a[i] + a[j]) - i - 1
		ans = ans + k
print(ans)


from bisect import bisect_left
N = int(input())
L_list = list(map(int, input().split()))
L_list.sort()
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		(a, b) = (L_list[i], L_list[j])
		r = bisect_left(L_list, a + b)
		ans += max(0, r - j - 1)
print(ans)


import bisect
from copy import deepcopy
N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(N):
	for j in range(i + 1, N - 1):
		b = L[j] + L[i]
		x = bisect.bisect_left(L, b) - j - 1
		if x > 0:
			ans += x
print(ans)


from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N - 2):
	a = L[i]
	for j in range(i + 1, N - 1):
		b = L[j]
		ans += bisect_left(L, a + b) - (j + 1)
print(ans)


import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n):
	for j in range(i + 1, n):
		b = a[i] + a[j]
		x = bisect.bisect_left(a, b)
		cnt += max(0, x - j - 1)
print(cnt)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(0, n - 2):
	for j in range(i + 1, n - 1):
		p = bisect.bisect_right(l, l[i] + l[j] - 1)
		cnt += p - j - 1
print(cnt)


from bisect import *
N = int(input())
(*L,) = sorted(map(int, input().split()))
r = 0
for a in range(N):
	for b in range(a + 1, N):
		x = L[a]
		y = L[b]
		r += max(0, bisect_left(L, x + y) - (b + 1))
print(r)


import bisect
n = int(input())
l = sorted(map(int, input().split()))
t = 0
for i in range(n):
	for j in range(i + 1, n):
		a = j + 1
		b = bisect.bisect_left(l, l[i] + l[j])
		t += b - a if b > a else 0
print(t)


n = int(input())
l = list(map(int, input().split()))
l.sort()
k = []
ans = 0
import bisect
for i in range(1, n):
	for j in range(i):
		p = l[j] + l[i]
		q = bisect.bisect_left(l, p)
		ans += q - i - 1
print(ans)


n = int(input())
li = list(map(int, input().split()))
li.sort()
num = 0
import bisect
for i in range(n):
	for j in range(i + 1, n):
		num += bisect.bisect_left(li, li[i] + li[j]) - (j + 1)
print(num)


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N):
	for j in range(i + 1, N):
		cnt += bisect.bisect_left(L, L[i] + L[j]) - (j + 1)
print(cnt)


from bisect import bisect_right as br
n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for x in range(n):
	for y in range(x + 1, n):
		i = l[x]
		j = l[y]
		cnt += br(l, i + j - 1) - 1 - y
print(cnt)


import bisect as bs
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(len(L) - 1):
	for j in range(i + 1, len(L)):
		ans += bs.bisect_left(L, L[i] + L[j]) - j - 1
print(ans)


import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	res = 0
	for i in range(n):
		k = i
		for j in range(i + 1, n):
			while k < n and l[k] < l[i] + l[j]:
				k += 1
			res += k - (j + 1)
	print(res)
	return 0

def __starting_point():
	solve()
__starting_point()


from bisect import *
(n, *l) = map(int, open(0).read().split())
l.sort()
print(sum((~j + bisect_left(l, l[i] + l[j], j + 1) for i in range(n) for j in range(i + 1, n))))


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 1):
	for g in range(i + 1, N - 1):
		bigger = bisect.bisect_left(L, L[i] + L[g])
		ans += bigger - g - 1
print(ans)


from bisect import bisect_left
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		a = bisect_left(l, l[i] + l[j])
		ans += a - 1 - j
print(ans)


import bisect
from itertools import combinations

def main():
	N = int(input())
	L = sorted(list(map(int, input().split())))
	ans = 0
	for l in combinations(L, 2):
		a = l[0]
		b = l[1]
		x = bisect.bisect_left(L, a + b)
		y = bisect.bisect(L, b - a)
		if b - a < a:
			ans += x - y - 2
		else:
			ans += x - y - 1
	print(ans // 3)

def __starting_point():
	main()
__starting_point()


from bisect import *
(_, l) = open(0)
l = sorted(map(int, l.split()))
print(sum((j - bisect(l, a - l[j], 0, j) for (i, a) in enumerate(l) for j in range(i))))


import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
count = 0
for a in range(N - 2):
	for b in range(a + 1, N - 1):
		count += bisect.bisect_left(L, L[a] + L[b]) - b - 1
print(count)


from bisect import *
n = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		k = bisect_right(L, L[i] + L[j] - 1)
		ans += k - j - 1
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		res = l[i] + l[j]
		mid = bisect.bisect_left(l, res)
		ans += mid - j - 1
print(ans)


from bisect import bisect_left
(N, *L) = list(map(int, open(0).read().split()))
L.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		a = L[i]
		b = L[j]
		ans += bisect_left(L, a + b, lo=j + 1) - (j + 1)
print(ans)


n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
import bisect
for i in range(n):
	a = l[i]
	for j in range(i + 1, n):
		b = l[j]
		ans += bisect.bisect_left(l, a + b) - j - 1
print(ans)


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

def check(a, b, c):
	return abs(a - b) < c < a + b
ans = 0
for i in range(n):
	short = l_ls[i]
	num = 0
	r = i + 1
	for l in range(i + 1, n):
		while r + 1 < n and check(short, l_ls[l], l_ls[r + 1]):
			r += 1
		num += r - l
		if r == l:
			r += 1
	ans += num
print(ans)


n = int(input())
import bisect
a = sorted(list(map(int, input().split(' '))))
ans = 0
for i in range(1, n - 1):
	b = a[:i]
	c = a[i + 1:]
	for j in b:
		ans += bisect.bisect(c, a[i] + j - 0.1)
print(ans)


from bisect import bisect_left
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0
for small in range(n - 2):
	for mid in range(small + 1, n - 1):
		div = bisect_left(arr, arr[small] + arr[mid], 0, n)
		if div > mid + 1:
			ans += div - mid - 1
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		(l1, l2) = (l[i], l[j])
		ans += max(bisect.bisect_left(l, l1 + l2) - j - 1, 0)
print(ans)


from bisect import bisect_left
n = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for a in range(n - 2):
	for b in range(a + 1, n - 1):
		cnt += bisect_left(L, L[a] + L[b]) - (b + 1)
print(cnt)


import itertools
import bisect
n = int(input())
bo = list(map(int, input().split()))
cnt = 0
bo.sort()
for a in range(n - 1):
	for b in range(a + 1, n):
		cnt += bisect.bisect_left(bo, bo[a] + bo[b]) - (b + 1)
print(cnt)


from bisect import *
n = int(input())
l = sorted(list(map(int, input().split())))
res = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		(a, b) = (l[i], l[j])
		c_cnt = bisect_left(l, a + b) - j - 1
		res += c_cnt
print(res)


import bisect
N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort()
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		count += bisect.bisect(L, L[i] + L[j] - 1) - j - 1
print(count)


from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
c = sum((bisect_left(l, l[i] + l[j]) - j - 1 for i in range(n - 2) for j in range(i + 1, n - 1)))
print(c)


from bisect import *
N = int(input())
(*L,) = sorted(map(int, input().split()))
r = 0
for a in range(N):
	r += sum((bisect_left(L, L[a] + L[b]) - (b + 1) for b in range(a + 1, N)))
print(r)


from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		c = L[i] + L[j]
		idx = bisect_left(L, c)
		ans += max(0, idx - (j + 1))
print(ans)


import bisect
n = int(input())
l = sorted(map(int, input().split()))
ans = 0
for a in range(n):
	for b in range(a):
		A = l[a]
		B = l[b]
		c = bisect.bisect_left(l, A + B)
		ans += c - a - 1
print(ans)


N = int(input())
(*L,) = map(int, input().split())
L.sort()
from bisect import *
i = 0
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		ans += bisect_left(L, L[i] + L[j]) - j - 1
print(ans)


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(1, N - 1):
	for j in range(i + 1, N):
		ans += i - bisect.bisect_right(L[:i], L[j] - L[i])
print(ans)


n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for (i, a) in enumerate(L[2:]):
	k = i + 1
	for (j, b) in enumerate(L[:i + 2]):
		while j < k and a - b < L[k]:
			k -= 1
		ans += i - max(k, j) + 1
print(ans)


N = int(input())
A = [int(i) for i in input().split()]
A.sort()
L = [0] * 2001
ans = 0
for i in range(N - 2):
	for j in range(i + 1):
		L[A[i + 1] + A[j]] += 1
	ans += sum(L[A[i + 2] + 1:])
print(ans)


import bisect

def binary_search(items, a, b, i, j):

	def c_is_x(c):
		is1 = c > max(a - b, b - a)
		is2 = c < a + b
		if is1 and is2:
			return 0
		elif is1:
			return 1
		else:
			return 2
	low = j + 1
	high = len(items) - 1
	while low <= high:
		mid = (low + high) // 2
		ans = items[mid]
		c_type = c_is_x(ans)
		if c_type == 0 and mid != i and (mid != j):
			return mid
		elif c_type == 1:
			low = mid + 1
		else:
			high = mid - 1
	return None
N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(N):
	for j in range(i + 1, N):
		a = L[i]
		b = L[j]
		k = bisect.bisect_left(L, a + b, lo=j) - 1
		if k < N:
			c = L[k]
			count += max(k - j, 0)
print(count)


import bisect
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):
		sum = l[i] + l[j]
		index = bisect.bisect_left(l, sum)
		cnt += index - j - 1
print(cnt)


from collections import deque
from bisect import bisect_left
n = int(input())
l = sorted(map(int, input().split()))
ld = deque(l)
cnt = 0
for a in range(n - 2):
	l_a = ld.popleft()
	for b in range(a + 1, n - 1):
		cnt += bisect_left(l, l_a + l[b]) - b - 1
print(cnt)


import bisect
n = int(input())
L = sorted(map(int, input().split()))
m = L[-1]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		k = L[i] + L[j]
		ans += bisect.bisect_left(L, k) - j - 1
print(ans)


from bisect import bisect_right
n = int(input())
a = sorted(map(int, input().split()))
print(sum((j - bisect_right(a, a[i] - a[j], 0, j) for i in range(2, n) for j in range(1, i))))


n = int(input())
L = sorted(map(int, input().split()))
ans = 0
import bisect
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		a = L[n - 1 - i]
		b = L[n - 1 - j]
		c = a - b + 1
		if c <= b:
			ans += n - 1 - j - bisect.bisect_left(L, c)
print(ans)


import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		num = L[i] + L[j]
		ind = bisect.bisect_right(L, num - 1)
		if ind > j - 1:
			ans += ind - j - 1
print(ans)


import bisect
N = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(N):
	for j in range(i + 1, N):
		count += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(count)


from bisect import *
N = int(input())
L = sorted(map(int, input().split()))
a = 0
for i in range(N):
	for j in range(i + 1, N):
		a += bisect_left(L, L[i] + L[j]) - (j + 1)
print(a)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		t = l[i] + l[j]
		idx = bisect.bisect_left(l, t)
		ans += max(0, idx - (j + 1))
print(ans)


import bisect
N = int(input())
List = list(map(int, input().split()))
List.sort()
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		ans += bisect.bisect_left(List, List[i] + List[j]) - (j + 1)
print(ans)


import bisect

def main():
	N = int(input())
	L = list(sorted(map(int, input().split())))
	res = 0
	for i in range(N - 2):
		x = L[i]
		for j in range(i + 1, N - 1):
			y = L[j]
			res += bisect.bisect_left(L, x + y) - j - 1
	print(res)
	return
main()


from bisect import bisect_right
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)


N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for b in range(N):
	r = b + 1
	for a in range(b):
		while r < N and L[r] < L[a] + L[b]:
			r += 1
		ans += r - (b + 1)
print(ans)


from bisect import *
(N, *L) = map(int, open(0).read().split())
L.sort()
print(sum((bisect_left(L, L[i] + L[j], j + 1) - j - 1 for i in range(N) for j in range(i + 1, N))))


N = int(input())
L = sorted(list(map(int, input().split())))
r = 0
from bisect import bisect
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		r += bisect(L, L[i] + L[j] - 1) - j - 1
print(r)


def findnumberofTriangles(arr):
	n = len(arr)
	arr.sort()
	count = 0
	for i in range(0, n - 2):
		k = i + 2
		for j in range(i + 1, n):
			while k < n and arr[i] + arr[j] > arr[k]:
				k += 1
			if k > j:
				count += k - j - 1
	return count
n = int(input())
arr = [int(x) for x in input().split()]
print(findnumberofTriangles(arr))


import bisect
N = int(input())
L = list(map(int, input().split()))
l = sorted(L)
result = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		result += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(result)


import bisect

def main():
	n = int(input())
	l = sorted(list((int(i) for i in input().split())))
	cnt = 0
	for i in range(n - 2):
		a = l[i]
		for j in range(i + 1, n - 1):
			b = l[j]
			cnt += bisect.bisect_left(l, a + b) - (j + 1)
	print(cnt)

def __starting_point():
	main()
__starting_point()


N = int(input())
L = list(map(int, input().split()))
ans = 0
c = [0] * 1001
for i in L:
	c[i] += 1
for i in range(1000):
	c[i + 1] = c[i] + c[i + 1]
for i in range(N - 1):
	for j in range(i + 1, N):
		(l, r) = (abs(L[i] - L[j]), min(L[i] + L[j] - 1, 1000))
		ans += c[r] - c[l]
		if l < L[i] and L[i] <= r:
			ans -= 1
		if l < L[j] and L[j] <= r:
			ans -= 1
print(ans // 3)


n = int(input())
l = list(map(int, input().split()))
l.sort()
from bisect import bisect_left as bl
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		ans += bl(l, l[j] + l[i]) - j - 1
print(ans)


import bisect

def resolve():
	n = int(input())
	l = sorted(list(map(int, input().split())))
	ans = 0
	for a in range(n):
		for b in range(a + 1, n):
			c = bisect.bisect_left(l, l[a] + l[b])
			if c > b:
				ans += c - b - 1
			else:
				pass
	print(ans)
resolve()


n = int(input())
A = list(map(int, input().split()))
ans = 0
A.sort()
from bisect import bisect_left as bi
for i in range(n):
	for j in range(i):
		index = bi(A, A[i] + A[j])
		ans += index - 1 - i
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		idx = bisect.bisect_right(l, l[i] + l[j] - 1, j + 1)
		ans += idx - (j + 1)
print(ans)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
s = 0
for i in range(0, n - 2):
	a = l[i]
	for j in range(i + 1, n - 1):
		b = l[j]
		s += bisect.bisect_left(l, a + b, j + 1) - j - 1
print(s)


import bisect
N = int(input())
L = sorted(map(int, input().split()))
count = 0
for a in range(N - 2):
	for b in range(a + 1, N - 1):
		count += bisect.bisect_left(L, L[a] + L[b]) - (b + 1)
print(count)


import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for b in range(1, n - 1):
	for c in range(b + 1, n):
		ans += b - bisect.bisect_right(L[:b], L[c] - L[b])
print(ans)


import bisect

def main():
	n = int(input())
	l_lst = list(map(int, input().split()))
	l_lst.sort()
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			a = l_lst[i]
			b = l_lst[j]
			tmp = bisect.bisect_left(l_lst, a + b)
			tmp -= j + 1
			tmp = max(0, tmp)
			count += tmp
	print(count)

def __starting_point():
	main()
__starting_point()


import bisect
n = int(input())
l = list(map(int, input().split()))
cnt = 0
l.sort()
for i in range(n):
	for j in range(i + 1, n):
		wa = l[i] + l[j]
		r = bisect.bisect_left(l, wa)
		cnt += r - j - 1
print(cnt)


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 a in range(N - 2):
		for b in range(a + 1, N - 1):
			x = bisect_left(L, L[a] + L[b])
			ans += x - 1 - b
	print(ans)

def __starting_point():
	main()
__starting_point()


import bisect
N = int(input())
L = [int(i) for i in input().split(' ')]
L.sort()
sum = 0
for (i, k) in enumerate(L):
	for j in range(i + 1, N):
		sum += bisect.bisect_left(L, L[j] + k) - j - 1
print(sum)


n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
	k = i
	for j in range(i + 1, n):
		while k < n and l[k] < l[i] + l[j]:
			k += 1
		ans += k - (j + 1)
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ct = 0
for i in range(n):
	for j in range(i + 1, n):
		ct += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ct)


import bisect
(n, *l) = map(int, open(0).read().split())
l.sort()
a = 0
for i in range(n):
	for j in range(i + 1, n):
		k = l[i] + l[j]
		a += max(0, bisect.bisect_left(l, k) - j - 1)
print(a)


n = int(input())
a = sorted([int(x) for x in input().split()])
ret = 0
for i in range(n - 1, 0, -1):
	l = 0
	r = i - 1
	while l < r:
		if a[l] + a[r] > a[i]:
			ret += r - l
			r -= 1
		else:
			l += 1
print(ret)


import bisect
n = int(input())
d = list(map(int, input().split()))
d.sort()
m = 0
for a in range(n - 2):
	for b in range(a + 1, n - 1):
		m += bisect.bisect_left(d, d[a] + d[b]) - 1 - b
print(m)


n = int(input())
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_right
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		ans += bisect_right(a, a[j] + a[i] - 0.5) - j - 1
print(ans)


from bisect import bisect_left

def can_make_tri(a, b, c):
	return a < b + c and b < c + a and (c < a + b)
(N, *L) = list(map(int, open(0).read().split()))
L.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		pos = bisect_left(L, L[i] + L[j], lo=j + 1)
		ans += pos - (j + 1)
print(ans)


import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for n in range(1, N):
	b = L[n]
	for k in range(n):
		a = L[k]
		index = bisect.bisect_left(L, a + b)
		ans += index - n - 1
print(ans)


from bisect import *
(n, *l) = map(int, open(0).read().split())
l.sort()
c = 0
for i in range(n):
	for j in range(i + 1, n):
		d = bisect_left(l, l[i] + l[j])
		c += max(0, d - j - 1)
print(c)


import bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n - 1, 1, -1):
	for j in range(i - 1, 0, -1):
		t = bisect.bisect_right(a, a[i] - a[j])
		if j - t > 0:
			ans += j - t
print(ans)


import sys, bisect
N = int(input())
L = list(map(int, sys.stdin.readline().rsplit()))
L.sort()
res = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		(a, b) = (L[i], L[j])
		c_l = bisect.bisect_left(L, a + b)
		if c_l <= j:
			continue
		res += c_l - (j + 1)
print(res)


import bisect
counter = 0
N = int(input())
L = sorted(list(map(int, input().split())))
for a in range(N - 2):
	for b in range(a + 1, N - 1):
		k = bisect.bisect_left(L, L[a] + L[b])
		counter += k - b - 1
print(counter)


import bisect
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
out = 0
for i in range(n):
	for j in range(1 + i, n):
		out += bisect.bisect_left(lis, lis[i] + lis[j]) - j - 1
print(out)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for i in range(2, n):
	for j in range(1, i):
		count += max(j - bisect.bisect_right(l, l[i] - l[j]), 0)
print(count)


import bisect
N = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(1, N - 1):
	for j in range(i + 1, N):
		m = bisect.bisect_right(l, l[j] - l[i])
		if i > m:
			ans += i - m
print(ans)


N = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
max = l[N - 1]
tc = N
st = [j + 1 for j in range(N - 1)]
for i in range(N - 2):
	if l[i] + l[i + 1] > max:
		k = N - i - 1
		ans += (k - 1) * k * (k + 1) // 6
		break
	for j in range(i + 1, N - 1):
		if j == tc:
			ans += tp
			break
		s = l[i] + l[j]
		if s <= l[j + 1]:
			continue
		if s > max:
			tc = j
			tp = (N - j - 1) * (N - j) // 2
			ans += tp
			break
		start = st[j]
		if s <= l[start]:
			ans += start - j - 1
			continue
		end = N
		while start != end:
			center = (start + end) // 2
			if s <= l[center]:
				end = center
			else:
				start = center + 1
		st[j] = end
		ans += end - j - 1
print(ans)


import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 1, 1, -1):
	for j in range(i - 1, 0, -1):
		t = bisect.bisect(L, L[i] - L[j])
		if j - t > 0:
			ans += j - t
print(ans)


N = int(input())
L = [int(x) for x in input().split()]
from bisect import bisect_left
L.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		t = L[i] + L[j]
		p = bisect_left(L, t)
		ans += max(0, p - j - 1)
print(ans)


import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		idx = bisect.bisect(L, L[i] + L[j] - 1)
		ans += idx - j - 1
print(ans)


import bisect
n = int(input())
an = [int(i) for i in input().split()]
an.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		k = an[i] + an[j] - 1
		ans += bisect.bisect_right(an, k) - j - 1
print(ans)


import bisect
a = int(input())
b = list(map(int, input().split()))
b.sort()
ans = 0
for i in range(a):
	for j in range(i + 1, a):
		k = bisect.bisect_right(b, b[i] + b[j] - 1)
		ans += k - j - 1
print(ans)


def main():
	N = int(input())
	L = [int(l) for l in input().split(' ')]
	L.sort()
	m = len(L)
	cnt = 0
	for i in range(m):
		k = m - 1
		for j in range(i + 1, m):
			while m + i - j < k:
				if L[m + i - j] + L[i] <= L[k]:
					k -= 1
				else:
					cnt += k - m - i + j
					break
	print(cnt)
main()


N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
import bisect
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		ind = bisect.bisect_left(L, L[i] + L[j])
		num = ind - (j + 1)
		ans += max(num, 0)
print(ans)


N = int(input())
(*L,) = map(int, input().split())
L.sort()
from bisect import *
i = 0
ans = 0
while i < N:
	j = i + 1
	while j < N:
		ans += bisect_left(L[j:], L[i] + L[j]) - 1
		j += 1
	i += 1
print(ans)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		x = bisect.bisect_left(l, l[i] + l[j])
		cnt += x - j - 1
print(cnt)


import sys

def solve(N: int, L: 'List[int]'):
	from itertools import combinations
	from bisect import bisect_left as bl
	L = sorted(L)
	ans = 0
	for (ai, a) in enumerate(L):
		for (bi, b) in enumerate(L[ai + 1:-1], ai + 1):
			ci = bl(L, a + b)
			ans += ci - bi - 1
	return ans

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	L = [int(next(tokens)) for _ in range(N)]
	print(solve(N, L))

def test():
	import doctest
	doctest.testmod()

def __starting_point():
	main()
__starting_point()


import bisect as b
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		ans += b.bisect_left(L, L[i] + L[j]) - j - 1
print(ans)


import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(n):
	for j in range(i + 1, n):
		T = bisect.bisect_left(L, L[i] + L[j])
		count += T - j - 1
print(count)


import bisect
N = int(input())
L = sorted([int(x) for x in input().split()])
cnt = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		cnt += bisect.bisect_left(L, L[i] + L[j]) - (j + 1)
print(cnt)


import sys
from io import StringIO
import unittest
import bisect

def bin_search(arr, ls, c):
	l = ls - 1
	r = len(arr)
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[m] >= c:
			r = m
		else:
			l = m
	return l - ls + 1

def resolve():
	readline = sys.stdin.readline
	n = int(readline())
	arr = list(map(int, readline().rstrip().split()))
	arr.sort()
	ans = 0
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			c = arr[i] + arr[j]
			ans += bisect.bisect_left(arr, c, j + 1) - j - 1
	print(ans)
	return
if 'doTest' not in globals():
	resolve()
	return


from bisect import bisect_left
(n, *l) = list(map(int, open(0).read().split()))
l.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ng = n - bisect_left(l, l[i] + l[j]) + 1
		ans += n - j - ng
print(ans)


from fractions import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
n = I()
L = readInts()
L = sorted(L)
ans = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		a = L[i]
		b = L[j]
		c = bisect.bisect_left(L, a + b)
		ans += c - (j + 1)
print(ans)


from bisect import bisect
from bisect import bisect_left
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
cnt = 0
for i in range(n - 2):
	a = lis[i]
	for j in range(i + 1, n - 1):
		b = lis[j]
		tmp = bisect_left(lis, a + b)
		cnt += tmp - 1 - j
print(cnt)


import bisect
N = int(input())
D = [int(x) for x in input().split()]
D.sort()
total = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		total += bisect.bisect_left(D, D[i] + D[j]) - j - 1
print(total)


import sys
import bisect
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		l = L[i] + L[j]
		p = bisect.bisect_left(L, l)
		ans += p - j - 1
print(ans)


n = int(input())
l = sorted(map(int, input().split()))
from bisect import *
print(sum((bisect_left(l, l[i] + l[j]) - i - 1 for i in range(n) for j in range(i))))


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 1, 1, -1):
	for j in range(i - 1, 0, -1):
		ans += j - bisect.bisect_right(l, l[i] - l[j], hi=j)
print(ans)


import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
g = 0
for ai in range(n - 2):
	for bi in range(ai + 1, n - 1):
		g += max(0, bisect.bisect_left(l, l[bi] + l[ai]) - 1 - bi)
print(g)


import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0
for i in range(n - 2):
	for k in range(i + 1, n - 1):
		ans += bisect.bisect_left(l, l[i] + l[k]) - k - 1
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for x in range(n):
	for y in range(x + 1, n - 1):
		ans += bisect.bisect_left(l, l[x] + l[y]) - y - 1
print(ans)


from bisect import bisect_left
N = int(input())
L = sorted(map(int, input().split()))
ans = sum((j - bisect_left(L, L[i] - L[j] + 1, 0, j) for i in range(2, N) for j in range(i)))
print(ans)


import bisect
N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for m in range(N):
	for s in range(m):
		ans += bisect.bisect_left(L, L[m] + L[s]) - (m + 1)
print(ans)


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

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

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	import bisect
	n = i_input()
	l = sorted(i_list())
	ans = 0
	for a in range(n - 2):
		for b in range(a + 1, n - 1):
			ans += bisect.bisect(l, l[a] + l[b] - 1) - b - 1
	print(ans)

def __starting_point():
	main()
__starting_point()


from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		k = l[i] + l[j]
		pos = bisect_left(l, k)
		ans += max(0, pos - j - 1)
print(ans)


import bisect
N = int(input())
L_list = list(map(int, input().split()))
L_list_min = sorted(L_list)
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		min = j + 1
		max = bisect.bisect_left(L_list_min, L_list_min[i] + L_list_min[j])
		if max - min >= 0:
			ans += max - min
print(ans)


import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		k = bisect.bisect_left(L, L[i] + L[j])
		ans += max(k - j - 1, 0)
print(ans)


from bisect import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ans += bisect(L, L[i] + L[j] - 1) - j - 1
print(ans)


import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for a in range(1, n - 1):
	for b in range(a + 1, n):
		ans += max(0, a - bisect.bisect(l, l[b] - l[a]))
print(ans)


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])
(dy8, dx8) = ([0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def sum_of_arithmetic_progression(s, d, n):
	return n * (2 * s + (n - 1) * d) // 2

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

def lcm(a, b):
	g = gcd(a, b)
	return a / g * b

def solve():
	N = int(input())
	L = list(sorted(list(map(int, input().split()))))
	ans = 0
	for i in range(N):
		a = L[i]
		for j in range(i + 1, N):
			b = L[j]
			ans += bisect_left(L, a + b) - j - 1
	print(ans)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


import bisect
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0
for i in range(N - 2):
	for j in range(i + 1, N - 1):
		k = bisect.bisect_left(arr, arr[i] + arr[j])
		if k > j:
			ans += k - j - 1
		else:
			pass
print(ans)


n = int(input())
l = list(map(int, input().split()))
from bisect import bisect_left, bisect_right
l.sort()
a = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		a += bisect_left(l, l[i] + l[j]) - j - 1
print(a)


import bisect
N = int(input())
L = sorted([int(n) for n in input().split()])
count = 0
for i in range(N - 1):
	b = L[:i]
	c = L[i + 1:]
	for j in b:
		count += bisect.bisect_left(c, L[i] + j)
print(count)


N = int(input())
L = [int(x) for x in input().split()]
L.sort()
ans = 0
for i in range(N - 2):
	p = i + 2
	for j in range(i + 1, N - 1):
		while p < N and L[p] < L[i] + L[j]:
			p += 1
		ans += max(0, p - j - 1)
print(ans)