Задано дерево с n вершинами, i - ое ребро которого соединяет вершину ui и вершину vi. На вершине i написано целое число ai. Для каждого целого числа k от 1 до n решите следующую задачу:

Составим последовательность, выстроив целые числа, записанные в вершинах кратчайшего пути от вершины 1 до вершины k, в порядке их появления. Найдите длину наибольшей возрастающей подпоследовательности этой последовательности.

Здесь наибольшая возрастающая подпоследовательность последовательности A длины L - это подпоследовательность Ai1, Ai2, ..., Aim с таким наибольшим возможным значением m, что 1 ≤ i1 < i2 < ...< im ≤ L и Ai1 < Ai2 < ... < Aim.

Входные данные

Первая строка содержит число n (2 ≤ n ≤ 2 * 105). Вторая строка содержит числа a1, a2, ..., an (1 ≤ ai ≤ 109). Каждая из следующих n - 1 строк содержит ребро (ui, vi) (1 ≤ ui, vi ≤ n).

Выходные данные

Выведите n строк. В k - ой строке выведите длину наибольшей возрастающей подпоследовательности для последовательности, полученной из кратчайшего пути от вершины 1 до вершины k.