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>
using namespace std;
using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> c(n);
  for(Int i=0;i<n;i++) cin>>c[i];
  
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  
  const Int INF = 1e9;
  Int ans=-INF;
  vector<Int> dp1(n,-INF),dp2(n,-INF),dp3(n,-INF);
  
  function<void(Int, Int)> dfs=
    [&](Int v,Int p){
      for(Int u:G[v]) if(u!=p) dfs(u,v);
      
      Int res=0;
      vector<Int> w;
      for(Int u:G[v]){
	if(u==p) continue;
	res+=max(0LL,dp2[u]-2);
	w.emplace_back((dp1[u]-1)-max(0LL,dp2[u]-2));	
      }
	
      for(Int u:G[v]){
	if(u==p) continue;
	chmax(dp1[v],c[v]+res+(dp1[u]-1)-max(0LL,dp2[u]-2));
	chmax(dp3[v],c[v]+res+(dp3[u]-2)-max(0LL,dp2[u]-2));
      }
      sort(w.rbegin(),w.rend());
      
      chmax(dp1[v],c[v]+res);
      chmax(dp2[v],c[v]+res);      
      if(w.size()>1u) chmax(dp3[v],c[v]+res+w[0]+w[1]);

      chmax(ans,dp1[v]);
      chmax(ans,dp2[v]);
      chmax(ans,dp3[v]);      
    };
  
  dfs(0,-1);
  cout<<ans<<endl;
  return 0;
}