Problem Statement

You are given a tree consisting of $N$ nodes rooted at

node $1.$ A tree is a connected acyclic graph. Each

node has some value attached to it$.$ Let's say the

value attached to node $u$ is $A_u.$

Let's denote Path$($u$)$ to be an array of values of all

the nodes on the path from the root to $u$ in the

increasing order of the node's distance from the root.

For every node $u$ between $1$ to $N,$ you have $10$ find

the length of the longest non$-$decreasing

subsequence in Path$(u).$

Input Format

The first line contains a single integer $N.$

The second line contains $N$ space$-$separated

integers denoting the values attached to each

node of the tree.

Next N$-1$ lines contain $2$ space$-$separated

integers each denoting the endpoints of the

edges of the tree. Each edge is present only

once. the length of the longest non$-$decreasing

subsequence in Path$($u$).$

Input Format

The first line contains a single integer $N.$

The second line contains $N$ space$-$separ.

integers denoting the values attached to

node of the tree.

Next N$-1$ lines contain $2$ space$-$separateu

integers each denoting the endpoints of the

edges of the tree. Each edge is present only

once.

Constraints

$1N{10}^5$

$1A_u{10}^6,$ for every $1uN$

Output Format

You have to output $N$ space$-$separated integers, $i^{th}$

integer denotes the answer for $i^{th}$ node.

Sample Test Case

Input

$5,$

$1,2,3,2,3$

$1,2,$

$1,3,$ once.

Constraints

$1N{10}^5$

$1A_u{10}^6,$ for every $1u1$

Output Format

You have to output $N$ space$-$separated integel

integer denotes the answer for $i^{th}$ node.

Sample Test Case

Input

Output

$12223$

Explanation

Path$(1)=[1],$ so the length of longest non

decreasing subsenuence is $1$

Pah$(2)-41\mathrm{.}21$ sothelengih of longest mon $5$

$12323$

$12$

$13$

$34$

$35$

Output

$12223$

Explanation

Path $(1)=[1],$ so the length of longest non

decreasing subsequence is $1.$

Path$(2)=[1,2],$ so the length of longest non

decreasing subsequence is $2.$

Path $(3)=[1,3],$ so the length of longest non

decreasing subsequence is $2.$

Path $(4)=[1,3,2],$ so the length of longest non

decreasing subsequence is $2.$

Path$(5)=[1,3,3],$ so the length of longest non

decreasing subsequence is $3.$

Execution time limit

$2$ seconds