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;

vector<int> graph[100010];
vector<int> tree[100010];

int mas[100010];
int n;

bool used[100010] = {};
void makeTree(int m){
  used[m] = true;
  for(int i = 0;i < graph[m].size();i++){
    if(!used[graph[m][i]]){
      tree[m].push_back(graph[m][i]);
      makeTree(graph[m][i]);
    }
  }
  return;
}

int dp[100010] = {};
int ep[100010] = {};
int fp[100010] = {};

void dfs(int x){
  dp[x] = mas[x];
  ep[x] = 0;
  fp[x] = 0;

  if(tree[x].size() == 0) return;

  for(int i = 0;i < tree[x].size();i++){
    dfs(tree[x][i]);
  }

  //bool used[100010] = {};
  memset(used,false,sizeof(used));
  for(int i = 0;i < tree[x].size();i++){
    if(dp[tree[x][i]] - 2 >= 0){
      used[tree[x][i]] = true;
      dp[x] += dp[tree[x][i]] - 2;
    }
  }

  int kari = 0;
  int kari2 = 0;
  for(int i = 0;i < tree[x].size();i++){
    if(used[tree[x][i]]){
      if(ep[tree[x][i]]+1 > kari){
        kari2 = kari;
        kari = ep[tree[x][i]]+1;
      }else if(ep[tree[x][i]]+1 > kari2){
        kari2 = ep[tree[x][i]]+1;
      }
    }else{
      if(ep[tree[x][i]]+1+dp[tree[x][i]]-2 > kari){
        kari2 = kari;
        kari = ep[tree[x][i]]+1+dp[tree[x][i]]-2;
      }else if(ep[tree[x][i]]+1+dp[tree[x][i]]-2 > kari2){
        kari2 = ep[tree[x][i]]+1+dp[tree[x][i]]-2;
      }
    }
  }

  if(kari >= 0){
    ep[x] = kari;
  }

  int kari3 = 0;
  for(int i = 0;i < tree[x].size();i++){
    if(used[tree[x][i]]){
      kari3 = max(kari3,fp[tree[x][i]]);
    }else{
      kari3 = max(kari3,fp[tree[x][i]]+dp[tree[x][i]]-2);
    }
  }

  fp[x] = max(kari3,max(kari+kari2,max(kari,kari2)));
  return;
}


int main(){
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> mas[i];
  }

  int a, b;
  for(int i = 0;i < n-1;i++){
    cin >> a >> b;
    a--; b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  makeTree(0);
  dfs(0);

  int ans = INT_MIN;
  for(int i = 0;i < n;i++){
    ans = max(ans,dp[i]+fp[i]);
  }

  cout << ans << endl;

  return 0;
}