Дано дерево. Кожній вершині дерева приписане певне ціле число. Для кожної вершини дерева необхідно знайти довжину найдовшої зростаючої послідовності чисел від кореня (вершини 1) до заданої вершини.

Формат вхідних даних

В першому рядку число \(N\) - кількість вершин дерева (\(1 \le N \le 2*10^5\))
В другому рядку \(N\) цілих чисел \(Ai\) - числа які записані на відповідних вершинах дерева (\(1 \le Ai \le 10^9\)).
В наступних \(N-1\) рядках міститься по 2 цілих числа - номера вершин дерева які з'єднані ребрами.

Формат вихідних даних

Для кожної вершини виведіть відповідь в окремому рядку.

Приклад вхідних даних

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Приклад вихідних даних

1
2
3
3
4
4
5
2
2
3