Tree

Genius Evgenievich has long wanted a tree. Trees with $n$ vertices are fashionable now, and each vertex has a number $x_i$ written on it. The long-awaited day came, and Genius Evgenievich bought such a tree. After returning from the store, he began computing various values on it. Everything was easy for him until he tried to find a path in this tree whose value $length(path(u, v)) \cdot \min(x_u, x_v)$ is maximal. Here $path(u, v)$ is the path between vertices $u$ and $v$, and $length(path)$ is the length of the path $path$ in edges. For many days now, Genius Evgenievich has not gone outside. His friends, naturally, have started to worry. They ask you to help Genius Evgenievich solve this problem.

The first line contains one integer $n$ ($1 \le n \le 10^5$), the number of vertices in the tree. The second line contains $n$ integers $x_i$ ($1 \le x_i \le 10^9$), where $x_i$ is the number written on vertex $i$. Each of the following $n-1$ lines contains a pair of integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$), an edge of the tree.

Print the maximum value of the quantity described in the statement.