29037번 - Дерево 다국어

문제

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

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

입력

В первой строке входных данных дано число $n$ (1ドル \le n \le 10^5$) --- количество вершин в дереве.

Во второй строке даны $n$ чисел $x_i$ (1ドル \le x_i \le 10^9$) --- числа написанные на вершинах. На $i$-й вершине написано число $x_i$.

В следующих $n-1$-й строке идут пары чисел $a_i,ドル $b_i$ (1ドル \le a_i, b_i \le n$) --- рёбра в дереве.

출력

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

제한

힌트