C. Trains 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Maxim flew to Korea and wanted to attend the fireworks festival in Busan.

The Korean train system is represented by a tree of $$$n$$$ vertices. Train routes are bidirectional, and each trip requires $$$1$$$ ticket.

Maxim starts his journey from vertex $$$1$$$ and needs to reach vertex $$$n$$$. While at vertex $$$i$$$, he can buy any number of tickets for $$$a_i$$$ won.

Find the minimum number of won needed for Maxim to reach vertex $$$n$$$ from vertex $$$1$$$.

Input

The first line contains the number $$$n$$$ $$$(2 \leq n \leq 2\cdot 10^{5})$$$ — the number of vertices in the tree.

The second line contains $$$n$$$ numbers — the array $$$a$$$ $$$(1 \leq a_i \leq 10^6)$$$. $$$a_i$$$ — the price of one ticket at vertex $$$i$$$.

The next $$$n-1$$$ lines contain $$$2$$$ numbers each: $$$v_i, u_i$$$ — the ends of the train routes.

Output

Output the minimum amount of money needed for Maxim to reach vertex $$$n$$$ from vertex $$$1$$$.

Examples
Input
6
100 10 5 4 100 10
1 2
2 3
3 4
1 5
5 6
Output
130
Input
7
8 1 5 7 9 4 3
1 2
1 3
2 4
3 5
1 6
2 7
Output
9
Input
9
1000 100 30 100 10 1000 1000 1000 10
1 2
2 3
2 4
4 5
1 6
6 7
7 8
8 9
Output
1260