Вам задано кореневе дерево з вершинами. Вершини пронумеровані від до , а коренем є вершина . -те ребро з’єднує вершини u_i та v_i. У вершині записано ціле число a_v.
Для кожної вершини знайдіть максимальне значення , для якого існує таке число , що всі значення x, x + 1, \dots, x + m - 1 присутні на шляху від кореня до вершини .
У першому рядку задано ціле число — кількість вершин дерева.
У другому рядку задано цілих чисел a_v, записаних у вершинах дерева.
У наступних n - 1 рядках задано по два цілі числа u_i, v_i — кінці -го ребра.
1 \le n \le 3 \cdot 10^5,
0 \le a_v \le 10^9,
1 \le u_i, v_i \le n.
В одному рядку виведіть цілих чисел — максимальне значення для кожної вершини , де 1 \le v \le n.
Example
Example 1
Перший приклад
У першому прикладі відповіді для всіх вершин є такими.
Вершина . Оскільки коренем є вершина , шлях від кореня до вершини містить лише одну вершину. У цьому випадку m = 1.
Вершина . Шлях від кореня до вершини містить дві вершини — та — зі значеннями та відповідно. Знову ж таки, m = 1.
Вершина . Шлях від кореня до вершини містить дві вершини — та — зі значеннями та відповідно. Для вершини відповідь дорівнює m = 1.
Вершина . Шлях від кореня до вершини містить три вершини — , та — зі значеннями , та відповідно. У цьому випадку відповідь дорівнює m = 3, оскільки для x = 2 на шляху присутні значення x = 2, x + 1 = 3 та x + 2 = 4.
Вершина . Шлях від кореня до вершини містить три вершини — , та — зі значеннями , та відповідно. У цьому випадку відповідь дорівнює m = 2, оскільки для x = 4 на шляху присутні значення x = 4 та x + 1 = 5.
Другий приклад