C. Almost Tree Cut
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 the 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.

Examples
Input
3
1 7 3
1 2
2 3
3 1
Output
3
Input
5
1 7 3 3 6
3 5
5 4
1 4
4 2
2 5
Output
2
Input
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
Output
0
Note

Explanation of the first testcase:

  • 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$$$.