City Maintenance

The country of Algorithm has $N$ cities and $N-1$ highways that connect them. Every city reaches every other city along the highways, directly or indirectly.

The country removes one city. When a city is removed, every highway attached to it disappears with it, and the removed city is no longer maintained.

Maintaining a city needs a maintenance machine. Each city has a minimum machine price. If a city's minimum price is $x$, only a machine that costs $x$ or more can maintain that city.

A machine moves only along highways. City maintenance is not urgent, so one machine is used for each set of cities that the remaining highways still connect to one another.

You run the company that builds the machines. Your revenue is the smallest cost of maintaining every remaining city. Write a program that prints the highest revenue that removing one city can produce.

The first line has a positive integer $N$ ($2 \le N \le 10^6$). The cities are numbered 1 through $N$.

The second line has the minimum machine price of city 1 through city $N$ in order, separated by spaces. Every price is a positive integer, and the sum of all prices is less than $2^{31}$.

Each of the next $N-1$ lines has the numbers of the two cities that one highway connects, separated by a space.

Print the highest revenue that removing one city can produce.