{"raw_statement":[{"iden":"problem statement","content":"We have a tree with $N$ vertices, whose $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$. Vertex $i$ has an integer $a_i$ written on it. For every integer $k$ from $1$ through $N$, solve the following problem:\n\n*   We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex $1$ to Vertex $k$, in the order they appear. Find the length of the longest increasing subsequence of this sequence.\n\nHere, the longest increasing subsequence of a sequence $A$ of length $L$ is the subsequence $A_{i_1} , A_{i_2} , ... , A_{i_M}$ with the greatest possible value of $M$ such that $1 \\leq i_1 < i_2 < ... < i_M \\leq L$ and $A_{i_1} < A_{i_2} < ... < A_{i_M}$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq a_i \\leq 10^9$\n*   $1 \\leq u_i , v_i \\leq N$\n*   $u_i \\neq v_i$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$:$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"10\n1 2 5 3 4 6 7 3 2 4\n1 2\n2 3\n3 4\n4 5\n3 6\n6 7\n1 8\n8 9\n9 10"},{"iden":"sample output 1","content":"1\n2\n3\n3\n4\n4\n5\n2\n2\n3\n\nFor example, the sequence $A$ obtained from the shortest path from Vertex $1$ to Vertex $5$ is $1,2,5,3,4$. Its longest increasing subsequence is $A_1, A_2, A_4, A_5$, with the length of $4$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}