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

from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + xmt[i][j]
	
	#for i in range(n + 1):
	#	print(cmt[i])

	for query in queries:
		ans = 0
		for j in range(query[0], query[1] + 1):
			ans += cmt[j][query[1]] - cmt[j][query[0] - 1] 
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + (cmt[i - 1][j] - cmt[i - 1][j - 1]) + xmt[i][j] 
	
	for query in queries:
		i, j = query
		ans = cmt[j][j] - cmt[i - 1][j] - cmt[j][i - 1] + cmt[i - 1][i - 1]
		print(ans)

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

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=sum(B[0:A[1]])
for i in range(A[0]-A[1]+1):
  C=max(C,sum(B[i:i+A[1]]))
print((C+A[1])/2)



### FIXED CODE ###

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=sum(B[0:A[1]])
D=C
for i in range(A[1]-1,A[0]-1):
  D=D+B[i+1]-B[i-A[1]+1]
  C=max(C,D)
print((C+A[1])/2)
### BUGGY CODE ###

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    g = [[] for _ in range(n)] 
    for _ in range(m):
        a,b = map(int, input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    for i in g[0]:
        if i in g[-1]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(set(x+y)):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


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

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            S += gcd(a, b, c)
print(S)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            if a == b == c:
                S += a
            if a == b != c or a != b == c:
                S += 3*math.gcd(a,c)
            if a != b != c:
                S += 6*gcd(a, b, c)
print(S)
### BUGGY CODE ###

S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = (3 if S[i] == "?" else 1) * d[i+1][3]
	d[i][2] = (3 if S[i] == "?" else 1) * d[i+1][2]
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = (3 if S[i] == "?" else 1) * d[i+1][1]
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = (3 if S[i] == "?" else 1) * d[i+1][0]
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)


### FIXED CODE ###

S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = ((3 if S[i] == "?" else 1) * d[i+1][3])%P
	d[i][2] = ((3 if S[i] == "?" else 1) * d[i+1][2])%P
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = ((3 if S[i] == "?" else 1) * d[i+1][1])%P
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = ((3 if S[i] == "?" else 1) * d[i+1][0])%P
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)
### BUGGY CODE ###


def main():
    L = input()
    n = len(L)
    t = []
    mod = 10 ** 9 + 7
    for i, v in enumerate(L):
        if v == '1':
            t.append(i)
    r = 1
    for i in reversed(t):
        r *= 2
        r += 3 ** (n - i - 1)
    print(r % mod)
main()


### FIXED CODE ###


def main():
    L = input()
    n = len(L)
    t = []
    mod = 10 ** 9 + 7
    for i, v in enumerate(L):
        if v == '1':
            t.append(i)
    r = 1
    p = 1
    for i, v in enumerate(reversed(L)):
        p %= mod
        if v == '1':
            r *= 2
            r += p
            r %= mod
        p *= 3
    print(r % mod)
main()
### BUGGY CODE ###

hyou = [0]*100001

N =  int(input())
a_data = [int(x) for x in input().split()]
Q = int(input())
b_data = [[int(x) for x in input().split()] for _ in range(Q)]

# 数列を分類
for x in a_data:
    hyou[x] += 1
# 操作と合計
for before_value,after_value in b_data:
    # 数値の入れ替え
    hyou[after_value] = hyou[before_value] + hyou[after_value] 
    hyou[before_value] = 0

    # 合計を求めて出力
    total = 0
    for i,x in enumerate(hyou):
        total += i*x
    print(total)

### FIXED CODE ###

hyou = [0]*100001

N =  int(input())
a_data = [int(x) for x in input().split()]
Q = int(input())
b_data = [[int(x) for x in input().split()] for _ in range(Q)]

# 数列を分類
for x in a_data:
    hyou[x] += 1
# 現段階の合計を求める。
total = 0
for i,x in enumerate(hyou):
    total += i*x

# 操作と合計
for before_value,after_value in b_data:
    total += (after_value - before_value) * hyou[before_value] 
    # 数値の入れ替え
    hyou[after_value] = hyou[before_value] + hyou[after_value] 
    hyou[before_value] = 0

    # 合計を出力
    print(total)
### BUGGY CODE ###

INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (20000)
dp[0] = 0
for a,b in ab:
    for j in range(H):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
print(min(dp[H:]))

### FIXED CODE ###

INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (20000)
dp[0] = 0
for a,b in ab:
    for j in range(H):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
print(min(dp[H:]))
### BUGGY CODE ###

def resolve():
    A, B, K = map(int, input().split())
    count = [A]
    ans = []
    for _ in range(1, B-A+1):
        count.append(A+_)
    if K > B-A-1:
        K = B-A+1
    for i in range(K):
        ans.append(count[i])
        if count[(i+1)*-1] > A+K-1:
            ans.append(count[(i+1)*-1])
    an = sorted(ans)
    for i in range(len(an)):
        print(an[i])
resolve()

### FIXED CODE ###

def resolve():
    A, B, K = map(int, input().split())
    if 2*K > B-A+1:
        for _ in range(B-A+1):
            print(A+_)
    else:
        for i in range(K):
            print(A+i)
        for j in range(K):
            print(B-K+j+1)
resolve()
### BUGGY CODE ###

from itertools import accumulate
from collections import Counter

s = input()
s = list(s)[::-1]
A = [int(s[i])  * (10**(i))for i in range(len(s))]
A = [0] + list(accumulate(A))
A = [a%2019 for a in A]

A = Counter(A).most_common()
ans = 0
for _, count in A:
  if count == 1:
    break
  ans += count*(count-1)//2
print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter

s = input()
s = list(s)[::-1]
ten = [1]
for _ in range(len(s)):
  ten.append(ten[-1]*10 % 2019)
  
A = [(int(s[i])  * ten[i])%2019 for i in range(len(s))]
A = list(accumulate(A))
A = [a%2019 for a in A]
A = [0] + A

A = Counter(A).most_common()
ans = 0
for _, count in A:
  if count == 1:
    break
  ans += count*(count-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
while True:
    a = list(set(a))
    tmp = a[:]
    for i in tmp:
        if i == a[0]:
            continue
        elif i % a[0] == 0:
            a.remove(i)
        else:
            a.append(i % a[0])
    a.sort()
    if len(a) == 1:
        break
print(a[0])


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
while True:
    a = sorted(list(set(a)))
    tmp = sorted(a[:])
    for i in tmp:
        if i == a[0]:
            continue
        elif i % a[0] == 0:
            a.remove(i)
        else:
            a.append(i % a[0])
            if i % a[0] == 1:
                print(1)
                exit()
            a.remove(i)
    if len(a) == 1:
        break
print(a[0])
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = [0 for k in range(M)]
B = [0 for k in range(M)]
for k in range(M):
    A[k], B[k] = map(int, input().split())
    A[k] -= 1
    B[k] -=1
good = [1 for k in range(N)]
for k in range(N):
    for j in range(M):
        if k == A[j] and H[k]<=H[B[j]]:
            good[k] = 0
        if k == B[j] and H[k]<=H[A[j]]:
            good[k] = 0

print(sum(good))
        

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = [0 for k in range(M)]
B = [0 for k in range(M)]

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

for k in range(M):
    if H[A[k]] <= H[B[k]]:
        good[A[k]] = 0
    if H[A[k]] >= H[B[k]]:
        good[B[k]] = 0   
        '''
for k in range(N):
    if good[k] ==1:
        if k in A:
            for j in range(M):
                if k == A[j] and H[k]<=H[B[j]]:
                    good[k] = 0
                if k == A[j] and H[k]>=H[B[j]]:
                    good[B[j]] = 0
        if k in B:
            for j in range(M):
                if k == B[j] and H[k]<=H[A[j]]:
                    good[k] = 0
                if k == B[j] and H[k]>=H[A[j]]:
                    good[A[j]] = 0
'''
print(sum(good))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0, -1)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p, tree, ans):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v, tree, ans)

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    dfs(0, -1, tree, ans)

    print(*ans)

main()
### BUGGY CODE ###

# C - Go to School
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [a.index(i) + 1 for i in range(1, n+1)]
    print(" ".join(map(str, ans)))

if __name__ ==  "__main__":
    main()

### FIXED CODE ###

# C - Go to School
def main():
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    a = np.array(a)
    a = np.argsort(a)
    for i in a:
        print(i+1,end=" ")

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

N,M=map(int, input().split())
P=[]
S=[]
for i in range(M):
    p,s=input().split()
    P.append(int(p))
    if s=="WA":
      S.append(0)
    else:
      S.append(1)


import numpy as np
P=np.array(P)
S=np.array(S)

if M>0:
    ans=np.unique(P[S==1])

    wa=0
    for j in ans:
        for i in S[P==j]:
            if i==0:
                wa+=1
            else:
                break

    print(len(ans),wa)
else:
    print(0,0)


### FIXED CODE ###

N,M=map(int,input().split())
AC={}
WA={}
for i in range(M):
    a,b=input().split()
    if not(a in AC.keys()):
        if b=="AC":
            AC[a]=1
        else:
            if a in WA.keys():
                WA[a]+=1
            else:
                WA[a]=1
y=0
for i in AC.keys():
    if i in WA.keys():
        y+=WA[i]
print(sum(AC.values()),y)
### BUGGY CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(set(A))
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = 2**e - a
            if counter[b] == 0:
                continue
            if a > b:
                adj[a].append(b)
            elif a < b:
                adj[b].append(a)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = 2**e
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを考え
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        b = pow2[a.bit_length()] - a
        if counter[b] == 0:
            continue
        cnt = min(counter[a], counter[b])
        ans += cnt
        counter[a] -= cnt
        counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


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

N=int(input())

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

Amap=dict()

for i in range(N):
    if A[i] in Amap:
        Amap[A[i]]+=1
    else:
        Amap[A[i]]=1

# print(Amap)

Q=int(input())
ans = list()
for i in range(Q):
    B, C =list(map(int,input().split()))

    if B in Amap:
        if C in Amap:
            Amap[C] += Amap[B]
        else:
            Amap[C] = Amap[B]

    else:
        if C in Amap:
            Amap[C] += 0
        else:
            Amap[C] = 0

    Amap[B] = 0
    # print(i, B, C, Amap)


    s = 0
    for k in Amap.keys():
        s += (int(k)*Amap[k])
    ans.append(s)
    # print(s)

for s in ans:
    print(s)

### FIXED CODE ###

N=int(input())

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

Amap=dict()

for i in range(N):
    if A[i] in Amap:
        Amap[A[i]]+=1
    else:
        Amap[A[i]]=1

# print(Amap)

s = 0
for k in Amap.keys():
    s += (int(k)*Amap[k])


Q=int(input())
ans = list()
for i in range(Q):
    B, C =list(map(int,input().split()))

    if B in Amap:
        if C in Amap:
            Amap[C] += Amap[B]
            s += (C-B)*Amap[B] 
        else:
            Amap[C] = Amap[B]
            s += (C-B)*Amap[B] 

    else:
        if C in Amap:
            Amap[C] += 0
        else:
            Amap[C] = 0

    Amap[B] = 0
    # print(i, B, C, Amap)


    ans.append(s)
    # print(s)

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

H,W=map(int,input().split())
n=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if (i+j)%2==0:
            n+=1
print(n)

### FIXED CODE ###

H,W=map(int,input().split())
if H==1 or W==1:
    print(1)
elif (H*W)%2==0:
    print((H*W)//2)
else:
    print((H*W+1)//2)
### BUGGY CODE ###


import random

def main():
    D = int(input())
    c_list = list(map(int, input().split()))
    s_list = [list(map(int, input().split())) for _ in range(D)]
    
    basic_bad = sum(c_list)

    # 初期解生成は必要っぽい
    res = 0
    bad = 0
    last_open = [0] * 26
    t_list = [0] * D

    max_res = -1
    max_t_list = [0] * D

    # loop
    for m in range(10**5):
        t_list = [random.randint(0,25) for i in range(D)]
        res = 0
        bad = 0
        last_open = [0] * 26
        for i in range(D):
            t = t_list[i]
            
            res += s_list[i][t]
            bad += basic_bad - (i+1 - last_open[t]) * c_list[t]
            last_open[t] = i+1

            res -= bad
            
        if max_res == -1 or max_res < res:
            max_res = res
            max_t_list = t_list.copy()

    for t in max_t_list:
        print(t+1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import random

D = int(input())
c_list = list(map(int, input().split()))
s_list = [list(map(int, input().split())) for _ in range(D)]

for i in range(D):
    print(random.randint(1,26))
### BUGGY CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
self_d = {}
d = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

for i in m:
    cnt = 0
    for j,k in c.items():
        if j == i:
            if k - 1 >= 2:
                self_d.setdefault(j, ans(k-1))
                cnt += self_d[j]
                
        else:
            d.setdefault(j, ans(k))
            cnt += d[j]
        
    print(cnt)

### FIXED CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
hyouji = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

cnt = 0
for i,j in c.items():
    n = ans(j)
    d[i] = n
    cnt += n


for k in m:
    if k in hyouji:
        print(hyouji[k])
    else: 
        if c[k] < 2:
            q = cnt
        elif c[k] == 2:
            q = cnt - 1
        else:
                q = cnt -d[k] + ans(c[k] - 1)

        hyouji[k] = q
        print(hyouji[k])
### BUGGY CODE ###

import fractions

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

G = fractions.gcd(A, B)

res = 1

i = 2
while G > 1:
    if G % i == 0:
        res += 1
        while G % i == 0:
            G /= i
    else:
        if i == 2:
            i += 1
        else:
            i += 2

print(res)


### FIXED CODE ###

import fractions

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

G = fractions.gcd(A, B)

res = 1

for i in [2] + list(range(3, int(G ** 0.5) + 1, 2)):
    if G % i == 0:
        res += 1
        while G % i == 0:
            G //= i

if G > 2:
    res += 1

print(res)
### BUGGY CODE ###

N = int(input())

l = []
for x in range(N):
    x = input()
    l.append(x)
    

lst = sorted(list(set(l)))
n_list = []


for x in lst:
    n = l.count(x)
    n_list.append(n)

max_n = max(n_list)
l_max = [i for i, x in enumerate(n_list) if x == max_n]

for x in l_max:
    print(lst[x]) 

### FIXED CODE ###

import collections

N = int(input())

l = []
for x in range(N):
    x = input()
    l.append(x)

l_dict = collections.Counter(l)

max_n = max(l_dict.values())

l_max = sorted([x[0] for x in l_dict.items() if x[1] == max_n])

for a in l_max:
    print(a)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7
dp = [0]*(n+1)
dp[0]=1

if not 1 in a:
  dp[1]=1

for i in range(2, n+1):
  if i in a:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]

print(dp[n]%mod)


### FIXED CODE ###

n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}

mod = 10**9+7
dp = [0]*(n+1)
dp[0]=1

if not 1 in a:
  dp[1]=1

for i in range(2, n+1):
  if i in a:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]

print(dp[n]%mod)
### BUGGY CODE ###

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

count = 0
for i in range(n):
    start_j = i + 1
    for j in range(start_j, n):
        start_k = j + 1
        for k in range(start_k, n):
            a = l_list[i]
            b = l_list[j]
            c = l_list[k]
            
            if (c<a+b and b<a+c and a<b+c):
                count += 1

print(count)

### FIXED CODE ###

import bisect

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

l_list.sort()

count=0
for i in range(n-2):
    for j in range(i+1,n-1):
        a=l_list[i]
        b=l_list[j]
        
        count+=(bisect.bisect_left(l_list,a+b)-j-1)

print(count)
### BUGGY CODE ###

import math

def comb(n, k, MOD, N):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N], MOD-2, MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n-k] % MOD

x, y = map(int, input().split())
mod = 10**9+7

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**7))

### FIXED CODE ###

import math

def comb(n, k, MOD, N):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N], MOD-2, MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n-k] % MOD

x, y = map(int, input().split())
mod = 10**9+7

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0 or (min(x, y) - diff) < 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**6))
### BUGGY CODE ###

n = int(input())
ans = 0
for h in range(1,n + 1):
    ans = 0
    for x in range(1, int((n/2)**0.5) + 1):
        for y in range(1, int((n/2)**0.5) + 1):
            for z in range(1, int((n/2)**0.5) + 1):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == h:
                    ans += 1
    print(ans)

### FIXED CODE ###

n = int(input())
ANS =[0 for _ in range(n)]
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            if x**2 + y**2 + z**2 + x*y + y*z + z*x > n:
                continue
            ANS[(x**2 + y**2 + z**2 + x*y + y*z + z*x) - 1] += 1
for i in ANS:
    print(i)