Harryxun/stf_run huggingface dataset:
import bisect
N = int(input())
A = list(map(int, input().split()))
A.sort()
insert_index = bisect.bisect_left(A,0)
if len(A[:insert_index]) % 2 == 0:
    Ans = -1*sum(A[:insert_index])+sum(A[insert_index:])
else:
    Tmp = -1*sum(A[:insert_index])+sum(A[insert_index:])
    if insert_index == 0:   #全て正のとき
        Ans = Tmp - A[0]*2
    else:
        if insert_index < len(A):
            Ans = max(Tmp-A[:insert_index]*2, Tmp+A[insert_index-1]*2)
        else:
            Ans = Tmp + A[-1]
print(Ans)

### FIXED CODE ###

import bisect
total = 0
N = int(input())
A = list(map(int, input().split()))
hu = [i for i in A if i < 0]
sei = [i for i in A if i >= 0]
hu.sort()
sei.sort()
if len(hu) % 2 == 0:
    print(sum(sei)+sum(hu)*-1)
else:
    if sei:
        print(sum(sei)+sum(hu)*-1 - min(-1*hu[-1], sei[0])*2)
    else:
        print(sum(sei)+sum(hu)*-1 + 1*hu[-1]*2)
import sys
sys.setrecursionlimit(1000000)
A,B,C,D,E,F = [int(x) for x in input().split()]

x = []
y = []
ans_max = 0
ans = []

for i in range(F//(100*A)+1):
    for j in range((F-100*A*i)//(100*B)+1):
        water = 100*(A*i+B*j)
        if(water<=F and not water in x):
            x.append(water)

for i in range(F):
    for j in range(F):
        salt = C*i+D*j
        if(salt<=F and not salt in y):
            y.append(salt)

for i in x:
    for j in y:
        if(i==0):
            break
        elif(100*j <= i*E and i+j <= F):
            percent = 100*j/(i+j)
            if(ans_max < percent):
                ans_max = percent
                ans = [i,j]

print(sum(ans),ans[1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
A,B,C,D,E,F = [int(x) for x in input().split()]

x = []
y = []
ans_max = 0
ans = [0,0]

for i in range(F//(100*A)+1):
    for j in range((F-100*A*i)//(100*B)+1):
        water = 100*(A*i+B*j)
        if(water<=F and not water in x and water!=0):
            x.append(water)

ans[0]=x[0]

for i in range(F):
    for j in range(F):
        salt = C*i+D*j
        if(salt<=F and not salt in y):
            y.append(salt)

for i in x:
    for j in y:
        if(i==0):
            continue
        elif(100*j <= i*E and i+j <= F):
            percent = 100*j/(i+j)
            if(ans_max < percent):
                ans_max = percent
                ans = [i,j]

print(sum(ans),ans[1])
# -*- coding: utf-8 -*-
import math
a,b =map(int,input().split())
N =str(a)+str(b)
int(ans)= math.sqrt(int(N))
if int(N)==ans*ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b =map(int,input().split())
N=a*b
if 0==N%2:
    print("Even")
else:
    print("Odd")
n = int()
a = list[map(int, input().split())]
s = 1
for i in n+1 :
  ans = s*a[i]
if ans => 10**8:
  print("-1")
else:
  print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 0 in a:
  print(0)
else:
  s = 1
  for i in a :
    s *= i
    if s > 10**18:
      s = -1
      break
  print(s)
n=int(input())
s=input()

r_cnt=s.count("R")
g_cnt=s.count("G")
b_cnt=s.count("B")

ans=r_cnt*g_cnt*b_cnt

for i in range(n):
    for d in range(n):
        j=i+d
        k=j+d
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans-=1

print(ans)

### FIXED CODE ###

n=int(input())
s=input()

r_cnt=s.count("R")
g_cnt=s.count("G")
b_cnt=s.count("B")

ans=r_cnt*g_cnt*b_cnt

for i in range(n):
    for d in range(n):
        j=i+d
        k=j+d
        if k>=n:
            break
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans-=1

print(ans)
N = int(input())
l = len(N)
for i in range(l):
  if N.index(i) ==7:
    print("Yes")
    exit()
print("No")    

### FIXED CODE ###

N = input()
l = len(N)
for i in range(l):
  if N[i] =="7":
    print("Yes")
    exit()
print("No")
def lcm(x, y):
	""" 最小公倍数を求める """
    return (x * y) // math.gcd(x, y)

def q3():
    """ C - Anti-Division """
    import math
    A,B,C,D = (int(i) for i in input().split())

    num_C = B // C - (A - 1) // C  # Cで割り切れる個数
    num_D = B // D - (A - 1) // D  # Dで割り切れる個数
    lcm_CD = lcm(C, D)
    num_CD = B // lcm_CD - (A - 1) // lcm_CD  # CとDの最小公倍数で割り切れる個数
    
    num_all = num_C + num_D - num_CD  # 全ての割り切れる個数
    ans = B - A + 1 - num_all
    print(ans)

if __name__ == '__main__':
    q3()

### FIXED CODE ###

def q3():
    """ C - Anti-Division """
    from fractions import gcd  # 3.4.3ではmath.gcdは無い
    A,B,C,D = (int(i) for i in input().split())

    def lcm(x, y):
        """ 最小公倍数を求める """
        return (x * y) // gcd(x, y)

    num_C = B // C - (A - 1) // C  # Cで割り切れる個数
    num_D = B // D - (A - 1) // D  # Dで割り切れる個数
    lcm_CD = lcm(C, D)
    num_CD = B // lcm_CD - (A - 1) // lcm_CD  # CとDの最小公倍数で割り切れる個数
    num_all = num_C + num_D - num_CD  # 全ての割り切れる個数
    ans = B - A + 1 - num_all
    print(ans)


if __name__ == '__main__':
    q3()
B = [int(input()) for _ in range(5)]
A = [10-int(str(B[i])[-1]) for i in range(5) if str(B[i])[-1] != "0"]
A.remove(max(A))
print(sum(B)+sum(A))

### FIXED CODE ###

B = [int(input()) for _ in range(5)]
A = [10-int(str(B[i])[-1]) for i in range(5) if str(B[i])[-1] != "0"]
if len(A) != 0:
	A.remove(max(A))
print(sum(B)+sum(A))
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = 0
vis = [0] * (N + 1)
def dfs(x):
  global vis
  r = 0
  if p[x] >= pp[x]: r = p[x] - ((p[x] - pp[x]) % 2)
  if p[x] <= pp[x]: return r
  for y in e[x]:
    if vis[y[0]] == 1: continue
    vis[y[0]] = 1
    r = max(r, dfs(y[0]))
  #print(r, x)
  return r
res = dfs(u)
for x in e[u]:
  if p[x[0]] > pp[x[0]]: 
    print(res)
    exit(0)
print(1)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = 0
for i in range(1, N + 1):
  if p[i] > pp[i]: res = max(p[i], res)
print(res - 1)
from math import ceil
x = int(input())
ans = ceil(x / 11 * 2)
if (x % 11) % 6 == 0 or if (x % 11) % 5 == 0:

print(ans)

### FIXED CODE ###

x = int(input())
ans = (x // 11 * 2)


if  x % 11 <= 6 and x % 11 != 0:
    ans += 1
elif x % 11 >= 7:
    ans += 2

print(ans)
N = int(input())
s = map(int, input().split())
c = 0

for i in range(1, N):
	if s[i] == s[i - 1]:
		c += 1
	else:
print(c)


### FIXED CODE ###

N = int(input())
a = [s for s in map(int, input().split())]
a.append(-1)
c = 0
result = 0
for i in range(1, N + 1):
	if a[i] == a[i - 1]:
		c += 1
	else:
		if c == 0:
			continue
		else:
			c += 1
			if c % 2 == 1:
				result += (c - 1) / 2
				c = 0
			else:
				result += c / 2
				c = 0
print(int(result))
n,m = map(int,input())
path = [map(int,input()) for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        print(z)
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        count += 1

### FIXED CODE ###

n,m = map(int,input().split())
path = [input().split() for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        count += 1
print(count)
a,b = int(input())
if a*b % 2 == 1:
  print("Odd")
else:
  print("Even")

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 1:
  print("Odd")
else:
  print("Even")
import itertools
import sys


def main(argv):
    inputs = [int(v) for v in argv]
    A = inputs[0]
    B = inputs[1]
    C = inputs[2]
    X = inputs[3]

    cnt = 0
    for n_500, n_100, n_50 in itertools.product(A, B, C):
        if 500 * n_500 + 100 * n_100 + 50 * n_50 == X:
           cnt += 1

    print(cnt)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

import itertools


def main():
    A = int(input()) + 1
    B = int(input()) + 1
    C = int(input()) + 1
    X = int(input())

    cnt = 0
    for n_500, n_100, n_50 in itertools.product(range(A), range(B), range(C)):
        y = 500 * n_500 + 100 * n_100 + 50 * n_50
        if y == X:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()
l=int(input())
print((l/3)**3)

### FIXED CODE ###

S=input()
N=len(S)
A=S[:(N-1)//2]
B=S[(N+3)//2-1:]
if S!=S[::-1] or A!=A[::-1] or B!=B[::-1]:
    print("No")
else:
    print("Yes")
S = input()
K = int(input())

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K < ones:
    print('1')
else:
    print(S[ones])

### FIXED CODE ###

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

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K-1 < ones:
    print('1')
else:
    print(S[ones])
n,m = list(map(int,input().split()))

dic = dict()
dicSet = set()
dicList = dict()
count = 0

ans = 0

for i in range(m):
    a,b = list(map(int,input().split()))
    if not(a in dicSet) and not(b in dicSet):
        dic[count] = set()
        dic[count].add(a)
        dic[count].add(b)
        dicList[a] = count
        dicList[b] = count
        count += 1
        dicSet.add(a)
        dicSet.add(b)

    elif a in dicSet and b in dicSet:
        if dicList[a] != dicList[b]:
            dic[count] = dic[dicList[a]] | dic[dicList[b]]
            del dic[dicList[a]]
            del dic[dicList[b]]
            dicList[a] = count
            dicList[b] = count
            count += 1

    elif a in dicSet:
        dic[dicList[a]].add(b)
        dicList[b] = dicList[a]
        dicSet.add(b)
    else:
        dic[dicList[b]].add(a)
        dicList[a] = dicList[b]
        dicSet.add(a)


ans = 1

#print(dic)

for i in range(0,count):
    long = len(dic[i])
    if long > ans:
        ans = long

print(ans)

### FIXED CODE ###

import collections

def searchRoot(n):
    par = parList[n]
    if n == par:
        if len(q) > 0:
            rootIn(q,n)
        return n
    else:
        q.append(n)
        return(searchRoot(par))

def rootIn(q,root):
    while len(q) > 0:
        parList[q.popleft()] = root

n,m = list(map(int,input().split()))
q = collections.deque()

parList = [i for i in range(n+1)]

for i in range(m):
    a,b = list(map(int,input().split()))
    aRoot = searchRoot(a)
    bRoot = searchRoot(b)
    if aRoot != bRoot:
        parList[max(aRoot,bRoot)] = min(aRoot,bRoot)
    
#print(parList)

ansDic = dict()
rootSet = set()
for i in range(1,n+1):
    root = searchRoot(i)
    if root in rootSet:
        ansDic[root] += 1
    else:
        rootSet.add(root)
        ansDic[root] = 1

ans = 1
for i in rootSet:
    if ansDic[i] > ans:
        ans = ansDic[i]

print(ans)
a, b = map(int, input().split())
if (a + b) % 2 == 0:
  print(a + b) // 2
else:
  print((a + b) // 2 + 1)

### FIXED CODE ###

a, b = map(int, input().split())
x = (a + b) / 2
if x == (a + b) // 2:
  print((a + b) //2)
else:
  print((a + b) // 2 + 1)
def mergesort(A, left, right):

    if left + 1 < right:
        mid = (left + right)/2
        
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
   
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 100000000000000000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        



# kannsei
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
            
    A[i+1], A[r-1]=A[r-1], A[i+1]
    
    retu
rn i+1

def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
        
        quicksort(A, p, q)
        quicksort(A, q+1, r)


if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
    print " \n".join(num_list)
    mergesort(num_list1, 0, len(num_list1))
    print "\n".join(num_list1)
    
    if num_list == num_list1:
        print ("Stable")
    else:c
        print ("Not stable")

### FIXED CODE ###

def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):

    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = "  10000000000"
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][2:]) <= int(R[j][2:]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = int(A[r-1][2:])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2:]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)
from sys import stdin, gettrace
import sys
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def main():
    def mincost(n,h):
    	dp=[-1 for i in range(n)]
    	dp[n-1]=0
    	dp[n-2]=abs(h[n-2]-h[n-1])
    	for i in range(n-3,-1,-1):
        	mn=min(i+k+1,n)
        	mnm=sys.maxsize
        	for j in range(i+1,mn):
            	mnm=min(dp[j]+abs(h[j]-h[i]),mnm)
        	dp[i]=mnm    
    	return dp[0]
    
    n,k=map(int,input().split())
    h=[int(x) for x in input().split()]
    print(mincost(n,h))
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin, gettrace
import sys
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def mincost(n,h,k):
  dp=[-1 for i in range(n)]
  dp[n-1]=0
  dp[n-2]=abs(h[n-2]-h[n-1])
  for i in range(n-3,-1,-1):
    mn=min(i+k+1,n)
    mnm=sys.maxsize
    for j in range(i+1,mn):
      mnm=min(dp[j]+abs(h[j]-h[i]),mnm)
    dp[i]=mnm    
  return dp[0]
 
def main():
  n,k=map(int,input().split())
  h=[int(x) for x in input().split()]
  print(mincost(n,h,k)) 
 
if __name__ == "__main__":
    main()
import sys
sys.setrecursionlimit(1000000000)

def rec(n):
    if n == 1:
        return 1
    return rec(n-1) + 1


print(rec(1000000))


### FIXED CODE ###

A, B = map(int, input().split())
print(max(A*2-1,A+B,B*2-1))
N = int(input())
arr = []
product = 1
# while i < N:
arr = ((input().split(' ')))

for i in arr:
    if( i == 0):
        print(0)
        return
    product = product * int(i)

if product <= (10**18):
    print(product)
else:
    print(-1)

### FIXED CODE ###

def main ():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A: 
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod) 

main ()
n,x=map(int,input().split())
B=["P"]
for i in range(1,n+1):
  b="B"+B[i-1]+"P"+B[i-1]+"B"
  B.append(b)
print(B[n][:x].count("P"))

### FIXED CODE ###

N,X=map(int,input().split())
a,p=[1],[1]
for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)
def f(n,x):
    if n==0:return 0 if x<=0 else 1
    elif x<=1+a[n-1]:return f(n-1,x-1)
    else:return p[n-1]+1+f(n-1,x-2-a[n-1])
print(f(N,X))
n = int(input())
for i in range(n):
  s = input():
    if s == "Y":
      print("Four")
      break
    else:
      print("Three")

### FIXED CODE ###

n = int(input())
s = list(input().split())

if len(set(s)) == 3:
  print("Three")
else:
  print("Four")
n = int(input())
s = input()

if s == "." * n:
    print(0)
else:
    black = [i for i, x in enumerate(s) if x == "#"]
    wb = [i for i, x in enumerate(s[black[0]:]) if x == "."]
    bw = [i for i, x in enumerate(s[:wb[-1]]) if x == "#"]
    print(min(len(wb), len(bw)))

### FIXED CODE ###

n = int(input())
s = input()
sr = s[::-1]

ans = s.count(".")
num = ans
for i in range(n):
    if s[i] == ".":
        num -= 1
    else:
        num += 1
    ans = min(num, ans)
print(ans)
n = input()
m = n.split()
print(m)
l = m[2:]
a = sorted(l, reverse=True)
p = 0
for i in range(0,int(m[1])):
    p = p + int(c[i])
print(int(p))

### FIXED CODE ###

n = input()
m = n.split()
a = [input() for l in range(0,1)]
b = a[0].split()
for i in range(0, len(b)):
    b[i] = int(b[i])
c = sorted(b, reverse=True)
p = 0
for i in range(int(m[0]) - int(m[1]),int(m[0])):
    p = p + int(c[i])
print(p)
whatMan = []
 
N, K = input()
for i in range(int(K)):
　　　　wahtMan.append(input().split())
print(wahtMan)

### FIXED CODE ###

whatMan = []

N, K = input().split()
for i in range(int(K)):
    input()
    whatMan.extend(input().split())
print(int(N) - len(set(whatMan)))
try:
	n = int(input())
	tmp = 360
	while True:
    	if tmp % n == 0:
        	print(tmp//n)
        	exit(0)
    	else:
        	tmp+= 360

### FIXED CODE ###

X = int(input())
tmp = 360
while True:
    if tmp % X == 0:
        print(tmp//X)
        exit()
    else:
        tmp+= 360
n = int(input())
n = n % 10
if n == 2 or n == 4 or n == 5 or n == 7 or n == 9:
    print("hon")
elif n == 0 or n == 1 or n == 6 or n == 8:
    print("pon")
else
    print("bon")


### FIXED CODE ###

n = int(input())
n = n % 10
if n == 2 or n == 4 or n == 5 or n == 7 or n == 9:
    print("hon")
elif n == 0 or n == 1 or n == 6 or n == 8:
    print("pon")
else:
    print("bon")
N, M = map(int, input().split())
A_sum = 0

for i in range(M):
    A_sum += int(input())

if (N - A_sum) > 0:
    print(N - A_sum)
else:
    print("-1")

### FIXED CODE ###

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

for i in range(M):
    sum += A[i]

if (N - sum) >= 0:
    print(N - sum)
else:
    print("-1")
n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

for i in range(n):
    print(ans[i+1])


### FIXED CODE ###


import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u, v = v, u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    tree[uv[1]].append(uv[0])
    

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        for child in tree[cur]:
            if used[child] == 0:
                queue.append(child)
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1
for i in range(n):
    print(ans[i+1])
n = int(input())
x = list(map(int, input().split()))

a = []
for pp in 100:
    sum = 0
    for xx in x:
        sum += abs((xx-pp) ** 2)
    a.append(sum)

print(min(a))


### FIXED CODE ###


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

a = []
for pp in range(1,101):
    sum = 0
    for xx in x:
        sum += abs((xx-pp) ** 2)
    a.append(sum)

print(min(a))
n=input()
s=input()
c,m=0,0
for i in range(n-1):
    if s[i]=="I":
        c+=1
        m=max(c,m)
    if s[i]=="D":
        c=c-1
print(m)

### FIXED CODE ###

input()
s=input()
c,m=0,0
for i in range(len(s)):
    if s[i]=="I":
        c+=1
        m=max(c,m)
    if s[i]=="D":
        c=c-1
        m=max(c,m)
print(m)