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 i64 = long long;

vector<i64> p;
vector<vector<i64>> G;

vector<i64> go;
vector<i64> ba;

void dfs(i64 v, i64 f) {
  i64 DIFF = 0;
  i64 SUM = 0;
  for(auto x: G[v]) {
    if(x == f) continue;
    dfs(x, v);
    if(ba[x] - 2 <= 0) {
      DIFF = max(DIFF, go[x] - 1);
    }
    else {
      SUM += ba[x] - 2;
      DIFF = max(DIFF, go[x] - 1 - (ba[x] - 2));
    }
  }
  ba[v] = SUM + p[v];
  go[v] = SUM + DIFF + p[v];

  //cout << v << " " << ba[v] << " " << go[v] << endl;
}

vector<i64> ans;

void rerooting(i64 v, i64 f, i64 fgo, i64 fba) {
  vector<pair<i64, i64>> diff;
  diff.push_back({ 0, -1 });
  i64 SUM = 0;
  i64 DIFF = 0;
  for(auto x: G[v]) {
    i64 g, b;
    if(x == f) {
      g = fgo;
      b = fba;
    }
    else {
      g = go[x];
      b = ba[x];
    }
    if(b - 2 <= 0) {
      DIFF = max(DIFF, g - 1);
      diff.push_back({ g - 1, x });
    }
    else {
      SUM += b - 2;
      DIFF = max(DIFF, g - 1 - (b - 2));
      diff.push_back({ g - 1 - (b - 2), x });
    }
  }
  ans[v] = SUM + DIFF + p[v];
  sort(begin(diff), end(diff));
  reverse(begin(diff), end(diff));
  for(auto x: G[v]) {
    if(x == f) continue;
    i64 s = SUM;
    if(ba[x] - 2 > 0) {
      s -= ba[x] - 2;
    }
    i64 g = s;
    if(diff.front().second != x) {
      g += diff.front().first;
    }
    else {
      g += diff[1].first;
    }
    rerooting(x, v, g + p[v], s + p[v]);
  }
}

int main() {
  i64 N;
  cin >> N;
  p.resize(N);
  ans.resize(N);
  for(i64 i = 0;i < N;i++) cin >> p[i];
  G.resize(N);
  for(i64 i = 0;i < N - 1;i++) {
    i64 s, t;
    cin >> s >> t;
    s--;
    t--;
    G[s].push_back(t);
    G[t].push_back(s);
  }
  go.resize(N, -1e18);
  ba.resize(N, -1e18);
  dfs(0, -1);
  rerooting(0, -1, 0, 0);
  cout << *max_element(begin(ans), end(ans)) << endl;
}