나무

가이니 예프게니예비치는 오래전부터 나무를 갖고 싶어 했다. 요즘 유행하는 나무는 정점이 $n$개이고, 각 정점에는 수 $x_i$가 적혀 있다. 드디어 그는 그런 나무를 구입했다. 가게에서 돌아온 그는 이 나무에서 여러 값을 계산하기 시작했다. 모든 계산이 쉬웠지만, 정점 $u$와 $v$ 사이의 경로 $path(u, v)$를 골라 $length(path(u, v)) \cdot \min(x_u, x_v)$의 값을 최대로 만드는 문제에서 막혔다. 여기서 $length(path)$는 경로 $path$의 간선 개수이다. 며칠째 가이니 예프게니예비치는 밖에 나오지 않고 있다. 친구들이 걱정하며 이 문제를 풀도록 도와 달라고 부탁했다.

첫 번째 줄에 정점의 개수 $n$ ($1 \le n \le 10^5$)이 주어진다. 두 번째 줄에는 $n$개의 정수 $x_i$ ($1 \le x_i \le 10^9$)가 주어지며, $x_i$는 정점 $i$에 적힌 수이다. 이어서 $n-1$개의 줄에 나무의 간선을 나타내는 정수 쌍 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$)가 주어진다.

위 조건에서 설명한 값의 최댓값을 출력한다.