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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	Zero,
	One,
	Two,
};

struct Info{
	Info(int arg_node_id,int arg_diff){
		node_id = arg_node_id;
		diff = arg_diff;
	}
	bool operator<(const struct Info & arg) const{
		return diff < arg.diff;
	}
	int node_id,diff;
};

int N;
int point[NUM];
int value[NUM][3];
vector<int> G[NUM];


void dfs(int node_id,int parent){

	int tmp_value = point[node_id];
	int child,tmp;

	for(int i = 0; i < G[node_id].size(); i++){

		child = G[node_id][i];
		if(child == parent)continue;

		dfs(child,node_id);

		tmp = value[child][Zero]-2;

		if(tmp >= 0){
			tmp_value += tmp;
		}
	}

	value[node_id][Zero] = tmp_value;

	priority_queue<Info> Q;

	for(int i = 0; i < G[node_id].size(); i++){

		child = G[node_id][i];
		if(child == parent)continue;

		Q.push(Info(child,(value[child][One]-1)-max(0,value[child][Zero]-2)));
	}

	value[node_id][One] = value[node_id][Zero];

	if(Q.empty() == false && Q.top().diff > 0){

		value[node_id][One] += Q.top().diff;
		Q.pop();

		if(Q.empty() == false && Q.top().diff > 0){
			value[node_id][Two] = value[node_id][One]+Q.top().diff;
		}
	}

	for(int i = 0; i < G[node_id].size(); i++){

		child = G[node_id][i];
		if(child == parent)continue;

		if(value[node_id][Two] < value[node_id][Zero]+(value[child][Two]-2)-max(0,value[child][Zero]-2)){
			value[node_id][Two] = value[node_id][Zero]+(value[child][Two]-2)-max(0,value[child][Zero]-2);
		}
	}
}

int main(){

	scanf("%d",&N);

	for(int i = 0; i < NUM; i++){
		value[i][Zero] = 0;
		value[i][One] = -BIG_NUM;
		value[i][Two] = -BIG_NUM;
	}

	for(int i = 0; i < N; i++){
		scanf("%d",&point[i]);
	}

	int from,to;

	for(int loop = 0; loop < N-1; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;
		G[from].push_back(to);
		G[to].push_back(from);
	}

	queue<int> Q;
	for(int i = 0; i < N; i++){
		if(G[i].size() == 0){
			Q.push(i);
		}
	}

	dfs(0,-1);
	int ans = -BIG_NUM;

	for(int i = 0; i < N; i++){
		ans = max(ans,max(value[i][Zero],max(value[i][One],value[i][Two])));
	}

	printf("%d\n",ans);

	return 0;
}