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;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, dp0[110000], dp1[110000], dp2[110000], ndp2[110000], p[110000], ans = MINF;
vector<ll> g[110000];

void dfs(ll v, ll par){
    vector<ll> s0, s1, s2;
    REP(i, g[v].size()){
        ll w = g[v][i];
        if (w == par) continue;
        dfs(w, v);
        if(dp0[w] - 2 > 0) dp0[v] += dp0[w] - 2;
        s0.push_back(dp0[w] - 2);
        s1.push_back(dp1[w] - 1);
        s2.push_back(dp2[w] - 2);
    }
    //dp1
    REP(i, s0.size()){
        if (s0[i] >= 0) dp1[v] += s0[i];
    }
    ll dp1ma = 0;
    REP(i, s0.size()){
        if (s0[i] >= 0) dp1ma = max(dp1ma, s1[i] - s0[i]);
        else dp1ma = max(dp1ma, s1[i]);
    }
    dp1[v] += dp1ma;

    //dp2 * 1
    REP(i, s0.size()){
        if (s0[i] >= 0) ndp2[v] += s0[i];
    }
    ll dp2ma = 0;
    REP(i, s0.size()){
        if (s0[i] >= 0) dp2ma = max(dp2ma, s2[i] - s0[i]);
        else dp2ma = max(dp2ma, s2[i]);
    }
    ndp2[v] += dp2ma;

    //dp1 * 2
    vector<ll> d2;
    REP(i, s0.size()){
        if (s0[i] >= 0) dp2[v] += s0[i];
    }
    REP(i, s0.size()){
        if (s0[i] >= 0) d2.push_back(s1[i] - s0[i]);
        else d2.push_back(s1[i]);
    }
    sort(ALL(d2), greater<ll>());
    REP(i, min(2ll, (ll)d2.size())){
        if(d2[i] > 0) dp2[v] += d2[i];
    }
    dp2[v] = max(dp2[v], ndp2[v]);
    dp0[v] += p[v];
    dp1[v] += p[v];
    dp2[v] += p[v];
    ans = max({ans, dp0[v], dp1[v], dp2[v]});
}
int main(){
    cin >> n;
    REP(i, n)cin >> p[i];
    REP(i, n - 1){
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    cout << ans << endl;
}