LIS on Tree
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:
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.
Here, the longest increasing subsequence of a sequence A of length L is the subsequence A[i1], A[i2], ..., A[im] with the greatest possible value of m such that 1 ≤ i[1] < i[2] < ...< i[m] ≤ L and A[i1] < A[i2] < ... < A[im].
Input
The first line contains number n (2 ≤ n ≤ 2 * 10^5). The second line contains numbers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9). Each of the next n - 1 lines contains an edge (u[i], v[i]) (1 ≤ u[i], v[i] ≤ n).
Output
Print n lines. In the k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.
