Дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
tree.in
вывод
tree.out

Гений Евгеньевич давно мечтал о дереве. Сейчас в моде деревья с n вершинами, на каждой из которых написано число xi. Долгожданный день настал, и Гений Евгеньевич смог себе приобрести такое дерево. Вернувшись из магазина после покупки, он начал считать различные величины на этом дереве. Все ему давалось очень просто, пока он не решил найти путь в этом дереве, значение величины length(path(u, v)) * min(xu, xv) для которого максимально. Здесь path(u, v) — путь между вершинами u и v, length(path) — длина пути path в ребрах.

Уже который день Гений Евгеньевич не выходит на улицу. Его друзья, естественно, начали волноваться. Они просят Вас помочь Гению Евгеньевичу справиться с задачей.

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

В первой строке входных данных дано число n (1 ≤ n ≤ 105) — количество вершин в дереве.

Во второй строке даны n чисел xi (1 ≤ xi ≤ 109) — числа написанные на вершинах. На i-й вершине написано число xi.

В следующих n - 1-й строке идут пары чисел ai, bi (1 ≤ ai, bi ≤ n) — рёбра в дереве.

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

Выведите максимальное значение величины, описанной в условии.

Примеры тестов

Входные данные
8
9 2 8 8 7 2 1 2
2 1
3 1
4 1
5 2
6 4
7 5
8 5
Выходные данные
21