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 = int64_t;

const i64 MOD = 1e9 + 7;


signed main(){
    i64 n;
    cin >> n;
    vector<i64> a(n);
    for(auto& x : a)
        cin >> x;
    vector<vector<i64>> edges(n), childs(n);
    for(i64 i = 0; i < n - 1; ++i){
        i64 s, t;
        cin >> s >> t;
        --s, --t;
        edges[s].emplace_back(t);
        edges[t].emplace_back(s);
    }
    vector<i64> flag(n, 0);

    vector<i64> score = a;
    vector<i64> score_back = a;

    function<void(i64)> f = [&](i64 from){
        vector<pair<i64,i64>> sc;
        for(auto& to : edges[from]){
            if(flag[to])
                continue;
            flag[to] = 1;
            childs[from].emplace_back(to);
            f(to);
            sc.emplace_back(max(0L, score_back[to] - 2), max(0L, score[to] - 1));
        }
        i64 dif_max = 0;
        i64 sum = 0;
        for(auto& scc : sc){
            dif_max = max(dif_max, scc.second - scc.first);
            sum += scc.first;
        }
        score_back[from] += sum;
        score[from] += sum + dif_max;
    };
    flag[0] = 1;
    f(0);

    vector<i64> ans(n, 0);

    function<void(i64,i64,i64)> g = [&](i64 from, i64 par_val, i64 par_val_back){
        vector<pair<i64,i64>> v_diff;
        i64 sum = 0;
        sum += max(0L, par_val_back);
        v_diff.emplace_back(max(0L, par_val) - max(0L, par_val_back), -1);
        for(auto& to : childs[from]){
            sum += max(0L, score_back[to] - 2);
            v_diff.emplace_back(max(0L, score[to] - 1) - max(0L, score_back[to] - 2), to);
        }
        sort(v_diff.begin(), v_diff.end(), greater<pair<i64,i64>>());

        ans[from] = a[from] + sum + v_diff[0].first;

        for(auto& to : childs[from]){
            i64 nex_v = sum - max(0L, score_back[to] - 2);
            i64 nex_v_diff = v_diff[v_diff[0].second == to].first;
            g(to, nex_v + a[from] + nex_v_diff - 1, nex_v + a[from] - 2);
        }
    };
    g(0, 0, 0);

    cout << *max_element(ans.begin(), ans.end()) << endl;

}