Harryxun/stf_run huggingface dataset:
from bisect import bisect_right

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_right(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')


### FIXED CODE ###

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_left(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')
# print('input >>')
S = input()
Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

is_reverse = False

for q in queries:
    ql = list(q.split())
    if len(ql) == 1:
        is_reverse = not is_reverse
    else:
        if ql[1] == '1': # 先頭に加える
            if not is_reverse:
                S = ql[2] + S
            else:
                S = S + ql[2]
        else: # 末尾に加える
            if not is_reverse:
                S = S + ql[2]

            else:
                S = ql[2] + S
    print(S, is_reverse)

# print('-----output-----')
if not is_reverse:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

# print('input >>')
S = deque(input())
Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

is_reverse = False

for q in queries:
    ql = list(q.split())
    if len(ql) == 1:
        is_reverse = not is_reverse
    else:
        if ql[1] == '1': # 先頭に加える
            if not is_reverse:
                S.appendleft(ql[2])
            else:
                S.append(ql[2])
        else: # 末尾に加える
            if not is_reverse:
                S.append(ql[2])
            else:
                S.appendleft(ql[2])

# print('-----output-----')
if not is_reverse:
    print(''.join(list(S)))
else:
    print(''.join(list(S)[::-1]))
import heapq
N,M,S,T = map(int,input().split())

adj=[[] for _ in range(N)]

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].add((b-1,c,d))
    adj[b-1].add((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,0)


while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen<D_S[next_node]:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_S[next_node]*N+next_node)

Q=[]
heapq.heappush(Q,0)

while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen<D_T[next_node]:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_T[next_node]*N+next_node)


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


for a in reversed(ans):
    print(10**15-a)


### FIXED CODE ###

import heapq
N,M,S,T = map(int,input().split())

adj=[[] for _ in range(N)]

for _ in range(M):
    a,b,c,d = map(int,input().split())
    adj[a-1].append((b-1,c,d))
    adj[b-1].append((a-1,c,d))


D_S=[float("inf")]*N
D_T=[float("inf")]*N

D_S[S-1]=0
D_T[T-1]=0

Q=[]
heapq.heappush(Q,S-1)


while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    for nex in adj[node]:
        (next_node,yen,_) = nex
        if dist_to_node+yen<D_S[next_node]:
            D_S[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_S[next_node]*N+next_node)

Q=[]
heapq.heappush(Q,T-1)

while Q:
    v = heapq.heappop(Q)
    dist_to_node,node=v//N,v%N
    if D_T[node]< dist_to_node:
        continue
    for nex in adj[node]:
        (next_node,_,yen) = nex
        if dist_to_node+yen<D_T[next_node]:
            D_T[next_node] = dist_to_node+yen
            heapq.heappush(Q,D_T[next_node]*N+next_node)


tmp_min=float("inf")
ans=[]
for i in reversed(range(N)):
    tmp_min = min(tmp_min,D_S[i]+D_T[i])
    ans.append(tmp_min)


for a in reversed(ans):
    print(10**15-a)
N, K = map(int, input().split())
S = input()

L = []
R = []
before = '1'
cnt_zero = 0
cnt_one = 0
len_l = 0
len_r = 0
for i in range(N):
    if before == '0' and S[i] == '0':
        cnt_zero += 1
    elif before == '0' and S[i] == '1':
        before = '1'
        L.append(cnt_zero)
        len_l += 1
        cnt_zero = 0
    elif before == '1' and S[i] == '0':
        before == '0'
        R.append(cnt_one)
        cnt_zero += 1
        cnt_one = 0
	else:
    	cnt_one += 1
      
if cnt_zero != 0:
    L.append(cnt_zero)
    len_l += 1

if cnt_one != 0:
	R.append(cnt_one)
	len_r = 0
ans = 0
sum_one = 0
if S[0] == '0'
	sum_one = sum(L[:K]) + sum(R[:K])
else:
	sum_one = sum(L[:K]) + sum(R[:K+1])

ans = sum_one

for i in range(len_l)[1:]:
  	if i + K > len_r:
		break
	if S[0] == '0' and i == 1:
      sum_one += (L[K] + R[K] - L[0])
    else:
      sum_one += (L[K+i-1] + R[K+i] - L[i-1] - R[i-1])
	ans = max(ans, sum_one)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()

before = S[0]
cnt = 0
same_nums = []
if S[0] == '0':
  same_nums.append(0)
for i in range(N):
  if S[i] == before:
    cnt += 1
  else:
    same_nums.append(cnt)
    before = S[i]
    cnt = 1
same_nums.append(cnt)
if S[-1] == '0':
  same_nums.append(0)
  
sum_nums = sum(same_nums[:2*K+1])
ans = sum_nums
for i in range(0, len(same_nums)-2*K, 2):
  sum_nums = sum_nums - sum(same_nums[i:i+2]) + sum(same_nums[i+2*K+1:i+2*K+3])
  ans = max(ans, sum_nums)
print(ans)
l = [int(i) for i in input().split()]
if min(abs(l[0]-l[1]), abs(l[1]-l[2]), abs(l[0]-abs[2])) <= l[3]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

l = [int(i) for i in input().split()]
print("Yes" if ((abs(l[0] - l[1]) <= l[3]) & (abs(l[1] - l[2]) <= l[3])) or (abs(l[0] - l[2]) <= l[3]) else "No")
data = [int(i) for i in input().split()]

data.sort()
print("{0} {1} {2}".format(data[0],data[1],data[2])

### FIXED CODE ###

data = [int(i) for i in input().split()]

data.sort()
print("{0} {1} {2}".format(data[0],data[1],data[2]))
N = int(input())
H = [int(x) for x in input().split()]
C = 0
for i in range(N-1):
  if H[i] <= H[i+1]+1:
    C += 1
if (C == N-1 OR C == N):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
C = 0
for i in range(N-1):
  if H[i] > H[i+1]:
    H[i+1]=H[i+1]+1
  if H[i] <= H[i+1]:
    C += 1
if C == N-1:
  print("Yes")
else:
  print("No")
import bisect
point=0
N=int(input())
A=list(map(int,input().split())).sort()
B=list(map(int,input().split())).sort()
C=list(map(int,input().split())).sort()
for i in range(N):
  m=bisect.bisect_left(A,B[i])
  n=bisect.bisect_left(C,B[i])
  point+=m*n
print(point)
  

### FIXED CODE ###

import bisect
point=0
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
for i in range(N):
  m=bisect.bisect_left(A,B[i])
  n=bisect.bisect_right(C,B[i])
  point+=m*(N-n)
print(point)
def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = int(input())

table = prime_factor(N)
table.sort()

if len(table)%2 == 0:
    tmp1 = 1
    tmp2 = 1
    for i in range(len(table)//2):
        tmp1 *= table[i]
        tmp2 *= table[i+len(table)//2]

    print(tmp1 + tmp2 - 2)

else:
    tmp1 = 1
    tmp2 = 1
    for i in range(len(table)//2):
        tmp1 *= table[i]
        tmp2 *= table[i+len(table)//2+i+1]

    tmp1 *= table[len(table)//2]
    print(tmp1 + tmp2 - 2)



### FIXED CODE ###

import math

N = int(input())

res = 10 ** 15
for i in range(1, int(math.sqrt(N))+1):
    if N%i == 0:
        res = min(res, N // i + i)

print(res-2)
n=int(input())
ans=0
for i in range(n):
    if len(list(n))%2==1:
        ans=ans+1
        
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
for i in range(n+1):
    if len(str(i))%2==1:
        ans=ans+1
        
print(ans-1)
import sys
N,M = map(int,input().split())
if M == 0:
	print('0 0')
	sys.exit()


p = [0]*M#問題の番号
s = [0]*M#結果 AC,WA

for i in range(M):
	p[i],s[i] = input().split()

cor_count = 0
pen_count = 0
AC_list = []

for i in range(M):
	if not p[i] in AC_list:
		if s[i] == 'AC':
			AC_list.append(p[i])
		else:
			pen_count += 1

#print(AC_list)
cor_count = len(set(AC_list))
if M != 0:
	print(cor_count,pen_count)




### FIXED CODE ###


C = input()



print(chr(ord(C)+1))
N = int(input())
A = sorted(list(map(int, input().split())))
Q = int(input())
M = list(map(int, input().split()))

def solve(idx, target):
    if target == 0:
        return True
    elif target < 0:
        return False
    if idx >= N:
        return False
    if solve(idx+1, target) or solve(idx+1, target-A[idx]):
        return True
    return False


for target in M:
    if solve(0, target):
        print("yes")
    else:
        print("no")


### FIXED CODE ###

def solve(dp, a, i, m):
  if m in dp[i]:
    return dp[i][m]

  if m == 0:
    dp[i][m] = True
  elif i >= len(a):
    dp[i][m] = False
  elif solve(dp, a, i+1, m):
    dp[i][m] = True
  elif solve(dp, a, i+1, m-a[i]):
    dp[i][m] = True
  else:
    dp[i][m] = False

  return dp[i][m]

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
M = list(map(int, input().split()))

dp = {}
for i in range(N+1):
  dp[i] = {}

for m in M:
  if solve(dp, A, 0, m):
    print('yes')
  else:
    print('no')
, b = map(int, input().split())

if a>=13:
    print(b)
elif a>=6:
    print(int(b/2))
else:
    print(0)

### FIXED CODE ###

a, b = map(int, input().split())

if a>=13:
    print(b)
elif a>=6:
    print(int(b/2))
else:
    print(0)
s = input()
t = input()
count = 0
for i in range(26):
    start[i] = -1
    goal[i] = -1
for i in range(0,len(s)):
    a = s[i]-'a'
    b = t[i]-'a'
    if start[a] != -1 or goal[b] != -1:
        if start[a] != b or goal[b] != a:
            count = 1
            break
    else:
        start[a] = b
        goal[b] = a
if count == 1:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

s = input()
t = input()
start = [-1]*30
goal = [-1]*30
count = 0
for i in range(0,len(s)):
    a = ord(s[i])-ord("a")
    b = ord(t[i])-ord("a")
    if start[a] != -1 or goal[b] != -1:
        if start[a] != b or goal[b] != a:
            count = 1
            break
    else:
        start[a] = b
        goal[b] = a
if count == 1:
    print("No")
elif count == 0:
    print("Yes")
n = int(input())
f = [int(input().replace(' ',''),2) for i in range(n)]
p = [list(map(int,input().split())) for i in range(n)]
prof = - 10 ** 10
for i in range(1,1 <<10):
	prof1 = 0
	for j,time in enumerate(f):
		same = bin(i & time).count(1)
		prof1 += p[j][same]
	prof = max(prof,prof1)
print(prof)


### FIXED CODE ###

N=int(input())
F=[int(input().replace(' ',''),2) for _ in range(N)]
P=[list(map(int,input().split())) for _ in range(N)]

ans=-10**10
for i in range(1,1<<10):
    prof=0
    for j,f in enumerate(F):
        prof+=P[j][bin(i&f).count("1")]
    ans=max(ans,prof)

print(ans)
for e in iter(input,'0'):
 a={tuple(map(int,input().split())) for _ in range(int(e))}
 s,t=a[0]
 b={tuple(map(int,input().split())) for _ in range(int(input()))}
 for x,y in b:
  flag = True
  for u,v in a[1:]:
   if(x+u-s,y+v-t)not in b:
    flag = False
    break
  if flag == True:
   print(x - s, y - t)
   break


### FIXED CODE ###

for e in iter(input,'0'):
 a=[[*map(int,input().split())]for _ in[0]*int(e)]
 s,t=min(a)
 b={tuple(map(int,input().split()))for _ in[0]*int(input())}
 m=max(b)[0]-max(a)[0]+s
 for x,y in b:
  if x<=m:
   for u,v in a:
    if(x+u-s,y+v-t)not in b:break
   else:print(x-s,y-t);break
kekka = ""
num = []
hantei = "OK"
INF = input().split()
gyosu = int(INF[1])
keta = int(INF[0])
out = []
for l in range(keta):
  out.append(0)


for i in range(gyosu):
  num.append([int(j) for j in input().split()])

for j in range(gyosu - 1):
  for k in range(gyosu - 1):
    if num[j][0] == num[k + 1][0]:
      if num[j][1] != num[k + 1][1]:
        hantei = "NG"
          
  if num[j][0] == keta:
    if num[j][1] == 0:
      hantei ="NG"








### FIXED CODE ###

import math

N = int(input())
P = math.floor(N / 2)
P = P + N % 2
print(P)
A,B,K = map(int,input().split())
if A > 100000000000 or B > 100000000000 or K > 100000000000:
    A = 0
    B = 0
else:
    C = max(0,A-K)
    B = max(0,(A+ B) - K)
print(C,B)

### FIXED CODE ###

a, b, k = map(int, input().split())
print(max(0, a - k), max(0, b - max(0, k - a)))
A,B,H,M = map(float, input().split())

import math

degreeA = float((H * 60 + M) / 2)
degreeB = float(M * 6)

#if degreeA == degreeB:
#    print(abs(A - B))
else:
    degreeAB = abs(degreeA - degreeB)
    if degreeAB == 180:
        print(A + B)
    elif degreeAB > 180:
        degreeAB = 360 - degreeAB
    C = float(A ** 2 + B ** 2 - 2 * A * B * float(math.cos(float(degreeAB * math.pi / 180))))
    print(math.sqrt(C))

### FIXED CODE ###

A,B,H,M = map(float, input().split())

import math

degreeA = float((H * 60 + M) / 2)
degreeB = float(M * 6)

degreeAB = abs(degreeA - degreeB)

if degreeAB > 180:
    degreeAB = 360 - degreeAB
C = float(A ** 2 + B ** 2 - 2 * A * B * float(math.cos(float(degreeAB * math.pi / 180))))
print(math.sqrt(C))
h,w,k=map(int,input().split())
b=[]
v=[[0]*w for _ in range(h)]
sh=0
sw=0
for i in range(h):
    s=list(input())
    b.append(s)
    
    if 'S' in s:
        sh=i
        sw=s.index('S')
#ans=10**18
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(y,x):
    ans=10**18
    c=0
    q=[(y,x)]
    v[y][x]=1
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if v[i+di][j+dj]!=1 and b[i+di][j+dj]!='#' and 0<=i+di<h and 0<=j+dj<w:
                    p.append((i+di,j+dj))
                    v[i+di][j+dj]=1
                    ans=min(ans,i+di,j+dj,h-1-i-di,w-1-j-dj)
        q=p
    return ans
ans=bfs(sh,sw)
print(1+(ans+k-1)//k)
#print(b,sh,sw)
#print(v)


### FIXED CODE ###

h,w,k=map(int,input().split())
b=[]
v=[[0]*w for _ in range(h)]
sh=0
sw=0
for i in range(h):
    s=list(input())
    b.append(s)
    
    if 'S' in s:
        sh=i
        sw=s.index('S')
#ans=10**18
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(y,x):
    ans=10**18
    c=0
    q=[(y,x)]
    v[y][x]=1
    ans=min(y,x,h-1-y,w-1-x)
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if 0<=i+di<h and 0<=j+dj<w and v[i+di][j+dj]!=1 and b[i+di][j+dj]!='#':
                    p.append((i+di,j+dj))
                    v[i+di][j+dj]=1
                    ans=min(ans,i+di,j+dj,h-1-i-di,w-1-j-dj)
        q=p
    return ans
ans=bfs(sh,sw)
print(1+(ans+k-1)//k)
P, Q, R = int(input()), int(input()), int(input())
print(min(P+Q, Q+R, R+P))

### FIXED CODE ###

P, Q, R =map(int ,input().split())
print(min(P+Q, Q+R, R+P))
import math
from decimal import *

getcontext().prec = 20      # デフォルト28桁のところを20桁にする
m = int(Decimal(n).sqrt())

a, b, c = map(int, input().split())
#sqa = math.floor(math.sqrt(a)*10**(1000))/10**(1000)
#sqb = math.floor(math.sqrt(b)*10**(1000))/10**(1000)
#sqc = math.floor(math.sqrt(c)*10**(1000))/10**(1000)
sqa = int(Decimal(a).sqrt())
sqb = int(Decimal(b).sqrt())
sqc = int(Decimal(c).sqrt())
 
#sqa = float("{:.100f}".format(math.sqrt(a)))
#sqb = float("{:.100f}".format(math.sqrt(b)))
#sqc = float("{:.100f}".format(math.sqrt(c)))
 
#s = c - (a + b)
#t = 2 * sqa * sqb
if sqa + sqb < sqc:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import math

a, b, c = map(int, input().split())


if c-a-b > 0 and 4*a*b < (c-a-b)**2:
  print("Yes")
else:
  print("No")
S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
cnt = 0
last = []
head = []
for i in range(Qlen):
    if int(Query[i][0]) == 1:
        cnt +=1
    else:
        if int(Query[i][1]) == 1: #頭につける
            if cnt % 2 != 0:   #逆さ
                last = last + [Query[i][2]]
            else:
                head = [Query[i][2]] + head
        else: #けつにつける
            if cnt % 2 != 0:
                head = [Query[i][2]] + head
            else:
                last = last + [Query[i][2]]
if cnt % 2 == 0:
    print(head + "".join(Slist) + last)
else:
    Slist = Slist[::-1]
    head = head[::-1]
    last = last[::-1]
    print("".join(last + Slist + head))
    
# head Slist last

### FIXED CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
reverse = False
back = []
head = []

for idx, value in enumerate(Query):
    if value[0] == "1":
        reverse ^= True
        head, back = back, head
    else:
        if value[1] == "1":
            head += [value[2]]
        else:
            back += [value[2]]

if reverse == False:
    head.reverse()
    print("".join(head + Slist + back))
else:
    head.reverse()
    print("".join(head + Slist[::-1] + back))
import numpy as np

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

suma=np.sum(A)
remain=N-suma

if remain>=0:
	print(remain)
else:
	print(-1)

### FIXED CODE ###

import numpy as np

s=int(input())

R=2*s*np.pi
print(R)
N,P = map(int,input().split())
ans=1
i=2
if N==1:
  print(P)
  exit()
if N>=40 or P==1:
  print(1)
  exit()
  
while i<=(P**(N/1)):
  while P%(i**N) == 0:
    ans *= i
    P = P//(i**N)
  if i==2:
    i+=1
  else:
    i+=2
print(ans)

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
r = 10000
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]: prime.append(i)

def solve(n,k,i):
	if k == 0: return 1 if n == 0 else 0
	if n-k*prime[i] < 0 : return 0
	return solve(n-prime[i],k-1,i+1) + solve(n,k,i+1)

while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	ans = 0
	for i in range(n):
		if k*prime[i] > n: break
		ans += solve(n-prime[i],k-1,i+1)
	print ans

### FIXED CODE ###

r = 1121
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]: prime.append(i)

dp = [[0]*r for i in range(15)]
dp[0][0] = 1
for i in range(len(prime)):
	for k in range(min(i+1,14),0,-1):
		for j in range(prime[i],r):
			dp[k][j] += dp[k-1][j-prime[i]]

while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	print dp[k][n]
A,B,C = [int(i) for i in input().split()]
list = [A,B,C]

for i in list:
  if i == 5:
    go += 1
  if i == 7:
    nana += 1

if go == 2 and nana == 1:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

A,B,C = [int(i) for i in input().split()]
list = [A,B,C]
go = 0
nana = 0
for i in list:
  if i == 5:
    go += 1
  if i == 7:
    nana += 1

if go == 2 and nana == 1:
  print("YES")
else:
  print("NO")
a, b ＝ map(int, input().split())
tower = []
tmp = 0

for i in range(1, 1000):
    tmp += i
    tower.append(tmp)
    
count = b - a

print(tower[count - 1] - b)


### FIXED CODE ###

a, b = map(int, input().split())
tower = []
tmp = 0

for i in range(1, 1000):
    tmp += i
    tower.append(tmp)
    
count = b - a

print(tower[count - 1] - b)
N,S = open(0).read().split()
N=int(N)
S=list(S)

def calc():
    group = [] if S[0] == '.' else [0]
    n = 0
    mark = S[0]
    for s in S:
        if s == mark:
            n += 1
        else:
            mark = s
            group.append(n)
            n = 1
    if n > 0:
        group.append(n)
    if S[-1] == '#':
        group.pop()

    cnt = 0
    i = 1
    j = len(group) - 1
    while i <= j:
        l = group[i]
        r = group[j]
        if l < r:
            cnt += l
            i += 2
        else:
            cnt += r
            j -= 2
    return cnt

all_w = sum([1 if s == '#' else 0 for s in S])
all_b = sum([1 if s == '.' else 0 for s in S])
lwrb = calc()
print(min(all_w, all_b, lwrb)

### FIXED CODE ###

N,S = open(0).read().split()
N=int(N)
S=[s == "." for s in list(S)]

w = sum([1 if s else 0 for s in S])
b = 0
m = w + b
for s in S:
    if s:
        w -= 1
    else:
        b += 1
    m = min(m, w + b)
print(m)
import sys
from collections import deque
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    LD = [[] for _ in range(n)]
    for _ in range(n):
        t, d = map(int, input().split())
        LD[t - 1].append([d, 0] if len(LD[t - 1]) else [d, 1])

    ALL = []
    for ld in LD:
        ALL.extend(ld)
    ALL.sort(reverse=True)
    que = deque(ALL)

    x = y = 0
    zero, one = [], []
    for _ in range(k):
        d, ex = que.popleft()
        x += d
        y += ex
        heappush(zero, d) if ex == 0 else heappush(one, d)

    res = x + y ** 2
    while que:
        d, ex = que.popleft()
        if ex:
            if zero:
                x += d - heappop(zero)
                y += 1
                res = max(res, x + y ** 2)
            else:
                x += d - heappop(one)
                res = max(res, x + y ** 2)
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
from collections import deque
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    TD = [list(map(int, input().split())) for _ in range(n)]
    TD.sort(key=lambda z: -z[1])
    TD_new = [[] for _ in range(n)]
    for t, d in TD:
        TD_new[t - 1].append([d, 0] if len(TD_new[t - 1]) else [d, 1])

    ALL = []
    for td in TD_new:
        ALL.extend(td)
    ALL.sort(reverse=True)
    que = deque(ALL)

    x = y = 0
    zero = []
    for _ in range(k):
        d, ex = que.popleft()
        x += d
        y += ex
        if ex == 0:
            heappush(zero, d)

    res = x + y ** 2
    while que:
        d, ex = que.popleft()
        if ex:
            if zero:
                x += d - heappop(zero)
                y += 1
                res = max(res, x + y ** 2)
            else:
                break

    print(res)


if __name__ == '__main__':
    resolve()
A,B=map(int,input().split())
pritn(6-A-B)

### FIXED CODE ###

A = int(input())
B = int(input())
print(6-A-B)
n = str(input())
ans = 0
for i in range(len(n)): 
	ans = (ans + int(ord(i) - ord('0'))) % 9
if ans: print ("No")
else: print("Yes")



### FIXED CODE ###

n = str(input())
ans = 0
for i in range(len(n)):
	ans = (ans + ord(n[i]) - ord('0')) % 9
if ans: print("No")
else: print("Yes")
import re
print("Yes")　if re.fullmatch(r'(hi)+',input())　else　print("No")

### FIXED CODE ###

import re
s=input()
if re.fullmatch(r'(hi)+',s):
    print("Yes")
else:
    print("No")
n,m = map(int,input().split())
height = list(map(int,input().split()))
lst = [0]*n
for j in range(m):
    x,y = map(int,input().split())
    if height[x-1] >= height[y-1]:
      lst[y-1] = 1
    if height[x-1] <= height[y-1]:
      lst[x-1] = 1
print(lst.count(0))

### FIXED CODE ###

s = input()
if s == "ABC":
  print("ARC")
else:
  print("ABC")