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

import math
from collections import deque

class UnionFind():
  def __init__(self, n):
    self.seg_tree = [-1 for i in range(n)]
  
  def root(self, i):
    if self.seg_tree[i] < 0:
      return i
    else:
      self.seg_tree[i] = self.root(self.seg_tree[i])
      return self.seg_tree[i]

  def size(self, i):
    return -self.seg_tree[self.root(i)]

  def unite(self, i, j):
    if self.same(i, j):
      return

    if self.size(i) == self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    elif self.size(i) > self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    else:
      self.seg_tree[self.root(j)] -= self.size(i)
      self.seg_tree[self.root(i)] = self.root(j)

  def same(self, i, j):
    return self.root(i) == self.root(j)

def nC2(n):
  return math.factorial(n) / math.factorial(2) / math.factorial(n - 2)

N, M = map(int, raw_input().split())
A = []
B = []
rev_res = []
rev_res.append(nC2(N))
uf = UnionFind(N)
for _ in range(M):
  a, b = map(long, raw_input().split())
  A.append(a - 1)
  B.append(b - 1)

for a, b in reversed(zip(A, B)):
  if not uf.same(a, b):
    res = rev_res[-1] - uf.size(a) * uf.size(b)
  else:
    res = rev_res[-1]
  rev_res.append(res)
  uf.unite(a, b)

for r in reversed(rev_res[:-1]):
  print r

### FIXED CODE ###

import math
from collections import deque

class UnionFind():
  def __init__(self, n):
    self.seg_tree = [-1 for i in range(n)]
  
  def root(self, i):
    if self.seg_tree[i] < 0:
      return i
    else:
      self.seg_tree[i] = self.root(self.seg_tree[i])
      return self.seg_tree[i]

  def size(self, i):
    return -self.seg_tree[self.root(i)]

  def unite(self, i, j):
    if self.same(i, j):
      return

    if self.size(i) == self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    elif self.size(i) > self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    else:
      self.seg_tree[self.root(j)] -= self.size(i)
      self.seg_tree[self.root(i)] = self.root(j)

  def same(self, i, j):
    return self.root(i) == self.root(j)

def nC2(n):
  return math.factorial(n) / math.factorial(2) / math.factorial(n - 2)

N, M = map(int, raw_input().split())
A = []
B = []
rev_res = []
uf = UnionFind(N)
for _ in range(M):
  a, b = map(long, raw_input().split())
  A.append(a - 1)
  B.append(b - 1)

ans = N * (N - 1) / 2
for a, b in reversed(zip(A, B)):
  rev_res.append(ans)
  if not uf.same(a, b):
    ans -= uf.size(a) * uf.size(b)
  uf.unite(a, b)

for r in reversed(rev_res):
  print r
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0

for i, x in enumerate(c):
    r = n-i-1
    cnt += (2**i + int(2**(i-1)) * i) * (2**r) * x
    cnt %= MOD

print(cnt * (2**n % MOD) % MOD)


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)
### BUGGY CODE ###

m, n = map(int, input().split())
print(divmod(pow(m, n), 1000000007)[1])

### FIXED CODE ###

m, n = map(int, input().split())
print(pow(m, n, 1000000007))
### BUGGY CODE ###

import sys

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


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)


### FIXED CODE ###

from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()
### BUGGY CODE ###

S = list(str(input()))
Q = int(input())

R = 0

for i in range(Q):
    Query = str(input())
    if len(Query) == 1:
        R = (R+1)%2
    else:
        T,F,C = map(str,Query.split())

        if (R + int(F) ) % 2 == 1:
            S.insert(0,C)
        else:
            S.append(C)

if R == 1:
    S = S[::-1]

for i in range(len(S)):
    print(S[i],end="")

### FIXED CODE ###

from collections import deque

S = list(str(input()))
Q = int(input())

d = deque(S)
R = 0

for i in range(Q):
    Query = str(input())
    if len(Query) == 1:
        R = (R+1)%2
    else:
        T,F,C = map(str,Query.split())

        if (R + int(F)) % 2 == 1:
            d.appendleft(C)
        else:
            d.append(C)

if R == 1:
    d.reverse()

for i in range(len(d)):
    print(d[i],end="")
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(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 k in range(1,K+1):
            if i==1 or j==1 or k ==1:
                ans += 1
            else:
                ans += gcd(i,j,k)

print(ans)


### FIXED CODE ###

#test.py
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(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 k in range(1,K+1):
            if i==1 or j==1 or k ==1:
                ans += 1
            else:
                ans += gcd(i,j,k)

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

N=int(input())
count=0
s=[sorted(input()) for i in range(N)]
n=['a' for t in range(N) for i in range(t+1,N) if s[t]==s[i]]
print(len(n))

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
        
        


### FIXED CODE ###

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
### BUGGY CODE ###

N = int(input())
A_i = list(map(int, input().split()))
uq_A_i = list(set(A_i))
C = [0] * N
for i in uq_A_i:
    C[i - 1] = A_i.count(i)
for c in C:
    print(c)


### FIXED CODE ###

N = int(input())
A_i = list(map(int, input().split()))
C = [0] * N
for i in A_i:
    C[i - 1] += 1
print(*C)
### BUGGY CODE ###

N,M = map(int,input().split())
ans = N-1
d = []
for m in range(M):
  A,B = map(int,input().split())
  for i,di in enumerate(d):
    if set([A,B]).issubset(di):
      d[i] = di|set([A,B])
      break
  else:
    d.append(set([A,B]))
    ans -= 1
print(ans)

### FIXED CODE ###

def f(x):
  while p[x]>0: x = p[x]
  return x
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)
### BUGGY CODE ###

import itertools
from collections import deque
s=input()
splitlist=[[k, len(list(g))] for k, g in itertools.groupby(s)]
n=len(splitlist)
#print(splitlist)

def makelist(lst):
	nlst=[]
	if lst[0]=="<":
		for i in range(lst[1]+1):
			nlst.append(i)
	else:
		for i in range(lst[1]+1):
			nlst.append(lst[1]-i)
	return deque(nlst)

def mergelist(a,b):
	if a[-1]>b[0]:
		b.popleft()
	else:
		a.pop()
	return list(a)+list(b)

lst=makelist(splitlist[0])
for i in range(1,n):
	lst=mergelist(lst,makelist(splitlist[i]))
print(sum(lst))

### FIXED CODE ###

import itertools
s=input()
splitlist=[[k, len(list(g))] for k, g in itertools.groupby(s)]
n=len(splitlist)
#print(splitlist)

def total(lst):
	return lst[1]*(lst[1]+1)//2


ans=total(splitlist[0])
for i in range(1,n):
	ans+=total(splitlist[i])
	if splitlist[i][0]==">":
		ans-=min(splitlist[i-1][1],splitlist[i][1])
print(ans)
### BUGGY CODE ###

def permutation_modp(n,k):
    ans=1
    for i in range(k):
        ans*=(n-i)
    return ans%1000000007
num_vertax,num_coler=map(int,input().split())
ver_array=[0]*num_vertax
for i in range(num_vertax-1):
    a,b=map(int,input().split())
    ver_array[a-1]+=1
    ver_array[b-1]+=1
ans=num_coler
top=1
for ver in ver_array:
    ans=(ans%1000000007)*permutation_modp(num_coler-2+top,ver+top-1)
    top=0
print(ans%1000000007)

### FIXED CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[False for i in range(N)] #0ならまだ塗ってない
 
abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    r_0 = int(s[-1]) % 13
    dp[0][r_0] += 1
else:
    for k in range(10):
        r_0 = k % 13
        dp[0][r_0] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] != "?":
            j = (int(s[-(i+1)]) * (10**i) + r) % 13
            dp[i][j] += dp[i-1][r]
        else:
            for k in range(10):
                j = (k * (10**i) + r) % 13
                dp[i][j] += dp[i-1][r]
print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = [0 for _ in range(N+1)]
stack = [[N,0]]
count[N] = 1
ok = False
for i in range(2*M):
    if stack == []:
        break
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                if count[i] == 0:
                    stack.append([i,arr[1]+1])
                    count[i] = 1
print('POSSIBLE' if ok else 'IMPOSSIBLE')    

### FIXED CODE ###

N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)
### BUGGY CODE ###

import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===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 union(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_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())


def main():
    n, m = ns()

    uf = UnionFind(n)

    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        uf.union(a, b)

    ans = 0
    for i in range(n):
        p = min(uf.parents)
        ans = max(ans, -p)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, m = ns()

    e = [[] for _ in range(n)]

    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    visited = [False for _ in range(n)]

    ans = 0
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            cnt = 1
            que = collections.deque()
            que.append(i)

            while que:
                q = que.popleft()

                for ei in e[q]:
                    if not visited[ei]:
                        visited[ei] = True
                        cnt += 1
                        que.append(ei)

            ans = max(ans, cnt)
    print(ans)


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

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [None] * N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        l = min(n, K)
        min_num = 10 ** 10
        dp[n] = min([min(abs(A[n] - A[n - k]) + dp[n - k], min_num) for k in range(1, l + 1)])

print(dp[-1])


### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

print(dp[-1])
### BUGGY CODE ###

# coding:utf-8

memo = []

def main():
    N,Q = map(int,input().split())
    S = input()
    for i in range(N-1):
        if S[i:i+2] == "AC":
            memo.append(i)
    # print(memo)
    for i in range(Q):
        li,ri = map(int,input().split())
        count = len(memo)
        # 両方の範囲に入る最初と最後
        start = -1
        end = -1

        for i in range(len(memo)):
            if ac_check(i,li,ri):
                start = i
                break
        if start < 0:
            count = 0
        else:
            for i in reversed(range(len(memo))):
                if ac_check(i,li,ri):
                    end = i
                    break
            # print(start,end)
            count = count - (start) - (len(memo)-end) + 1

        print(count)

def ac_check(i,li,ri):
    if memo[i] >= li-1 and memo[i]+1 <= ri-1:
        return True
    return False

# def ac_check(sub_s):
#     count = 0
#     for i in range(len(sub_s)-1):
#         if sub_s[i:i+2] == "AC":
#             count += 1
#     return count


if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8

memo = []

def main():
    N,Q = map(int,input().split())
    S = input()
    t = [0] *(N+1)
    for i in range(N):
        if S[i:i+2] == "AC":
            t[i+1] = t[i] + 1
        else:
            t[i+1] = t[i]
    # for i in range(N-1):
    #     if S[i:i+2] == "AC":
    #         memo.append(i)
    # print(memo)

    for i in range(Q):
        li,ri = map(int,input().split())
        print(t[ri-1] - t[li-1])
        # count = len(memo)
        # 両方の範囲に入る最初と最後
        # print(li,ri)
        # for i in range(li-1,ri-1):
        #     # print("debug"+str(i))
        #     if S[i] == "A" and S[i+1] == "C":
        #         count += 1
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else: 
        #     for i in reversed(range(li-1,ri+1)):
        #         if S[i-1] == "A" and S[i] == "C":
        #             end = i-1
        #             break
        #     print(start,end)
        #     count = memo.index(end) - memo.index(start) + 1


        # for i in range(len(memo)):
        #     if ac_check(i,li,ri):
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else:
        #     for i in reversed(range(len(memo))):
        #         if ac_check(i,li,ri):
        #             end = i
        #             break
        #     # print(start,end)
        #     count = count - (start) - (len(memo)-end) + 1
        # print(count)

# def ac_check(i,li,ri):
#     if memo[i] >= li-1 and memo[i]+1 <= ri-1:
#         return True
#     return False

# def ac_check(sub_s):
#     count = 0
#     for i in range(len(sub_s)-1):
#         if sub_s[i:i+2] == "AC":
#             count += 1
#     return count


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

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tc = N
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 = j+1
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        ans += end-j-1
print(ans)

### FIXED CODE ###

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 #これをiの中でできないか
            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)