Harryxun/stf_run huggingface dataset:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n0 = int(input())
    c0 = list(map(int, readline().split()))
    c0.sort(reverse=True)

    ans = 0
    mul = pow(2, n0 - 1, MOD)
    add = pow(2, n0 - 2, MOD)

    for i, cc in enumerate(c0, 1):
        ans += cc * mul
        ans %= MOD
        mul += add

    ans *= pow(2, n0, MOD)
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n0 = int(input())
    c0 = list(map(int, readline().split()))
    c0.sort(reverse=True)

    ans = 0
    mul = pow(2, n0 - 1, MOD)
    add = pow(2, max(0, n0 - 2), MOD)

    for i, cc in enumerate(c0, 1):
        ans += cc * mul
        ans %= MOD
        mul += add
        mul %= MOD

    ans *= pow(2, n0, MOD)
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
from collections import deque

A, B, K = input().split()

A = int(A)
B = int(B)
K = int(K)

s = [i for i in range(A, B+1)]
value = deque()

for i in range(K):
    if s[i] not in value:
        value.append(s[i])

for i in range(len(s)-K, len(s)):
    if s[i] not in value:
        value.append(s[i])

for i in range(len(value)):
    print(value[i])

### FIXED CODE ###

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

value = []

if B - A < K or B <= K:
    value.extend([i for i in range(A, B+1)])
    
else:
    value.extend([i for i in range(A, A+K)])
    value.extend([i for i in range(B-K+1, B+1)])    

num = list(set(value))
num.sort()

for i in range(len(num)):
    print(num[i])
from collections import Counter
N,K=map(int,input().split())
N=list(map(int,input().split()))
A=Counter(N)
C=list(A.values())
C=C.sort(reverse=True)
print(C)
if len(C)<=K:
    print(0)
else:
    ans=sum(C[-(len(C)-K):])
    print(ans)

### FIXED CODE ###

from collections import Counter
N,K=map(int,input().split())
N=list(map(int,input().split()))
A=Counter(N)
C=list(A.values())
C.sort(reverse=True)
if len(C)<=K:
    print(0)
else:
    ans=sum(C[-(len(C)-K):])
    print(ans)
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
TA=10**10
num=0
for i in range(n):
    if TA>abs(a-(t-h[i]*0.006))>0:
        num=i+1
        TA=abs(a-(t-h[i]*0.006))
 
print(num)

### FIXED CODE ###

x,y=map(int,input().split())
print(int(x+y/2))
S = str(input())
K = int(input())

if len(S) <= K:
  print(S)
else:
  print(S[0:K],"...")

### FIXED CODE ###

K = int(input())
S = input()

if len(S) <= K:
  print(S)
else:
  print(S[0:K]+"...")
x=input()
if x>=30:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x=int(input())
if x>=30:
  print("Yes")
else:
  print("No")
#!/usr/bin/env python

N = int(input())

print "ABD" if N >= 1000 else "ABC"


### FIXED CODE ###

#!/usr/bin/env python

N = int(input())

print "ABD" if N >= 1000 else "ABC"
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B=map(int,input().split())
if (B-A)%2==0:5 2 
    print((B-A)//2)
else:
    print(min(B-1,N-A))

### FIXED CODE ###

N,A,B=map(int,input().split())
if (B-A)%2==0:
    print((B-A)//2)
else:
    print(min((B+A-1)//2,((2*N-B+1-A)//2)))
x, t = list(map(int, input().split()))

if x - t <:
	print(0)
else:
	print(x - t)

### FIXED CODE ###

x, t = list(map(int, input().split()))

if x - t < 0:
	print(0)
else:
	print(x - t)
from math import gcd
A, B = map(int,input().split())
n = (A * B) // gcd(A, B)
print(n)

### FIXED CODE ###

from fractions import gcd
A, B = map(int,input().split())
n = (A * B) // gcd(A, B)
print(n)
H, W = map(int, input().split())
if H==1 or W==1:
    print("1")
elif W%2==0:
    result = (W/2)*H
else:
    if H%2==0:
        result=W*(H/2)
    else :
        result=W*(H-1)/2+(W+1)/2
print(str(round(result)))

### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(list[K-1])
a = int(input())
b = input.split()
b = [int(elem) for elem in b]
sumation = 0
for i, elem in enumerate(b):
	for j, elem2 in enumerate(b[i:]):
      sumation += elem * elem2
print('{}'.format(sumation)

### FIXED CODE ###

a = int(input())
b = input().split()
b = [int(elem) for elem in b]
total = 0
for i in range(len(b)-1):
  for j in range(i+1, len(b)):
    total += b[i] * b[j]
print('{}'.format(total))
n=input()
a=list(map(int,input().split()))
s=list()
for i in range(n):
  s.append(a.index(i))
print(' '.join(s))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=[0]*n
for i,m in enumerate(a):
  s[m-1]=i+1
b=map(str,s)
print(' '.join(b))
N=input().split
if N[0] != N[1] and N[0] != N[2] and N[1] != N[2]:
  print("No")
elif N[0] == N[1] and N[0] == N[2] and N[1] == N[2]:
  print("No") 
else:
  print("Yes")

### FIXED CODE ###

N=input().split()
if N[0] != N[1] and N[0] != N[2] and N[1] != N[2]:
  print("No")
elif N[0] == N[1] and N[0] == N[2] and N[1] == N[2]:
  print("No") 
else:
  print("Yes")
a,b,c=map(str,input().split())

if (2*b-a-c)==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

if (2*b-a-c)==0:
    print("YES")
else:
    print("NO")
n=int(input())
A=sorted(list(map(int,input().split())))
L={}
if n==1:
        print(1)
elif n==2:
    if abs(A[0]-A[1])==1:
        print(2)
    else:
        print(1)
else:
    for i in A:
        if i not in L:
            L[i]=1
        else:
            L[i]+=1
    print(L)
    ans=[]
    for j in range(A[0],A[-1]+1):
        if (j in L) and (j-1 in L) and (j+1 in L):
            ans.append(L[j]+L[j+1]+L[j-1])
        elif (j in L) and (j-1 in L):
            ans.append(L[j-1]+L[j])
        elif (j in L) and (j+1 in L):
            ans.append(L[j+1]+L[j])
        elif (j-1 in L) and (j+1 in L):
            ans.append(L[j+1]+L[j-1])
        elif (j in L):
            ans.append(L[j])
print(max(ans))

### FIXED CODE ###

n=int(input())
A=sorted(list(map(int,input().split())))
L={}
if n==1:
        print(1)
elif n==2:
    if abs(A[0]-A[1])==1:
        print(2)
    else:
        print(1)
else:
    for i in A:
        if i not in L:
            L[i]=1
        else:
            L[i]+=1
    ans=[]
    for j in range(A[0],A[-1]+1):
        if (j in L) and (j-1 in L) and (j+1 in L):
            ans.append(L[j]+L[j+1]+L[j-1])
        elif (j in L) and (j-1 in L):
            ans.append(L[j-1]+L[j])
        elif (j in L) and (j+1 in L):
            ans.append(L[j+1]+L[j])
        elif (j-1 in L) and (j+1 in L):
            ans.append(L[j+1]+L[j-1])
        elif (j in L):
            ans.append(L[j])
    print(max(ans))
S = input()
K = int(input())

L = []
temp = S[0]
c = 1
for i in range(1, len(S)):
    if S[i] == temp:
        c += 1
    else:
        L.append(c)
        c = 1
        temp = S[i]
    if i == len(S)-1:
        L.append(c)
        
ans = 0
if S[0] != S[-1]:
    for i in range(len(L)):
        ans += (L[i]//2)
    ans *= K
else:
    if len(L) == 1:
        ans = K*L[0]//2
    else:
        for i in range(1, len(L)-1):
            ans += (L[i]//2)
        ans *= K
        ans += (L[0]+L[-1])//2*K
        
print(ans)

### FIXED CODE ###

S = input()
K = int(input())

L = []
temp = S[0]
c = 1
for i in range(1, len(S)):
    if S[i] == temp:
        c += 1
    else:
        L.append(c)
        c = 1
        temp = S[i]
    if i == len(S)-1:
        L.append(c)
        
ans = 0

if S[0] != S[-1]:
    for i in range(len(L)):
        ans += (L[i]//2)
    ans *= K
else:
    if len(L) == 1:
        ans += K*L[0]//2
    elif len(L) == 0:
        ans += K//2
    else:
        for i in range(1, len(L)-1):
            ans += (L[i]//2)
        ans *= K
        ans += L[0]//2
        ans += L[-1]//2
        ans += (L[0]+L[-1])//2*(K-1)
        
print(ans)
a=float(input())
b=float(input())
print(a*b," ",2*a+2*b)


### FIXED CODE ###

a=input().split()
b=[int(i) for i in a]
print(b[0]*b[1],2*(b[0]+b[1]))
def gcd(a,b):
    while a%b:
        a,b=b,a%b
    return b

def lcm(a,b):
    return a*b/gcd(a,b)

while 1:
    a,b=map(int, raw_input().split())
print gcd(a,b),lcm(a,b)

### FIXED CODE ###

import sys

def gcd(a,b):
    while a%b:
        a,b=b,a%b
    return b

def lcm(a,b):
    return a*b/gcd(a,b)

for ab in sys.stdin:
    a,b=map(int, ab.split())
    a,b=max(a,b),min(a,b)
    print gcd(a,b),lcm(a,b)
def g(l):
    if not l:
        return 0, 0
    m,s = max(l), sum(l)
    if 2*m > s:
        return 2*m - s, (s-m)
    return s % 2, s//2

def f(v, vs):
    ks = []
    r = 0
    rkoma = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, k2, koma = f(u, vs)
        ks.append(k1)
        rkoma += koma
        r += k2
    r1, r2 = g(ks)
    # r1 深さの和、r2 操作の回数
    rkoma += km[v]
#    print(v, r1 + rkoma, r + r2, rkoma)
    return r1 + rkoma, r + r2, rkoma

N = int(input())
km = [0] + [int(i) for i in input()]
d = [set() for _ in range(N+1)]

for _ in range(N-1):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)

r = -1
for i in range(N):
    a, b, c = f(i+1, {i+1})
    if a == c:
        r = b
print(r)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def f(v, vs):
    kminmax = 0
    r = 0
    rkoma = 0
    fff = 0
    ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax = k1
            ffmx = ff
        kminmax = max(kminmax, k1)
        rkoma += koma
        fff += ff
    if kminmax > fff - ffmx:
        r1 = kminmax+ffmx-fff
    else:
        r1 = fff % 2
    rkoma += km[v]
#    print(v, r1 + rkoma, rkoma, fff + rkoma)
    return r1 + rkoma, rkoma, fff + rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)

r = 10**10
#print(f(4, {4}))
for i in range(N):
    a, c, fff = f(i+1, {i+1})
#    print(i, a, c)
    if a == c:
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)
S = input()
K = int(input())
INF = 5 * 10 ** 16

if S[0] == "1":
    if K <= int(S[1]) * 5 * 10 ** 15 + 1:
        print(S[1])
    else:
        print(S[2])
else:
    if K <= int(S[0]) * 5 * 10 ** 15:
        print(S[0])
    else:
        print(S[1])

### FIXED CODE ###

S = input()
K = int(input())

ans = "1"
for i in range(K):
    if S[i] != "1":
        ans = S[i]
        break

print(ans)
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2]).most_common(2)
b = Counter(v[1::2]).most_common(2)
if a[0][0] == b[0][0]:
    if a[1][1] > b[1][1]:
        print(n - a[1][1] - b[0][1])
    else:
        print(n - a[0][1] - b[1][1])
else:
    print(n- a[0][1] - b[0][1])

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2]).most_common()
b = Counter(v[1::2]).most_common()
if len(a) == 1:
    a.append([0, 0])
if len(b) == 1:
    b.append([0, 0])
if a[0][0] == b[0][0]:
    if a[1][1] > b[1][1]:
        print(n - a[1][1] - b[0][1])
    else:
        print(n - a[0][1] - b[1][1])
else:
    print(n- a[0][1] - b[0][1])
a,b = map(int,input().split)
print(a*b -a-b+1)

### FIXED CODE ###

H,W = map(int,input().split())
h,w = map(int,input().split())
print((H-h)*(W-w))
A,B,K=map(int,input().split())
 
for i in range(A,A+K):
    if i <= B-K:
        print(i)
for i in range(B-K,B):
    print(i)

### FIXED CODE ###

X=input()
A=X[0]
B=X[1]
C=X[2]
if A!=B and B!=C and C!=A:
    print("Yes")
else:
    print("No")
a = []
i = 0
while true:
  n = input()
  if n == 0:
    break
  a.append(n)
  print('Case {0}: {1}'.format(i,a))
  i++

### FIXED CODE ###

i = 1
while True:
  n = input()
  if n == "0":
    break
  print("Case {0}: {1}".format(i,n))
  i += 1
from heapq import heapify, heappop
from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n, k = map(int, input().split())

    dt = [(0, 0)] * n
    for i in range(n):
        t, d = map(int, input().split())
        dt[i] = (d, t-1)

    dt.sort(key=lambda x: x[0], reverse=True)

    # select k biggest points
    base = 0
    variety = [0] * n
    bonus = 0
    heap = []
    for d, t in dt[:k]:
        base += d
        if variety[t] == 0:
            bonus += 1
        variety[t] += 1
        heap.append((d, t))
    heapify(heap)

    # select exchange candidates
    new_dt = []
    for d, t in dt[k:]:
        if variety[t] == 0:
            variety[t] = 1
            new_dt.append((d, t))

    # exchange
    ans = base + bonus * bonus
    for new_d, new_t in new_dt:
        if len(heap) == 1:
            break
        d, t = heappop(heap)
        while len(heap) > 0 and variety[t] == 1:
            d, t = heappop(heap)
        variety[t] -= 1

        base -= d - new_d
        bonus += 1
        if ans < base + bonus * bonus:
            ans = base + bonus * bonus

    print(ans)

main()

### FIXED CODE ###

from heapq import heapify, heappop
from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n, k = map(int, input().split())

    dt = [(0, 0)] * n
    for i in range(n):
        t, d = map(int, input().split())
        dt[i] = (d, t-1)

    dt.sort(key=lambda x: x[0], reverse=True)

    # select k biggest points
    base = 0
    variety = [0] * n
    bonus = 0
    heap = []
    for d, t in dt[:k]:
        base += d
        if variety[t] == 0:
            bonus += 1
        variety[t] += 1
        heap.append((d, t))
    heapify(heap)

    # select exchange candidates
    new_dt = []
    for d, t in dt[k:]:
        if variety[t] == 0:
            variety[t] = 1
            new_dt.append((d, t))

    # exchange
    ans = base + bonus * bonus
    for new_d, new_t in new_dt:
        d, t = heappop(heap)
        while len(heap) > 0 and variety[t] == 1:
            d, t = heappop(heap)
        if len(heap) == 0:
            break
        variety[t] -= 1

        base -= d - new_d
        bonus += 1
        if ans < base + bonus * bonus:
            ans = base + bonus * bonus

    print(ans)

main()
n,k = map(int,input().split())
l = list(map(int,input().split()))
if n <= k:
    print("0")
    sys.exit()
l = sorted(l,reverse = True)
for i in range(k):
    l.remove(l[0])
d = dict.fromkeys(l)
a = 0
for j in d.keys():
    a += j
print(a)

### FIXED CODE ###

import sys
n,k = map(int,input().split())
l = list(map(int,input().split()))
if n <= k:
    print("0")
    sys.exit()
l = sorted(l,reverse = True)
hissatu = 0
for i in range(k):
    hissatu += l[i]
total = 0
for j in l:
    total += j
print(total-hissatu)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
RowIdx = set()
ColIdx = set()
Grid = defaultdict(list)
RowGrid = defaultdict(list)
ColGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	RowGrid[r].append(c)
	ColGrid[c].append(r)
	Grid[(r, c)] = a
	RowIdx.add(r)
	ColIdx.add(c)	

fresh = 1
while(fresh == 1):
	fresh = 0
	for row in RowIdx:
		if (len(RowGrid[row]) == 1):
			continue
		TempRow = RowGrid[row].copy()
		TempColGrid = ColGrid.copy()
		for pointer in TempRow:
			TempCol = TempRow.copy()
			TempCol.remove(pointer)
			for pair in TempCol:
				dif = Grid[(row, pointer)] - Grid[(row, pair)]
				ObjCol = TempColGrid[pointer].copy()
				ObjCol.remove(row)
				for obj in ObjCol:
					val = Grid[(obj, pointer)]- dif 
					if (val < 0):
						print("No")
						exit()
					if ((obj, pair) in Grid):
						if (val != Grid[(obj, pair)]):
							print("No");
							exit()
					else:
						Grid[(obj, pair)] = val
						RowGrid[obj].append(pair)
						ColGrid[pair].append(obj)
						fresh = 1
print("Yes")

### FIXED CODE ###

#A-Codefestival 2016
str=input()
str1=str[:4]+" "+str[4:]
print(str1)
N = int(input()):

if N % 10 == 2 or N % 10 == 4 or N % 10 == 5 or N % 10 == 7 or N % 10 == 9:
  print('hon')
elif N % 10 == 0 or N % 10 == 1 or N % 10 == 6 or N % 10 == 8:
  print('pon')
else:
  print('bon')

### FIXED CODE ###

n = int(input())

n_onesplace = n%10

if n_onesplace==2 or n_onesplace==4 or n_onesplace==5\
    or n_onesplace==7 or n_onesplace==9:
    print('hon')
elif n_onesplace==0 or n_onesplace==1 or\
    n_onesplace==6 or n_onesplace==8:
    print('pon')
else:
    print('bon')
r = []
c = 0
for i in input():
  if i == 'R':
    c+=1
  elif i=='S':
    r.append(c)
    c = 0
r.sort()
print(r[-1])
 

### FIXED CODE ###

c = 0
r = []
for i in input():
  if i=='R':
    c+=1
  else:
    r.append(c)
    c = 0
r.append(c)
if not len(r):
  print(c)
else:
  print(max(r))
x, y, z, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
import heapq
q = []
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
def val(i, j, k):
  return -(A[i] + B[j] + C[k])
heapq.heappush(q, (val(0,0,0), 0,0,0))
for _ in range(k):
  v, aa, bb, cc = heapq.heappop(q)
  print(-v)
  heapq.heappush(q, (val(aa+1, bb, cc), aa+1, bb, cc))
  heapq.heappush(q, (val(aa, bb+1, cc), aa, bb+1, cc))
  heapq.heappush(q, (val(aa, bb, cc+1), aa, bb, cc+1))


### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
import heapq
q = []
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
def val(i, j, k):
  return -(A[i] + B[j] + C[k])
heapq.heappush(q, (val(0,0,0), 0,0,0))
visited = set((0,0,0))
for _ in range(k):
  v, aa, bb, cc = heapq.heappop(q)
  print(-v)
  if aa + 1 < len(A) and (aa+1, bb, cc) not in visited:
    visited.add((aa+1, bb, cc))
    heapq.heappush(q, (val(aa+1, bb, cc), aa+1, bb, cc))
  if bb + 1 < len(B) and (aa, bb+1, cc) not in visited:
    visited.add((aa, bb+1, cc))
    heapq.heappush(q, (val(aa, bb+1, cc), aa, bb+1, cc))
  if cc + 1 < len(C) and (aa, bb, cc+1) not in visited:
    visited.add((aa, bb, cc+1))
    heapq.heappush(q, (val(aa, bb, cc+1), aa, bb, cc+1))
N = int(input())
A = [int(input()) for i in range(N)]
A.sorted()
print(sum(A[::-2]) - sum(A[-2::-2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
print(sum(A[::-2]) - sum(A[-2::-2]))
import re
seven = re.pattern("7")
print("Yes") if seven.match(input()) else "No"

### FIXED CODE ###

str = input()
print("Yes") if '7' in str else print("No")
import itertools
N, K = map(int, input().split())
pair = itertools.combinations(list(map(int, input().split())), 2)
res = [i[0] * i[1] for i in pair]
res.sort()
if len(res) != 0:
    print(res[K-1])

### FIXED CODE ###

A, B, C = map(int, input().split())
if A == B and A == C:
    print("No")
elif A == B or A == C or B == C:
    print("Yes")
else:
    print("No")
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import math
input = sys.stdin.readline

def gcd(a, b):
    return math.gcd(a, b)

def lcm(a, b):
    return a * b / gcd(a, b)

class slist(list):
    def __init__(self, *args, **kw):
        list.__init__(self, *args, **kw)
        self.sort()

    def append(self, value):
        bisect.insort(self,value)

    def index_left(self, value):
        return bisect.bisect_left(self, value)


if __name__ == '__main__':
    a,b = map(int, input().split())
    if a <= 8 and b <= 8:
        print('Yay!')
    else:
        print(':()')


### FIXED CODE ###

# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import math
import sys
input = sys.stdin.readline

def gcd(a, b):
    return math.gcd(a, b)

def lcm(a, b):
    return a * b / gcd(a, b)

class slist(list):
    def __init__(self, *args, **kw):
        list.__init__(self, *args, **kw)
        self.sort()

    def append(self, value):
        bisect.insort(self,value)

    def index_left(self, value):
        return bisect.bisect_left(self, value)


if __name__ == '__main__':
    a,b = map(int, input().split())
    if a <= 8 and b <= 8:
        print('Yay!')
    else:
        print(':(')
N=int(input())
num=0
ans=""
for i in range(1,9):
    if 26**i > N:
        N-=1
       for j in range(i):
           ans+=chr(ord("a")+N%26)
           N//=26
       break
    else:
       N-=26**i
print(ans[::-1])


### FIXED CODE ###

N=int(input())
num=0
ans=""
for i in range(1,99):
    if 26**i >= N:
        N-=1
        for j in range(i):
            ans+=chr(97+N%26)
            N//=26
        break
    else:
        N-=26**i
print(ans[::-1])
W,H,x,y,r=map(int,input().split())
if y+r<=H and y>r and x+r<W and x>r:
    print("Yes")
else
    print("No")


### FIXED CODE ###

W,H,x,y,r=map(int,input().split())
if y+r<=H and y>=r and x+r<=W and x>=r:
    print("Yes")
else:
    print("No")
def main():
    s = input()
    lens = len(s)

    d1 = defaultdict(int)
    ss = int(s[-4:]) % 2019
    k = 5
    while k <= lens:
        d1[ss] += 1
        ss += (int(s[-k]) * (10 ** (k - 1))) % 2019
        ss = ss % 2019
        k += 1
    d1[ss] += 1
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()
import math
s = list(str(input()))
lis = ""
li = ""
num = 0
cou = [0 for i in range(26)]
for i in range(len(s)):
  if s[i] != "x":
    lis += s[i]
    li = s[i] + li
  else:
    num += 1
if lis != li:
  print(-1)
  exit()
point = lis[len(lis)//2]
ss = []
tt = []
nu = 0
while s[nu] != point:
  ss.append(s[nu])
  nu += 1
nu = 0
while s[-1-nu] != point:
  tt.append(s[-1-nu])
  nu += 1
ans = 0
for i in range(len(ss)):
  if ss[i] != tt[i]:
    ans += 1
print(ans)

### FIXED CODE ###

import math
s = str(input())
cou = 0
co = 0
ans = 0
while cou + co +2 <= len(s):
  if s[cou] == "x":
    if s[-1-co] == "x":
      cou += 1
      co += 1
    else:
      cou += 1
      ans += 1
  else:
    if s[-1-co] == "x":
      co += 1
      ans += 1
    else:
      if s[cou] == s[-1-co]:
        cou += 1
        co += 1
      else:
        print(-1)
        exit()
print(ans)
A,B=map(int,input().split())
x = [A,B]
A = [1,2,3]
for idx in range(len(A)):
  if A[idx] in x == False:
    print(A[idx])
    break
 

### FIXED CODE ###

A = int(input())
B = int(input())
print(6-A-B)
from bisect import bisect_left

n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

lis = [float('inf')]*(n+5)
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:continue
        dfs(to, now)
    lis[idx] = tmp

dfs(0,-1)
for x in ans:
    print(x)

### FIXED CODE ###

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

n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

lis = [float('inf')]*n
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:
            continue
        dfs(to, now)
    lis[idx] = tmp

dfs(0,-1)
for x in ans:
    print(x)