import sys

import numpy as np

import numba

from numba import njit, b1, i4, i8

from numba.types import Omitted



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



@njit((i8[:, :], ), cache=True)

def to_undirected(G):

    N = len(G)

    G = np.vstack((G, G))

    G[N:, 0] = G[:N, 1]

    G[N:, 1] = G[:N, 0]

    ind = G[:, 0].argsort()

    return G[ind]



@njit([(i8, i8[:, :], i8[:], i8), (i8, i8[:, :], i8[:], Omitted(1))],

      cache=True)

def euler_tour(N, G, ind, root=1):

    parent = np.zeros(1 + N, np.int64)

    tour = np.zeros(N + N, np.int64)

    st = np.empty(len(G) + 10, np.int64)

    p = 0



    def add(v):

        nonlocal p

        st[p] = v

        p += 1



    def pop():

        nonlocal p

        p -= 1

        return st[p]



    add(-root)

    add(root)

    n = 0

    while p:

        v = pop()

        tour[n] = v

        n += 1

        if v > 0:

            for i in range(ind[v - 1], ind[v]):

                w = G[i, 1]

                if w == parent[v]:

                    continue

                add(-w)

                add(w)

                parent[w] = v

    return tour, parent



@njit((i8, i8[:], i8[:, :]), cache=True)

def main(N, A, G):

    G = to_undirected(G)

    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')

    tour, parent = euler_tour(N, G, ind)

    INF = 1 << 60

    reverse = np.empty((N + 1, 2), np.int64)

    dp = np.full(N + 1, INF, np.int64)

    ans = np.empty(N + 1, np.int64)

    for v in tour:

        if v > 0:

            i = np.searchsorted(dp, A[v])

            reverse[v] = i, dp[i]

            dp[i] = A[v]

            ans[v] = np.searchsorted(dp, INF)

        else:

            v = -v

            i, x = reverse[v]

            dp[i] = x

    return ans[1:]



N = int(readline())

A = np.array([0] + readline().split(), np.int64)

G = np.array(read().split(), np.int64).reshape(-1, 2)



ans = main(N, A, G)

print(('\n'.join(map(str, ans.tolist()))))
import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



def to_undirected(G):

    N = len(G)

    G = np.vstack((G, G))

    G[N:, 0] = G[:N, 1]

    G[N:, 1] = G[:N, 0]

    ind = G[:, 0].argsort()

    return G[ind]



def euler_tour(N, G, ind, root):

    parent = np.zeros(1 + N, np.int64)

    tour = np.zeros(N + N, np.int64)

    st = np.empty(len(G) + 10, np.int64)

    p = 0



    def add(v):

        nonlocal p

        st[p] = v

        p += 1



    def pop():

        nonlocal p

        p -= 1

        return st[p]



    add(-root)

    add(root)

    n = 0

    while p:

        v = pop()

        tour[n] = v

        n += 1

        if v > 0:

            for i in range(ind[v - 1], ind[v]):

                w = G[i, 1]

                if w == parent[v]:

                    continue

                add(-w)

                add(w)

                parent[w] = v

    return tour, parent



def main(N, A, G):

    G = to_undirected(G)

    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')

    tour, parent = euler_tour(N, G, ind, 1)

    INF = 1 << 60

    reverse = np.empty((N + 1, 2), np.int64)

    dp = np.full(N + 1, INF, np.int64)

    ans = np.empty(N + 1, np.int64)

    for v in tour:

        if v > 0:

            i = np.searchsorted(dp, A[v])

            reverse[v] = i, dp[i]

            dp[i] = A[v]

            ans[v] = np.searchsorted(dp, INF)

        else:

            v = -v

            i, x = reverse[v]

            dp[i] = x

    return ans[1:]



if sys.argv[-1] == 'ONLINE_JUDGE':

    import numba

    from numba.pycc import CC

    i4 = numba.int32

    i8 = numba.int64

    cc = CC('my_module')



    def cc_export(f, signature):

        cc.export(f.__name__, signature)(f)

        return numba.njit(f)



    to_undirected = cc_export(to_undirected, (i8[:, :], ))

    euler_tour = cc_export(euler_tour, (i8, i8[:, :], i8[:], i8)) 

    main = cc_export(main, (i8, i8[:], i8[:, :]))

    cc.compile()



from my_module import main



N = int(readline())

A = np.array([0] + readline().split(), np.int64)

G = np.array(read().split(), np.int64).reshape(-1, 2)



ans = main(N, A, G)

print(('\n'.join(map(str, ans.tolist()))))
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit((i8[:, :],), cache=True)
def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]


@njit([(i8, i8[:, :], i8[:], i8), (i8, i8[:, :], i8[:], Omitted(1))], cache=True)
def euler_tour(N, G, ind, root=1):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent


@njit((i8, i8[:], i8[:, :]), cache=True)
def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), "right")
    tour, parent = euler_tour(N, G, ind)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]


N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)
ans = main(N, A, G)
print(("\n".join(map(str, ans.tolist()))))

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]


def euler_tour(N, G, ind, root):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent


def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), "right")
    tour, parent = euler_tour(N, G, ind, 1)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]


if sys.argv[-1] == "ONLINE_JUDGE":
    import numba
    from numba.pycc import CC

    i4 = numba.int32
    i8 = numba.int64
    cc = CC("my_module")

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    to_undirected = cc_export(to_undirected, (i8[:, :],))
    euler_tour = cc_export(euler_tour, (i8, i8[:, :], i8[:], i8))
    main = cc_export(main, (i8, i8[:], i8[:, :]))
    cc.compile()
from my_module import main

N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)
ans = main(N, A, G)
print(("\n".join(map(str, ans.tolist()))))

-import numba -from numba import njit, b1, i4, i8 -from numba.types import Omitted -@njit((i8[:, :],), cache=True) -@njit([(i8, i8[:, :], i8[:], i8), (i8, i8[:, :], i8[:], Omitted(1))], cache=True) -def euler_tour(N, G, ind, root=1): +def euler_tour(N, G, ind, root): -@njit((i8, i8[:], i8[:, :]), cache=True) -    tour, parent = euler_tour(N, G, ind) +    tour, parent = euler_tour(N, G, ind, 1) +if sys.argv[-1] == "ONLINE_JUDGE": +    import numba +    from numba.pycc import CC + +    i4 = numba.int32 +    i8 = numba.int64 +    cc = CC("my_module") + +    def cc_export(f, signature): +        cc.export(f.__name__, signature)(f) +        return numba.njit(f) + +    to_undirected = cc_export(to_undirected, (i8[:, :],)) +    euler_tour = cc_export(euler_tour, (i8, i8[:, :], i8[:], i8)) +    main = cc_export(main, (i8, i8[:], i8[:, :])) +    cc.compile() +from my_module import main +