Problem: Bob is playing a game called "Dungeon 2" which is the sequel to the popular "Dungeon" released last year. The game is played on a map consisting of $N$ rooms and $N-1$ roads connecting them. The roads allow bidirectional traffic and the player can start his tour from any room and reach any other room by way of multiple of roads. A point is printed in each of the rooms.

Bob tries to accumulate the highest score by visiting the rooms by cleverly routing his character "Tora-Tora." He can add the point printed in a room to his score only when he reaches the room for the first time. He can also add the points on the starting and ending rooms of Tora-Tora’s journey. The score is reduced by one each time Tora-Tore passes a road. Tora-Tora can start from any room and end his journey in any room.

Given the map information, make a program to work out the maximum possible score Bob can gain.



Input

The input is given in the following format.


$N$
$p_1$
$p_2$
$...$
$p_N$
$s_1$ $t_1$
$s_2$ $t_2$
$...$
$s_{N-1}$ $t_{N-1}$


The first line provides the number of rooms $N$ ($1 \leq N \leq 100,000$). Each of the subsequent $N$ lines provides the point of the $i$-th room $p_i$ ($-100 \leq p_i \leq 100$) in integers. Each of the subsequent lines following these provides the information on the road directly connecting two rooms, where $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) represent the numbers of the two rooms connected by it. Not a single pair of rooms are connected by more than one road.

Output

Output the maximum possible score Bob can gain.

Examples

Input

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


Output

10


Input

4
5
0
1
1
1 2
2 3
2 4


Output

5

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
static const int N_MAX=100000;
static const int NINF=-1000000000;
int N,P[N_MAX],ans;
int dp[N_MAX][3];//0:1p,1:0p,2:2p
vector<int> T[N_MAX];
bool V[N_MAX];

void dfs(int u){
	V[u]=true;
	vector<int> C;
	rep(i,T[u].size()){
		int v=T[u][i];
		if(!V[v]){
			C.push_back(v);
			dfs(v);
		}
	}
	//子cがすべて訪問・決定済み
	
	if(C.size()==0){
		rep(i,3)dp[u][i]=P[u];
	}else if(C.size()==1){
		int v=C[0];
		dp[u][0]=max(dp[v][0]-1+P[u],P[u]);
		dp[u][1]=max(dp[v][1]-2+P[u],P[u]);
		dp[u][2]=max(dp[v][2]-2+P[u],P[u]);
	}else{
		int a1,a2,c1;//candidate child
		a1=a2=c1=C[0];
		rep(i,C.size()){
			int v=C[i];
			if(dp[a1][0]-1-max(dp[a1][1]-2,0)<=dp[v][0]-1-max(dp[v][1]-2,0))a1=v;
			if(dp[c1][2]-2-max(dp[c1][1]-2,0)<=dp[v][2]-2-max(dp[v][1]-2,0))c1=v;
		}
		rep(i,C.size())if(C[i]!=a1){a2=C[i];break;}
		rep(i,C.size()){
			int v=C[i];
			if(v==a1)continue;
			if(dp[a2][0]-1-max(dp[a2][1]-2,0)<=dp[v][0]-1-max(dp[v][1]-2,0))a2=v;
		}
		int sumA1=0;//bbbbab
		int sumB1=0;//bbbbbb
		int sumC1=0;//bbbcbb
		int sumC2=0;//abbabb
		for(int i=0;i<C.size();i++){
			int v=C[i];
			sumA1+=(v==a1)?(dp[v][0]-1):max(dp[v][1]-2,0);
			sumB1+=max(dp[v][1]-2,0);
			sumC1+=(v==c1)?(dp[v][2]-2):max(dp[v][1]-2,0);
			sumC2+=(v==a1||v==a2)?(dp[v][0]-1):max(dp[v][1]-2,0);
		}
		int sumA=sumA1;
		int sumC=max(sumC1,sumC2);
		int sumB=sumB1;
		dp[u][0]=max(P[u],sumA+P[u]);
		dp[u][1]=max(P[u],sumB+P[u]);
		dp[u][2]=max(P[u],sumC+P[u]);
	}
	rep(i,3)ans=max(ans,dp[u][i]);
}
int solve(int s){
	rep(i,N)rep(j,3)dp[i][j]=NINF;
	rep(i,N)V[i]=false;
	ans=NINF;
	dfs(s);
	return ans;
}

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>P[i];	
	}
	for(int i=0;i<N-1;i++){
		int s,t;cin>>s>>t;
		s--;t--;
		T[s].push_back(t);
		T[t].push_back(s);
	}
	
	int a=solve(0);
	cout<<a<<endl;
	return 0;
}