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

import sys 

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

a_sorted = sorted(a)

a_max = a_sorted[-1]
a_min = a_sorted[0] - n

kanasisa_min = sys.maxsize
for b in range(a_min,a_max+1):
    kanasisa = 0
    for i,data in enumerate(a):
        kanasisa += abs(data - (b + i + 1))
    if kanasisa < kanasisa_min:
        kanasisa_min = kanasisa

print(kanasisa_min)

### FIXED CODE ###

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

a_max = max(a)
a_min = min(a) - n

t = (a_min + a_max) // 2

while (a_min <= a_max):
    plus_minus = 0
    for i,data in enumerate(a):
        if data < t + i + 1:
            plus_minus -= 1
        elif data > t + i + 1:
            plus_minus += 1

    if (plus_minus == 0):
        break
    elif (plus_minus > 0):
        a_min = t + 1
    elif (plus_minus < 0):
        a_max = t - 1
    t = (a_min + a_max) // 2

kanasisa = 0
for i,data in enumerate(a):
    kanasisa += abs(data - (t + i + 1))

print(kanasisa)
### BUGGY CODE ###

import itertools

N = int(input())
P = tuple(map(int, input().split()))

m = 0

for i in range(1, N+1, 1):
    p = P[i-1]
    #print(P[:i])
    q = sorted(P[:i])[0]

    if p <= q:
        m += 1

print(m)

### FIXED CODE ###

N = int(input())
P = tuple(map(int, input().split()))

pmin = P[0]

m = 1

for i in range(1, N, 1):
    if P[i] < pmin:
        pmin = P[i]
        m += 1

print(m)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

x = int(input())
s_candidates = []


for i in range(1, x+1):
    if x % i == 0:
        s_candidates.append(i)

for s in s_candidates:
    for a in range(x):
        b = a - s
        t = x / s
        tmp = a**4 + (a**3) * b + (a**2) * (b**2) + a * (b**3) + b**4
        if t == tmp:
            ans_a = a
            ans_b = b
            break
    if t == tmp:
        break

print(ans_a, ans_b)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

x = int(input())
flg = 0

for i in range(1, x+1):
    if x % i != 0:
        continue
    else:
        for a in range(x):
            b = a - i
            if a**5 - b**5 == x:
                ans_a = a
                ans_b = b
                flg = 1
                break
            elif a > i and a**5 - b**5 > x:
                flg = -1
                break
        if flg == 1:
            break
        elif flg == -1:
            flg = 0
            continue

print(ans_a, ans_b)
### BUGGY CODE ###

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

K = A[1]
N = A[0]

P = list(map(float, input().split()))

new_list = []

for val in range(N-K+1):
    P_list=P[val:val+K]
    new_list.append(sum(list(map(lambda x: (1+x) / 2, P_list))))

print(max(new_list))


### FIXED CODE ###

import numpy

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

K = A[1]
N = A[0]

P = list(map(float, input().split()))

EP = list(map(lambda x: (1+x)/2, P))

cumEP = list(numpy.cumsum(EP))

new_list = []

if N>K:
    for val in range(N-K):
        new_list.append(cumEP[val+K]-cumEP[val])
    print(max(new_list))
else:
    print(sum(EP))
### BUGGY CODE ###

MOD = 10**9 + 7


def ketadp3(a, b):
    L = len(str(a))

    # dp = [[[0 for i in range(b)] for j in range(2)] for k in range(L + 1)]
    dp = [[[0 for i in range(2)] for j in range(b)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(str(a)[i])
        for k in range(b):
            for j in range(2):
                for d in range(10 if j else D+1):
                    dp[i + 1][((k + d) % b)][j or (d < D)] += dp[i][k][j]
                    dp[i + 1][((k + d) % b)][j or (d < D)] %= MOD

    return (dp[L][0][0] + dp[L][0][1] - 1) % MOD


def main():
    # a, b = map(int, input().split())
    # print(ketadp(b)-ketadp(a-1))
    n = int(input())
    d = int(input())
    print(ketadp3(n, d))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10**9 + 7
def ketadp3(a, b):
    L = len(a)

    dp = [[[0 for i in range(2)] for j in range(b)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(a[i])
        for k in range(b):
            for j in range(2):
                for d in range(10 if j else D+1):
                    dp[i + 1][(k + d) % b][j or (d < D)] += dp[i][k][j]
                    dp[i + 1][(k + d) % b][j or (d < D)] %= MOD

    print((dp[L][0][0] + dp[L][0][1] - 1) % MOD)


def main():
    n = input()
    d = int(input())
    ketadp3(n, d)


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

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

def median(x):
    x = sorted(x)

    return(x[(len(x) + 1) // 2 - 1])

for i in range(n):
    a = x.pop(i)
    print(median(x))
    x.insert(i, a)

### FIXED CODE ###

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

y = sorted(x)

for i in x:
    if i < y[len(y) // 2]:
        print(y[len(y) // 2])
    else:
        print(y[len(y) // 2 - 1])
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= k**(v - fs[k])
    ans += a
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

lcm = 1
for a in A:
    lcm = lcm // gcd(lcm,a) * a

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
import os

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    A=[0]*M
    B=[0]*M
    for i in range(M):
        A[i],B[i]=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i])+" tmp:"+str(tmp))
        # print(tmp[A[i]-1])

    al=[False]*N    #すでに探索したか
    al[0]=True
    out=[0]*N   #何番目に通るか
    li=[]
    li.append([1])     #深さ毎の数値
    for de in range(N): #深さで探索
        tmp=[]
        # print(de)
        for l in li[de]:
            for i in range(M):  #A,Bの探索
                if A[i]==l and not al[B[i]-1]: #A[i]が一個前とつながってたら
                    tmp.append(B[i])
                    out[B[i]-1]=l
                    al[B[i]-1]=True
                    # print("A="+str(B[i])+" l="+str(l)+" out"+str([B[i]-1])+"="+str(out[B[i]-1]))
                if B[i]==l and not al[A[i]-1]:
                    tmp.append(A[i])
                    out[A[i]-1]=l
                    al[A[i]-1]=True
                    # print("B="+str(A[i])+" l="+str(l)+" out"+str([A[i]-1])+"="+str(out[A[i]-1]))
        li.append(tmp)
        # print(al)


    print('Yes')
    [print(x) for x in out[1:]]

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i]))
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        # print(tmp[A[i]-1])
    # print(r)

    q=deque()
    q.append(1)
    visited=set()
    visited.add(1)
    out=[0]*(N-1)
    while len(q)>0:
        # print("q="+str(q))
        position=q.popleft()
        # print("p="+str(position))
        for des in r[position]: #今いる場所から行ける場所を探索
            if des not in visited:  #訪問済みでないなら
                q.append(des)   #行ける場所だった場合キューに追加
                visited.add(des)   #訪問済みにする
                out[des-2]=position
                # print("destination="+str(des)+" p="+str(position)+" q="+str(q))
    # print(visited)



    print('Yes')
    [print(x) for x in out]

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

import sys
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

### FIXED CODE ###

from collections import deque

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])
### BUGGY CODE ###

N = int(raw_input())
a = map(int,raw_input().split())
con = 0
i = 0
while i <= N:
  if len(a)==0:
    con = -1
    print con
    break
  elif len(a)==con:
    print N-con
    break
  elif a[con] == con+1:
    con = con + 1
  else:
    a.pop(con)
  i= i+1

### FIXED CODE ###

N = int(raw_input())
a = map(int,raw_input().split())
con = 1
ans = 0
for i in range(0,N):
  if a[i] == con:
    con = con + 1
    continue
  else:
    ans = ans + 1
if ans == N:
  print -1
else:
  print ans
### BUGGY CODE ###

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

set_ = set()

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            set_.add(''.join([s[i], s[j], s[k]]))

print(len(set_))

### FIXED CODE ###

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

cnt = 0
for x in range(10):
    x_ = str(x)
    for i in range(n-2):
        if s[i] == x_:
            break
    else:
        continue
    for y in range(10):
        y_ = str(y)
        for j in range(i+1, n-1):
            if s[j] == y_:
                break
        else:
            continue
        for z in range(10):
            z_ = str(z)
            for k in range(j+1, n):
                if s[k] == z_:
                    cnt += 1
                    break

print(cnt)
### BUGGY CODE ###

N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for i in range(N):
        if not isused[i]:
            d1 = min(abs(xy[n][0] - xy[i][0]), abs(xy[n][1] - xy[i][1]))
            heappush(h, (d1, i))
    
print(result)


### FIXED CODE ###

N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    neighbors[x1].append(x2)
    neighbors[x2].append(x1)
    neighbors[y1].append(y2)
    neighbors[y2].append(y1)

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for i in neighbors[n]:
        if not isused[i]:
            d1 = min(abs(xy[n][0] - xy[i][0]), abs(xy[n][1] - xy[i][1]))
            heappush(h, (d1, i))
    
print(result)
### BUGGY CODE ###

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

ans = N  # consider l < r cases below
sumA = [0]
for i in range(N):
    sumA.append(sumA[-1]+A[i])

for l in range(N):
    r = l - 1
    while r < N - 1:
        r += 1
        cur_sum = sumA[r+1] - sumA[l]
        if r == l:
            xor_A = A[r]
        else:
            xor_A = xor_A ^ A[r]
            if xor_A == cur_sum:
                ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
r = 0
xor_A = 0
for l in range(N):
    while (r < N and (xor_A ^ A[r]) == (xor_A + A[r])):
        xor_A += A[r]
        r += 1
    ans += r - l
    if l == r:
        r += 1
    else:
        xor_A -= A[l]
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(len(As)):
    for j in range(i+1, len(As)):
        if (abs(i - j ) == As[i] + As[j]):
            ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict
import numpy as np
import collections

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

B = defaultdict(int)

ans = 0

for index, A in enumerate(As):
    ans += B[index-A]
    
    B[index+A] += 1
#    print(B)
#    print(list(B[:20]))

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

N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=[0]*100001
for i in range(100001):
    number_count[i]=number.count(i)

for _ in range(Q):
    B,C=map(int,input().split())
    sum_number += (C-B)*number_count[B]
    number_count[C] += number_count[B]
    number_count[B] = 0
    print(sum_number)


### FIXED CODE ###

from collections import Counter
N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=Counter(number)


for _ in range(Q):
    B,C=map(int,input().split())
    sum_number += (C-B)*number_count[B]
    number_count[C] += number_count[B]
    number_count[B] = 0
    print(sum_number)
### BUGGY CODE ###

N = int(input())

li = 0
print(li, flush=True)
ls = input()
if ls == 'Vacant':
    exit()

ri = N - 1
print(ri, flush=True)
rs = input()
if rs == 'Vacant':
    exit()

for _ in range(18):
    mid = (li + ri) // 2

    print(mid, flush=True)
    s = input()

    if s == 'Vacant':
        exit()

    c1 = (mid - li - 1) % 2 == 1 and ls == s
    c2 = (mid - li - 1) % 2 == 0 and ls != s
    if c1 or c2
        ri = mid
        rs = s
    else:
        li = mid
        ls = s


### FIXED CODE ###

N = int(input())

li = 0
print(li, flush=True)
ls = input()
if ls == 'Vacant':
    exit()

ri = N - 1
print(ri, flush=True)
rs = input()
if rs == 'Vacant':
    exit()

for _ in range(18):
    mid = (li + ri) // 2

    print(mid, flush=True)
    s = input()

    if s == 'Vacant':
        exit()

    # [li, mid]に空席がある
    c1 = (mid - li) % 2 == 1 and ls == s
    c2 = (mid - li) % 2 == 0 and ls != s
    if c1 or c2:
        ri = mid
        rs = s
    else:
        li = mid
        ls = s
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

ls = []

for i in range(1, N):
    A = sum(ax[:i])
    B = sum(ax[i:])
    ls.append(abs(A-B))

print(sorted(ls)[0])


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

ls = []
A = sum(ax[:1])
B = sum(ax[1:])

for i in range(1, N):
    sub = abs(A-B)
    ls.append(sub)
    if(sub is 0):
        break
    A += ax[i]
    B -= ax[i]

print(sorted(ls)[0])
### BUGGY CODE ###

import sys

# import bisect
# from collections import Counter, deque

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

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


def main():
    n = int(input())
    a = [int(readline()) for _ in range(n)]

    c = [-1] * n
    ans = 1

    for number in a:
        for j in range(ans):
            if c[j] < number:
                c[j] = number
                break
        else:
            c[ans] = number
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

import bisect

# from collections import Counter, deque

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

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


def main():
    n = int(input())
    a = [-int(readline()) for _ in range(n)]

    c = [1] * n

    for number in a:
        idx = bisect.bisect_right(c, number)
        c[idx] = number

    ans = bisect.bisect_left(c, 1)
    print(ans)


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

n,k=map(int,input().split())
H=list(map(int,input().split()))

dp=[float('inf')]*n
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<n:
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))

dp=[float('inf') for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<len(dp):
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[-1])
### BUGGY CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
sum=0
i=0
while i<n:
  if v[i]>c[i]:
    sum+=v[i]-c[i]
print(sum)

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
sum=0
i=0
while i<n:
    if v[i]>c[i]:
        sum+=v[i]-c[i]
    i+=1
print(sum)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [(1, -maxsize)] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())
        a -= 1
        base[a] += v

        b = a - a % 10000
        index = value = -maxsize
        for i, v in enumerate(base[b:b+10000], b+1):
            if value < v:
                value = v
                index = i
        midway[b//10000] = (index, value)

        index = value = -maxsize
        for i, v in midway:
            if value < v:
                value = v
                index = i
        print(index, value)
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


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

import copy
import numpy as np
from math import factorial

def num_choice_2(N):
    if N > 1:
        return N * (N - 1) // 2
    else:
        return 0

N = int(input())
A = [int(x) for x in input().split()]

nums = np.zeros(N, dtype=int)
for a_i in A:
    nums[a_i - 1] += 1

num_default = np.sum([num_choice_2(x) for x in nums])

for i in range(N):
    if nums[A[i] - 1] <= 1:
        ans = num_default
    else:
        nums[A[i] - 1] -= 1
        ans = np.sum([num_choice_2(x) for x in nums])
        nums[A[i] - 1] += 1
    
    print(ans)

### FIXED CODE ###

def n_c_2(n):
    if n < 1:
        return 0
    else:
        return n * (n - 1) // 2

N = int(input())
A = [int(x) for x in input().split()]

n_balls = [0 for _ in A]
for a_i in A:
    n_balls[a_i - 1] += 1

n_combinations = [n_c_2(n) for n in n_balls]
total_combinations = sum(n_combinations)

for i, a_i in enumerate(A):
    diff = n_c_2(n_balls[a_i - 1]) - n_c_2(n_balls[a_i - 1] - 1)
    print(total_combinations - diff)
### BUGGY CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
t = 10**9+7
for i in ln:
    r += k//A[i]
    r %= t
print(r)


### FIXED CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(300000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)
### BUGGY CODE ###

n = int(input())
list = list(map(int,input().split(" ")))
result = n
for i in range(n):
    for j in range(i+1):
        if list[i] > list[j]:
            result -= 1
            break
print(result)

### FIXED CODE ###

n = int(input())
list = list(map(int,input().split(" ")))
result = n
tem = list[0]
for i in range(n):
    if tem >= list[i]:
        tem = list[i]
    else:
        result -= 1

print(result)