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

from collections import Counter
import heapq

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

hq  = sorted(tuple(Counter(l).items()), key=lambda x:x[0])

heapq.heapify(hq)
# print(hq)

for i in range(m):
    b,c = map(int,input().split())
    while b > 0:
        x,y = heapq.heappop(hq)
        if x < c:
            if b < y:
                heapq.heappush(hq,(c,b))
                heapq.heappush(hq,(x,y-b))
                b = 0
            else:
                heapq.heappush(hq,(c,y))
                b -= y
        else:
            heapq.heappush(hq,(x,y))
            break
    # print(hq)

ans = 0
for i in range(len(hq)):
    ans += hq[i][0]*hq[i][1]
print(ans)

### FIXED CODE ###

from collections import Counter
import heapq

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

hq  = sorted(tuple(Counter(l).items()), key=lambda x:x[0])

heapq.heapify(hq)
# print(hq)
BC = [list(map(int, input().split())) for i in range(m)]
BC = sorted(BC,key = lambda x:-x[1])

for b,c in BC:
    while b > 0:
        x,y = heapq.heappop(hq)
        if x < c:
            if b < y:
                heapq.heappush(hq,(c,b))
                heapq.heappush(hq,(x,y-b))
                b = 0
            else:
                heapq.heappush(hq,(c,y))
                b -= y
        else:
            heapq.heappush(hq,(x,y))
            break
    # print(hq)

ans = 0
for i in range(len(hq)):
    ans += hq[i][0]*hq[i][1]
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,j,l)

print(ans)

### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
k = int(input())
 
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,j,l)
 
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

INF = 2**31-1


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s


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

for j in range(N):
    T.add(j+1, j+1, A[j])
prev_T = T

for i in range(min(k, 3*int(math.log(N))+1)):
    T = RangeUpdate(N)
    for j in range(N):
        num = prev_T.sum(j+1, j+1)
        T.add(max(j - num + 1, 1), min(j + num + 1, N), 1)

    prev_T = T

ans = [0]*N
for i in range(N):
    ans[i] = prev_T.sum(i+1, i+1)

print(*ans)


### FIXED CODE ###

import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

N, k = map(int, input().split())
prev_arr = list(map(int, input().split()))

# N = k = 200000
# prev_arr = [0]*N

count = 0
for i in range(min(k, 3*int(math.log(N))+5)):
    que = []
    arr = [0]*N
    for j in range(N):
        heapq.heappush(que, j+prev_arr[j])
        while que[0] < j:
            heapq.heappop(que)
        arr[j] += len(que)
    # print(arr)

    que = []
    for j in reversed(range(N)):
        heapq.heappush(que, -(j-prev_arr[j]))
        while -que[0] > j:
            heapq.heappop(que)
        arr[j] += len(que) - 1

    prev_arr = arr
    count += 1

# print(count)
print(*prev_arr)
### BUGGY CODE ###

n = int(input())
candidate = [sorted(list(input())) for _ in range(n)]

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if str(candidate[i]) == str(candidate[j]):
            ans += 1
print(ans)

### FIXED CODE ###

from fractions import Fraction
import math
n = int(input())
candidate = [sorted(list(input())) for _ in range(n)]
ans = 0
candidate.sort()

# 有理数型をインポート
# 組合せの総数


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

#     if n < 0 or k < 0:
#         pdt = 0

#     else:
#         pdt = 1
#         for s in range(1, k + 1):
#             pdt *= Fraction(n - s + 1, s)

#     # 戻り値をint型にするために分子を取り出す
#     return pdt.numerator


cnt = []
num = 1
for i in range(1, n):
    if candidate[i] == candidate[i - 1]:
        num += 1
        if i == n - 1 and num > 1:
            cnt.append(num)
    else:
        if num > 1:
            cnt.append(num)
        num = 1
for i in cnt:
    if i > 1:
        ans += combinations_count(i, 2)
print(ans)
### BUGGY CODE ###

import numpy as np
X, Y, Z, K = [int(i) for i in input().split()]

A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

Anum = 0
Bnum = 0
Cnum = 0

AB=np.zeros(X*Y)
for i in range(X):
    for j in range(Y):
        AB[Y*i+j] = A[i]+B[j]

AB = sorted(AB, reverse=True)
AB = AB[:min(X*Y,K)]

ABC=np.zeros(len(AB)*Z)
for i in range(len(AB)):
    for j in range(Z):
        ABC[Z*i+j]=AB[i]+C[j]

ABC = sorted(ABC, reverse=True)

for i in range(K):
    print(int(ABC[i]))


### FIXED CODE ###

X, Y, Z, K = [int(i) for i in input().split()]

A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

Anum = 0
Bnum = 0
Cnum = 0

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB = sorted(AB, reverse=True)
AB = AB[:min(X*Y,K)]

ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])

ABC = sorted(ABC, reverse=True) 

for i in range(K):
    print(int(ABC[i]))
### BUGGY CODE ###

import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

import bisect
def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    for a in A:
        if a*a <= x:
            cnt -= 1
        if a > 0:
            c = x//a
            cnt += bisect.bisect_right(A, c)
        elif a < 0:
            c = (-x-1)//(-a)
            cnt += n - bisect.bisect_right(A, c)
        else:
            if x >= 0:
                cnt += n
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    m = (l+r)//2
    if ok(m):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

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

import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)
A = np.sort(A)

P = A[A>0]
Z = A[A==0]
N = A[A<0]

#t = n*(n-1)//2

def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    #cnt += np.searchsorted(A, np.ceil(x/P), side='right').sum()
    cnt += np.searchsorted(A, x//P, side='right').sum()
    #cnt += n-np.searchsorted(A, np.floor(x/N), side='left').sum()
    cnt += (n-np.searchsorted(A, (-x-1)//(-N), side='right')).sum()
    if x >= 0:
        cnt += len(Z)*n
    cnt -= np.count_nonzero(A*A <= x)
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

n,a = [int(i) for i in input().split()]

X = [int(i) for i in input().split()]
X = [0]+X
m = max(X+[a])
dp = [[[0]*50*(n+1) for i in range(n+1)] for j in range(n+1)]
#print(dp)


for i in range(n+1):
    for j in range(n+1):
        for k in range(m*(n+1)):
            if i == j == k == 0:
                dp[i][j][k] = 1
            elif i >= 1 and k < X[i]:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and k >= X[i]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

         

ans = 0
for i in range(1,n+1):
    ans += dp[n][i][i*a]
    
print(ans)

### FIXED CODE ###

n,a = [int(i) for i in input().split()]

X = [int(i)-a for i in input().split()]
dp = [[0]*(100*n+1) for i in range(n+1)]
#print(dp)
dp[0][50*n]=1

for i in range(n):
    for j in range(50,100*n+1-50):
            dp[i+1][j] = dp[i][j]+dp[i][j-X[i]]
        
ans = dp[n][n*50]-1
    
print(ans)
### BUGGY CODE ###

from collections import Counter

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

for k in range(N):
  sum_k = 0
  temp_c = c.copy()
  temp_c[A[k]] -= 1
  for v in temp_c.values():
    if v > 1:
      sum_k += cmb(v,2)
  print(int(sum_k))

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb

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

num = 0
for v in c.values():
  if v > 1:
      num += comb(v, 2,exact=True)
for k in range(N):
  print(int(num - (c[A[k]]-1)))
### BUGGY CODE ###

s=list(input())
for i in range(0,len(s)):
    s[i]=int(s[i])
    
adj=-1
op=0
while(adj==-1):
    adj=0
    for i in range(1,len(s)):
        if((s[i]==0 and s[i-1]==1) or (s[i]==1 and s[i-1]==0)):
            adj=-1
            s[i]=2
            s[i-1]=2
            op+=2
    while True:
        try:
            s.remove(2)
        except:
            break
            
print(op)


### FIXED CODE ###

def main(s):
    a = s.count("0")
    b = s.count("1")
    return 2*min(a,b)

s = input()


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

import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [[float("INF"),float("INF")]] * (n + 1)
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

heapq.heapify(cost)
nn,l = heapq.heappop(cost)
for i in range(n):
    while l <= i:
        nn,l = heapq.heappop(cost)
    print(10 ** 15 - nn)


### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group(self):
        return [self.members(r) for r in self.roots()]
      
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
input = sys.stdin.readline
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
  x, y = map(int, input().split())
  uf.unite(x, y)
ans = 0
L = []
for l in uf.all_group():
  K = []
  for i in l:
    heapq.heappush(K, A[i])
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

### FIXED CODE ###

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

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  G[x].append(y)
  G[y].append(x)
ans = 0
L = []
seen = [False]*n
def dfs(v):
  global ans
  K = []
  stack = [v]
  while stack:
    v = stack.pop()
    heapq.heappush(K, A[v])
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for i in range(n):
  if not seen[i]:
    dfs(i)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [ int(input()) for x in range(n) ] 

maximum = max(a)

for i in a:
    if i == maximum:
        b = a.copy()
        b.remove(i)
        print( max(b) )
    else:
        print(maximum)

### FIXED CODE ###

n = int(input())
a = [ int(input()) for x in range(n) ] 

b = sorted(a, reverse = True)
maximum = b[0]

for i in a:
    if i == maximum:
        print(b[1])
    else:
        print(maximum)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int, input().split()))

HP = sum(H)
count = 0
Z = 0
if K >= len(H):
    print(0)

else:
    for k in range(K):
        Z += sorted(H, reverse=True)[k]
    hp = HP - Z
    print(hp)

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int, input().split()))

HP = sum(H)
ld = sorted(H , reverse=True)
if K >= len(H):
    print(0)

else:
    Z = sum(ld[:K])
    hp = HP - Z
    print(hp)
### BUGGY CODE ###

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

import numpy as np

table = np.zeros((N+1, W+1))
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return int(table[N][W])

print(dp(N, W))

### FIXED CODE ###

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

table = {i: [0]*(W+1) for i in range(N+1)}
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return table[N][W]

print(dp(N, W))
### BUGGY CODE ###

class work(object):
    def __init__(self, nums):
        self.a = nums[0]
        self.b = nums[1]

    def __repr__(self):
        return "({}, {})".format(self.a, self.b)

    def __lt__(self, other):
        if self.a == other.a:
            return self.b > other.b
        return self.a < other.a


(n, m) = map(int, input().split())
works = []
for _ in range(n):
    works.append(work(list(map(int, input().split()))))
sorted_works = sorted(works)

sum = 0
for i in range(1, m + 1):
    index = 0
    for j, w in enumerate(sorted_works):
        if i < w.a:
            break
        index += 1
    if 0 == index:
        continue
    target_works = sorted_works[:index]
    best_work = max(enumerate(target_works), key=lambda x: x[1].b)
    sum += best_work[1].b
    del sorted_works[best_work[0]]

print(sum)


### FIXED CODE ###

import heapq

(n, m) = map(int, input().split())
jobs = {}
for _ in range(n):
    (a, b) = map(int, input().split())
    if not a in jobs:
        jobs[a] = []
    jobs[a].append(-b)

heap = []
sum = 0
for i in range(1, m + 1):
    if i in jobs:
        for j in jobs[i]:
            heapq.heappush(heap, j)
    if 0 < len(heap):
        sum -= heapq.heappop(heap)
print(sum)
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = 0

    for i in range(1,10**5):
        cnt = max(a.count(i-1)+a.count(i)+a.count(i+1),cnt)
    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = [0] * (max(a) + 2)

    for i in a:
        if i != 0:
            cnt[i-1] += 1
        cnt[i] += 1
        cnt[i+1] += 1
    print(max(cnt))

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

N = int(input())
se = [()] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = (x-l, x+l)
se = sorted(se, key=lambda x: x[1])
ans = []
while se:
	now = se.pop(0)
	temp = []
	for s, e in se:
		if now[1] <= s:
			temp.append((s, e))
	se = temp
	ans.append(now)
print(len(ans))

### FIXED CODE ###

N = int(input())
se = [[]] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = [x-l, x+l]
se = sorted(se, key=lambda x: x[1])
ans = N
for i in range(1, N):
	if se[i-1][1] > se[i][0]:
		se[i][1] = se[i-1][1]
		ans -= 1
print(ans)
### BUGGY CODE ###

from collections import deque
N=int(input())
K=list(input())

ans = 0
while len(K)>3:
    a = K.pop()
    for i, b in enumerate(K):
        if b != a:
            k = K[i+1:]
    
            for ii,c in enumerate(k):
                    if (c != b) and (c != a):
                        if (ii != (len(k)-1)/2):
                            ans +=1
                 
print(ans)


### FIXED CODE ###

N=int(input())
K=input()
dic = {}
ts = 'RGB'
for t in ts:
    p=[]
    for ir, r in enumerate(K):
        if r == t:
            p.append(ir)
    dic[t] = p
ans1 = len(dic['R']) * len(dic['G']) * len(dic['B'])

ans2 = 0

for i in range(N):
    for j in range(i, N):
        if (i + 2*(j-i) < N):
            if  K[i] != K[j] and K[i] != K[i + 2*(j-i)] and K[i+2*(j-i)] != K[j]:
                ans2 +=1

print(ans1 - ans2)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ret = 0
    for a in range(N-2):
        for b in range(a+1,N-1):
#            a<b+c => a-b<c
#            b<c+a => b-a<c
#            c<a+b
# b-a<c<a+b
            rr = bisect_right(L[b+1:], L[a]+L[b]-1)
            ll = bisect_left(L[b+1:], L[b]-L[a]+1)
            ret += rr - ll

    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
answer = 0
for i in range(len(S)-3):
    num = int(S[i:i+4])
    remain = num % 2019
    if remain == 0:
        answer += 1
    for j in range(i+4, len(S)):
        remain = (remain * 10 + int(S[j])) % 2019
        if remain == 0:
            answer += 1

print(answer)


### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
mod_cnt = [0] * 2019
mod_cnt[0] = 1
power = 1
remain = 0
answer = 0
for i in range(len(S)-1, -1, -1):
    remain += int(S[i]) * power
    remain %= 2019
    power *= 10; power %= 2019
    answer += mod_cnt[remain]
    mod_cnt[remain] += 1

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

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

l.sort(reverse=True)
kmax = len(format(l[0], 'b'))

l0 = [0]*kmax
l1 = [0]*kmax

for i in range(n):
  a = format(l[i], 'b')
  a = ''.join(list(reversed(a)))
  for j in range(kmax):
    if j > len(a)-1:
      l0[j] += 1
    elif a[j] == '0':
      l0[j] += 1
    else:
      l1[j] += 1

ans = 0
for k in range(kmax):
  ans += l0[k]*l1[k]*(2**k)
  ans %= 10**9+7
print(ans)

### FIXED CODE ###

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

l.sort(reverse=True)
kmax = len(format(l[0], 'b'))

l0 = [0]*kmax
l1 = [0]*kmax

for i in range(n):
  a = format(l[i], 'b')
  a = ''.join(list(reversed(a)))
  for j in range(kmax):
    if j > len(a)-1:
      l0[j] += 1
    elif a[j] == '0':
      l0[j] += 1
    else:
      l1[j] += 1

ans = 0
for k in range(kmax):
  ans += l0[k]*l1[k]*(2**k)
  ans %= 10**9+7
print(ans)