问题描述

给定一棵带点权的树，对于树上的一条路径，设路径包含的点数为P ，路径上的最大点权为Max ，最小点权为Min。请找一条路径使得P-Max+Min最小，输出这个最小值。

Input

第一行输入一个整数N 表示树的点数。

接下来一行N 个整数ai 表示 i 号点的权值。

接下来N− 1对整数xi , yi 表示xi , yi 之间存在一条边

Output

输出一个数表示最小值。

Examples

输入样例1:

5 

2 1 4 4 1  

3 2 

1 2 

5 2 

4 5

输出样例1:

-1

输入样例2:

5 

2 3 3 3 1  

1 4 

5 1 

5 3 

3 2

输出样例2:

0

输入样例3:

6 

5 1 1 6 4 5  

2 5 

1 6 

4 3 

3 1 

5 1

输出样例3:

-3

Notes

前 60%的测试数据满足N≤ 1000 ;

全部测试数据满足1 ≤ N ≤ 10^6 , 1 ≤ai≤ 10^9