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"

#pragma warning(disable:4996)
using namespace std;
using ld = long double;
ld eps=1e-9;

int answer=-1e9;
vector<int> dfs(const vector<vector<int>>&edges, 
	const vector<int>&scores,
	const int now, const int from) {
	vector<int>ans(3,-1e9);
	ans[0]=scores[now];
	for (auto e : edges[now]) {
		if (e != from) {
			auto v = dfs(edges,scores, e, now);
			vector<int>nextans(ans);
			for (int l = 0; l < 3; ++l) {
				for (int r = 0; r < 3; ++r) {
					if (l + r <= 2) {
						if (r == 0) {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 2);
							if (l + r + 1 <= 2)nextans[l + r + 1] = max(nextans[l + r + 1],
								ans[l] + v[r] - 1);
						}
						else if (r == 1) {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 1);

						}
						else {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 2);
						}
					}
					
				}
			}
			ans=nextans;
		}
	}
	for (auto a : ans) {
		answer=max(answer,a);
	}
	return ans;
}
int main() {
	int N;cin>>N;
	vector<vector<int>>edges(N);
	vector<int>scores(N);
	for (int i = 0; i < N; ++i) {
		int a;cin>>a;
		scores[i]=a;

	}
	for (int i = 0; i < N - 1; ++i) {
		int a,b;cin>>a>>b;a--;b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	auto v=dfs(edges,scores,0,-1);
	cout<<answer<<endl;
	return 0;
}