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

from bisect import insort_left, bisect_left
n = int(input())
s = input()
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind+1)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)
    if t=='1':
        for li in dic.values():
            if a in li:
                li.remove(a)
                break
        insort_left(dic[b], a)
    else:
        b = int(b)
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)


### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
### BUGGY CODE ###

import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
F = inl()
A.sort()
F.sort(reverse=True)


def solve():
    if N == 1:
        return max(A[0] - K, 0) * F[0]
    hp = []
    for i in range(N):
        heapq.heappush(hp, (-A[i] * F[i], F[i]))
    k = K
    while k > 0:
        t0, f0 = heapq.heappop(hp)
        t0 = -t0
        t1, f1 = hp[0]
        t1 = -t1
        if t0 == t1:
            m = 1
        else:
            assert t0 > t1
            m = ((t0 - t1) + f0 - 1) // f0
        m = min(m, k)
        k -= m
        t0 -= m * f0
        heapq.heappush(hp, (-t0, f0))

    t0, _ = hp[0]
    return -t0


print(solve())


### FIXED CODE ###

import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
F = inl()
A.sort()
F.sort(reverse=True)


def check(val):
    k = K
    for i in range(N):
        tmp = A[i] * F[i]
        if tmp <= val:
            continue
        dec = ((tmp - val) + F[i] - 1) // F[i]
        assert A[i] >= dec
        assert (A[i] - dec) * F[i] <= val
        k -= dec
        if k < 0:
            return False
    return True


def solve():
    ng, ok = -1, max([A[i] * F[i] for i in range(N)])
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok


print(solve())
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
z = sorted(list(map(int, input().split())))
import heapq
shou = 3 * 10**10 + 1
ans = []
for i in range(X-1, -1, -1):
  for j in range(Y-1, -1, -1):
    for k in range(Z-1, -1, -1):
      if (X-i)*(Y-j)*(Z-k) <= K:
        sub = x[i]+y[j]+z[k]
        ans.append(sub)
ans = list(map(lambda x: x*(-1), ans)) 
heapq.heapify(ans)
for i in range(K):
  print(heapq.heappop(ans)*(-1))

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
z = sorted(list(map(int, input().split())))


import heapq
ans = []
for i in range(X-1, -1, -1):
  for j in range(Y-1, -1, -1):
    for k in range(Z-1, -1, -1):
      if (X-i)*(Y-j)*(Z-k) <= K:
        sub = x[i]+y[j]+z[k]
        ans.append(sub)
      else:
        break
ans = list(map(lambda x: x*(-1), ans)) 
heapq.heapify(ans)
for i in range(K):
  print(heapq.heappop(ans)*(-1))
### BUGGY CODE ###

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
q = int(input())
cnt_A = dict(Counter(A))
for i in range(q):
    ans = 0
    b, c = map(int, input().split())
    if b in cnt_A and cnt_A[b] > 0:
        m = cnt_A[b]
        cnt_A[b] = 0
        if c not in cnt_A:
            cnt_A[c] = m
        else:
            cnt_A[c] += m
    ans = sum([k * v for k, v in cnt_A.items()])
    print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
q = int(input())
cnt_A = dict(Counter(A))
ans = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b in cnt_A and cnt_A[b] > 0:
        count = cnt_A[b]
        cnt_A[b] = 0
        if c not in cnt_A:
            cnt_A[c] = count
        else:
            cnt_A[c] += count
        ans += ((c - b) * count)
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
def sad(b):
    ret = 0
    for i in range(N):
        ret += abs(A[i]-b-i)
    return ret
L = -(10**10)
R = 10**10
tmp = sad(R)
while L+1<R:
    mid = (L+R)//2
    sm = sad(mid)
    sm1 = sad(mid-1)
    if sm1 < sm:
        R = mid
    elif sm1 == sm:
        ans = sm
        break
    else:
        L = mid
else:
    ans = sad(L)
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
def sad(b):
    ret = 0
    for i in range(N):
        ret += abs(A[i]-b-i)
    return ret
L = -(10**10)
R = 10**10
tmp = sad(R)
while L+1<R:
    mid = (L+R)//2
    sm = sad(mid)
    sm1 = sad(mid-1)
    if sm1 < sm:
        R = mid
    elif sm1 == sm:
        ans = sm
        break
    else:
        L = mid
else:
    ans = sad(L)
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):

      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx

            if 0<=ny<h and 0<=nx<w:
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='#':
                continue
              visited[ny][nx]=True #忘れがち
              # print(i,j,ny,nx)
              ans+=1
              for ddy,ddx in dd:
                nny=ny+ddy
                nnx=nx+ddx
                if 0<=nny<h and 0<=nnx<w:
                  if visited[nny][nnx]:
                    continue
                  if field[nny][nnx]=='.':
                    continue
                  q.append((nny,nnx))

      # print(ans)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if visited[i][j]:
        continue
      if field[i][j]!='#':
        continue
      q=collections.deque()
      q.append((i,j))
      b=0
      wh=0
      while q:
        y,x=q.popleft()
        if visited[y][x]:
          continue
        if field[y][x]=='#':
          b+=1
        else:
          wh+=1
        visited[y][x]=True
        for dy,dx in dd:
          ny=y+dy
          nx=x+dx
          if not (0<=ny<h and 0<=nx<w):
            continue
          if field[y][x]==field[ny][nx]:
            continue
          if visited[ny][nx]:
            continue
          q.append((ny,nx))
      ans+=b*wh
      # print(i,j,b,wh,ans)
  return ans

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

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele > ref:
            left.append(ele)
        elif ele < ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

color = []
color.append(a.pop(0))
clen = 1
for ai in a:
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            color = quick_sort(color)
            break
        else:
            if i+1 == clen:
                color.append(ai)
                clen += 1
                break
print(clen)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))
### BUGGY CODE ###

x,y=map(int, input().split())
while not (x ==0 and y==0) :
 if x < y : print(x, y)
 else : print(y, x)

### FIXED CODE ###

x, y = map(int, input().split())
while not( x == 0 and y == 0 ):
 if x < y : print(x, y)
 else : print(y, x)
 x, y = map(int, input().split())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
large_p = 10**9 + 7
a = []
kazu_memo = {}
def f(target_step):
    global kazu_memo
    #print(target_step)
    if target_step in a:
        return 0
    elif target_step < 0:
        return 0
    elif target_step == 0:
        return 1
    else:
        if kazu_memo[target_step] > 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = 0
            kazu_tmp += f(target_step - 1)
            kazu_tmp += f(target_step - 2)
            kazu_memo[target_step] = kazu_tmp % large_p
            return kazu_tmp % large_p

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    kazu_memo = {e: -1 for e in range(1, n + 1)}
    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
large_p = 10**9 + 7
a = []
kazu_memo = {}
kazu_tmp = 0
def f(target_step):
    global kazu_memo, kazu_tmp
    #print(target_step)
    if target_step < 0:
        return 0
    else:
        if kazu_memo[target_step] >= 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = (f(target_step - 1) + f(target_step - 2)) % large_p
            kazu_memo[target_step] = kazu_tmp
            return kazu_tmp

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    kazu_memo = {e: -1 for e in range(0, n + 1)}
    kazu_memo[0] = 1
    for _ in range(m):
        ta = int(input())
        kazu_memo[ta] = 0

    r = f(n)
    print(r % large_p)


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

def getlist():
	return map(int, input().split())

L = []

H, W = getlist()
for i in range(H):
	S = list(input())
	L.append(S)

ans1 = [[0 for i in range(W)] for j in range(H)]
ans2 = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
	val = 0
	l = []
	for j in range(W):
		if L[i][j] == "#":
			for k in l:
				ans1[i][k] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans1[i][k] = val

for i in range(W):
	val = 0
	l = []
	for j in range(H):
		if L[j][i] == "#":
			for k in l:
				ans2[k][i] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans2[k][i] = val


ans = -1
for i in range(H):
	for j in range(W):
		x = ans1[i][j] + ans2[i][j] - 1
		if x > ans:
			ans = x

print(ans)


### FIXED CODE ###

L = []

H, W = map(int, input().split())
for i in range(H):
	S = list(input())
	L.append(S)

ans1 = [[0 for i in range(W)] for j in range(H)]
ans2 = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
	val = 0
	l = []
	for j in range(W):
		if L[i][j] == "#":
			for k in l:
				ans1[i][k] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans1[i][k] = val

for i in range(W):
	val = 0
	l = []
	for j in range(H):
		if L[j][i] == "#":
			for k in l:
				ans2[k][i] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans2[k][i] = val


ans = -1
for i in range(H):
	for j in range(W):
		x = ans1[i][j] + ans2[i][j] - 1
		if x > ans:
			ans = x

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

N = int(input())
P_lis = list(map(int,input().split()))
 
count = 0
for i in range(N):
  for j in range(i):
    if P_lis[i] >= P_lis[j]:
      count += 1
      break
print(N - count)

### FIXED CODE ###

N = int(input())
P_lis = list(map(int, input().split()))
 
dummy = 2*10**5
answer = 0
 
for p in P_lis:
  if p <= dummy:
    answer += 1
    dummy = p
print(answer)
### BUGGY CODE ###

k=int(input())
s=7
ans=1
while True:
    if s%k==0:
        break
    else:
        s=s*10+7
        ans+=1
print(ans)

### FIXED CODE ###

k=int(input())
ans=1
judge=0
s=7%k
while ans<=k:
    if s==0:
        judge=1
        break
    else:
        s=s*10+7
        s%=k
        ans+=1
if judge==1:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(A):
    x = r[i]
    for j in range(B):
        y=g[j]
        if 2*x-y in b:
            k+=1
        if 2*y-x in b:
            k+=1
        if (x+y)/2 in b:
            k+=1

print(A*B*C-k)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

if __name__ == '__main__':
    n = int(input())
    print(fibonacci(n))

### FIXED CODE ###

def fibonacci(n):
    a, b = 1, 1
    for i in range(n-1):
        a, b = b, a+b

    return b

if __name__ == '__main__':
    n = int(input())
    print(fibonacci(n))
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    S = input().strip()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    sums = [0]
    d = 1
    for c in S[::-1]:
        sums.append((sums[-1] + int(c) * d) % 2019)
        mod_count[sums[-1]] += 1
        d *= 10

    print(sum([m * (m - 1) for m in mod_count]) // 2)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3


def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

    print(sum([m * (m - 1) for m in mod_count]) // 2)


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

import heapq

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort(reverse=True)
key = []
judge = [[False]*n for i in range(n)]

heapq.heappush(key, [-(a[0]+a[0]), 0, 0])
judge[0][0] = True

ans = 0
for i in range(m):
    p = heapq.heappop(key)
    p1, p2, p3 = p[0], p[1], p[2]
    ans += (-p1)
    if p2 < n-1 and judge[p2+1][p3] == False:
        heapq.heappush(key, [-(a[p2+1]+a[p3]), p2+1, p3])
        judge[p2+1][p3] = True
    if p3 < n-1 and judge[p2][p3+1] == False:
        heapq.heappush(key, [-(a[p2]+a[p3+1]), p2, p3+1])
        judge[p2][p3+1] = True

print(ans)

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    
    l, r = -1, 10**6
    while r-l > 1:
        k = (r+l)//2
        count = 0
        for i in range(n):
            count += n-bisect.bisect_left(a, k-a[i])
        
        if count > m:
            l = k
        else:
            r = k
    ans = 0
    count = 0
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] += b[i]+a[i]
    for i in range(n):
        index = bisect.bisect_left(a, r-a[i])
        ans += b[n]-b[index]+a[i]*(n-index)
        count += n-index
    
    if count < m:
        ans += (m-count)*l
    
    print(ans)
    
    
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = 0
while True:
  water = False
  for i in range(n):
    if h[i] > 0:
      h[i] -= 1
      water = True
    elif water:
      ans += 1
      water = False
  if water:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = 0
while True:
  water = False
  finish = True
  for i in range(n):
    if h[i] > 0:
      h[i] -= 1
      water = True
      finish = False
    elif water:
      ans += 1
      water = False
  if water:
    ans += 1
  if finish:
    break
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N,Q = map(int, input().split())

A = set() # 辺
for i in range(N-1):
    a,b = map(int, input().split())
    A.add((a,b))

P = [] # 足す操作
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))

V = [0]*N # 頂点のカウンター
for p in P:
    V[p[0]-1] += p[1] # P で指定されたノード・値で初期化

# 方針：親から子にカウンターの値を流していく。
# 根付き木なので、根から始めれば、ある辺（親から子）は一度処理するだけで良いはず。
parent = {1} # 親（最初は根）
while parent:
    children = set() # 子。根からの深さが同じの頂点（になるはず）
    for p in parent:
        tmp = set(a for a in A if p in a) # P を含む辺＝処理する辺
        child = set() # p を親に持つノードの index
        for a in tmp:
            child.add(a[1] if a[0] == p else a[0]) # 親と異なる値が子
        for c in child:
            V[c-1] += V[p-1] # 子のカウンターに、親のカウンターの値を足す
        A -= tmp # 処理済みの辺を除去
        children |= child # 子の集合の和を取る
    parent = children # 子の集合を次の親にする

print(*V)


### FIXED CODE ###

import sys
input=sys.stdin.readline

N,Q = map(int, input().split())

V = [0]*N

A = []
for i in range(N-1):
    a,b = map(int, input().split())
    A.append((a,b))
A.sort()
P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))
P.sort()

#print("V", V)
#print("A", A)
#print("P", P)

for p in P:
    V[p[0]-1] += p[1]
for a in A:
    V[a[1]-1] += V[a[0]-1]

print(*V)
### BUGGY CODE ###

N=int(input())
ans = 1
for i in range(1,N+1):
    ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

N=int(input())
ans = 1
for i in range(1,N+1):
    ans = ans*i % (10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]

adjm = [[float('inf')] * N for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjm[a][b] = 1
    adjm[b][a] = 1
    
dv = dijkstra(adjm, indices=v-1)
du = dijkstra(adjm, indices=u-1)
dOK = [i for i, j in zip(dv, du) if i>j]

print(int(max(dOK)-1))



### FIXED CODE ###

import sys, heapq
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N, u, v = map(int, input().split())



def dijkstra_heap(s,edge):
#始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

AB = [list(map(int, input().split())) for _ in range(N-1)]

adjl = [[] for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjl[a].append([1, b])
    adjl[b].append([1, a])

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))
### BUGGY CODE ###

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

s = [0]*(n+1)
for i in range(len(a)):
    s[i+1]=(s[i]+a[i])%m

ans= 0
for i in range(len(s)):
    ans += s[0:i].count(s[i])

print(ans)

### FIXED CODE ###

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

s = [0]*(n+1)
d = {0:1}
for i in range(len(a)):
    s[i+1]=(s[i]+a[i])%m
    if s[i+1] in d:
        d[s[i+1]] +=1
    else:
        d[s[i+1]] = 1

def calc(n):
    return int(n*(n-1)/2)

ans = 0
for i in d:
    ans += calc(d[i])

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

import heapq

def calc_minus(n):
    return n * (-1)

N, M = map(int, input().split())
values = list(map(int, input().split()))
tmp = 0

values_minus = []
for val1 in values:
    values_minus.append(calc_minus(val1))

for i in range(M):
    heapq.heapify(values_minus)
    tmp = heapq.heappop(values_minus)
    tmp_push = ((tmp * (-1)) // 2) * (-1)
    heapq.heappush(values_minus, tmp_push)

values_plus = []
for val2 in values_minus:
    values_plus.append(calc_minus(val2))

result = 0
for val3 in values_plus:
    result += val3

print(result)

### FIXED CODE ###

import heapq

def calc_minus(n):
    return n * (-1)

N, M = map(int, input().split())
values = list(map(int, input().split()))
tmp = 0

values_minus = []
for val1 in values:
    values_minus.append(calc_minus(val1))

heapq.heapify(values_minus)

for i in range(M):
    tmp = heapq.heappop(values_minus)
    tmp_push = ((tmp * (-1)) // 2) * (-1)
    heapq.heappush(values_minus, tmp_push)

values_plus = []
for val2 in values_minus:
    values_plus.append(calc_minus(val2))

result = 0
for val3 in values_plus:
    result += val3

print(result)
### BUGGY CODE ###

N = map(int, input())
data = list(map(int, input().split()))
sum = 0

#L_list = [3 4 2 1]なら[3,4,2],[3,4,1],[3,2,1],[4,2,1]の4通り
def listExcludedIndices(data, indices=[]):
  return [x for i, x in enumerate(data) if i not in indices]

L_combinations = []

for i in range(len(data)):
  for j in range(i, len(data) - 1):
    for k in range(j, len(data) - 2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      L_combinations.append([data[i], jData[j], kData[k]])

# print(L_combinations)
for L_combination in L_combinations:
    if L_combination[0] < L_combination[1] + L_combination[2] and L_combination[1] < L_combination[2] + L_combination[0] and L_combination[2] < L_combination[0] + L_combination[1]:
        sum += 1

print(sum)

### FIXED CODE ###

N = int(input())
L_list = list(map(int, input().split()))
sum = 0

L_list.sort()

from bisect import bisect_left

for i in range(N):
    for j in range(i+1, N):
        t = L_list[i]+L_list[j]
        idx = bisect_left(L_list, t)
        sum += max(0, idx-(j+1))
        
print(sum)