You are given a connected undirected graph with $n$ nodes and $n$ edges. Each node $i$ has an associated cost $a_i$.

A cut of the given graph is obtained by removing some edges in order to split the graph into exactly $2$ disjoint connected subgraphs.

If the sum of the costs of the nodes from the first subgraph is $s_1$ and the sum of the costs of the nodes from the second subgraph is $s_2$, then the cost of the cut is equal to $|s_1-s_2|$, where $|x|$ denotes the absolute value of $x$.

What is the smallest possible cost of a cut of the given graph?

Input

The first line of input contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of nodes and edges of the given graph.

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

The following $n$ lines contain the edges of the graph. Each line contains two integers, $u$ and $v$ ($1 \le u,v \le n, u \neq v$) — the endpoints of an edge.

It is guaranteed that there are no multiple edges and that the given graph is connected.

Output

Output a single integer, the minimum possible cost of a cut.

Example 1

stdin

3
1 7 3
1 2
2 3
3 1

stdout

3

Note

If we delete the edges $(1,2)$ and $(2,3)$, the resulting subgraphs will be $\{1,3\}$ and $\{2\}$. The cost of this cut is equal to $|a_1+a_3-a_2|=|4-7|=3$.

Example 2

stdin

5
1 7 3 3 6
3 5
5 4
1 4
4 2
2 5

stdout

2

Example 3

stdin

8
5 7 9 12 13 19 7 16
1 2
2 3
3 1
1 4
4 5
4 6
3 7
7 8

stdout

0