J. Jovial Jaunt
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jack the jolly jester lives on an undirected tree with $$$n$$$ vertices, conveniently numbered $$$1$$$ through $$$n$$$. At the $$$i$$$-th ($$$1 \le i \le n$$$) vertex, there is a jazz jellyfish with a jubilance value of $$$a_i$$$.

Jack plans to take a jovial jaunt throughout the joyful junctions. He will choose a starting vertex $$$s$$$ and an ending vertex $$$e$$$, then walk along the unique path from $$$s$$$ to $$$e$$$. It is allowed for $$$s=e$$$.

Let the vertices he visits be $$$v_1, v_2, \ldots, v_{\ell}$$$ in order (so $$$v_1 = s$$$ and $$$v_{\ell} = e$$$). Because Jack is a perfectly normal human, the total jubilance he gets from walking through this path is defined in the most natural possible way. It will be $$$f(a_{v_1}, a_{v_2}, \ldots, a_{v_{\ell}})$$$, where $$$f$$$ is defined as follows:

  • $$$f(x_1) = x_1$$$.
  • $$$f(x_1, x_2) = \max{(x_1, x_2)} + \left\lfloor\sqrt{\min{(x_1, x_2)}}\right\rfloor$$$.
  • For $$$k \gt 2$$$, $$$f(x_1, x_2, \ldots, x_k) = f(f(x_1,\ldots, x_{k-1}), x_k)$$$.

Note that the path from $$$s$$$ to $$$e$$$ may have a different weight from the path from $$$e$$$ to $$$s$$$ — we consider these paths to be distinct.

Find the maximum possible jubilance over all paths in the tree.

Input

The first line contains a single integer $$$n$$$, the number of vertices in the tree ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the labels of the vertices ($$$1 \le a_i \le 10^9$$$).

The next $$$n-1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$, the edges of the graph ($$$1 \le u_i, v_i \le n$$$).

Output

Print a single integer — the maximum jubilance of a path in the tree.

Examples
Input
3
3 2 3
1 2
1 3
Output
5
Input
5
2 3 3 2 3
3 2
5 2
3 4
4 1
Output
7
Note

In the first test case, the path from vertex $$$2$$$ to vertex $$$3$$$ has jubilance $$$5$$$. We can show that no path with greater weight exists.

In the second test case, the path from vertex $$$5$$$ to vertex $$$1$$$ has jubilance $$$7$$$. We can show that no path with greater weight exists.