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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

vector<int> way[SIZE];
int point[SIZE];
int ans = -INF;

pair<pair<int,int>,int> dfs(int now, int back = -1){
  vector<int> vec, vec2;
  int sum = 0;
  
  for(int i=0;i<way[now].size();i++){
    if(way[now][i] == back) continue;
    auto p = dfs(way[now][i], now);
    vec.push_back(p.first.first - p.first.second);
    vec2.push_back(p.second - p.first.second);
    sum += p.first.second;
  }

  vec.push_back(0);
  vec.push_back(0);
  vec2.push_back(0);
  sort(vec.begin(), vec.end(), greater<int>());
  sort(vec2.begin(), vec2.end(), greater<int>());

  ans = max(ans, sum + vec[0] + vec[1] + point[now]);
  ans = max(ans, sum + vec2[0] + point[now]);
  
  return {{max(0, sum + vec[0] + point[now] - 1), max(0, sum + point[now] - 2)},
      max({0, sum + vec[0] + vec[1] + point[now] - 2, sum + vec2[0] + point[now] - 2})};
}

int main(){
  int n;

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

  for(int i=0;i<n-1;i++){
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    way[a].push_back(b);
    way[b].push_back(a);
  }

  dfs(0);

  printf("%d\n", ans);
  
  return 0;
}