## 原始题面

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a tree with $$n$$ vertices numbered from $$1$$ to $$n$$. The height of the $$i$$-th vertex is $$h_i$$. You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency $$e$$ costs $$e$$ coins, where $$e > 0$$

It is considered that a vertex $$x$$ gets a signal if for some pair of towers at the vertices $$u$$ and $$v$$ ($$u \neq v$$, but it is allowed that $$x = u$$ or $$x = v$$) with efficiencies $$e_u$$ and $$e_v$$, respectively, it is satisfied that $$\min(e_u, e_v) \geq h_x$$ and $$x$$ lies on the path between $$u$$ and $$v$$

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices

### Input

The first line contains an integer $$n$$ ($$2 \le n \le 200\,000$$) — the number of vertices in the tree

The second line contains $$n$$ integers $$h_i$$ ($$1 \le h_i \le 10^9$$) — the heights of the vertices

Each of the next $$n- 1$$ lines contain a pair of numbers $$v_i, u_i$$ ($$1 \le v_i, u_i \le n$$) — an edge of the tree. It is guaranteed that the given edges form a tree

### Output

Print one integer — the minimum required number of coins Examples

### Note

In the first test case it's optimal to install two towers with efficiencies $$2$$ at vertices $$1$$ and $$3$$

In the second test case it's optimal to install a tower with efficiency $$1$$ at vertex $$1$$ and two towers with efficiencies $$3$$ at vertices $$2$$ and $$5$$

In the third test case it's optimal to install two towers with efficiencies $$6$$ at vertices $$1$$ and $$2$$

## 复杂度

$$O(n)$$

Show code