Bajtocia is preparing to launch her first rocket into space. Bajtazar is one of the employees of the space program and is responsible for the process of boarding astronauts into the rocket. The interior of the rocket consists of $n$ cabins connected by bidirectional corridors in such a way that between any two cabins there is exactly one way to walk (if we do not turn back along the way). Traversing any corridor takes one Bajtocian second. The cabins are numbered from $1$ to $n$. The entrance to the rocket leads to cabin number $1$.

There will be $n$ astronauts boarding the rocket, also numbered from $1$ to $n$. For each $1 \le i \le n$, astronaut number $i$ will live in cabin number $i$. The astronauts enter the rocket one after another at one-second intervals (in Bajtocian seconds) and walk along the shortest path to their cabin. After astronaut $i$ reaches their cabin, they start unpacking their belongings, which takes exactly $a_i$ Bajtocian seconds.

The boarding order must be such that nobody has to pass through a cabin whose resident is already inside (regardless of whether that resident has already finished unpacking or not).

Bajtazar’s task is to plan the boarding process so that it finishes as quickly as possible, i.e., so that as little time as possible passes between the moment the first astronaut enters the rocket and the moment when all astronauts have finished unpacking.

Input

The first line of input contains an integer $n$ ($2 \le n \le 500,000$), the number of astronauts and the number of cabins. The second line contains a sequence of $n$ integers $a_i$ ($1 \le a_i \le 10^9$). The value $a_i$ specifies how much time astronaut number $i$ needs to unpack. The next $n - 1$ lines describe the layout of cabins in the rocket. Each of them contains two integers $a$ and $b$ ($1 \le a, b \le n$), meaning that cabins $a$ and $b$ are directly connected by a corridor.

Output

Print the minimum time needed for all astronauts to enter the rocket and settle into their cabins.

Example

For the input data:

5
2 3 5 2 1
2 1
3 2
2 4
1 5

the correct output is:

7