#include <bits/stdc++.h>
long long max(long long a, long long b) { return a > b ? a : b; }
int oo[1 + (100000 - 1) * 2], oj[1 + (100000 - 1) * 2];
int link(int o, int j) {
  static int _ = 1;
  oo[_] = o, oj[_] = j;
  return _++;
}
int ae[100000], aa[100000];
long long hh[100000], dp[100000], dq[100000];
void dfs1(int p, int i) {
  int o;
  long long h1, h2;
  h1 = h2 = 0;
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      dfs1(i, j);
      if (h1 < hh[j])
        h2 = h1, h1 = hh[j];
      else if (h2 < hh[j])
        h2 = hh[j];
      dp[i] = max(dp[i], dp[j]);
    }
  }
  hh[i] = h1 + aa[i];
  dp[i] = max(dp[i], h1 + h2 + aa[i]);
}
void dfs2(int p, int i, long long h, long long q) {
  int o, jh1, jh2, jdp1;
  long long h1, h2, h3, dp1, dp2;
  dq[i] = q;
  h1 = h2 = h3 = 0, jh1 = jh2 = -1;
  dp1 = dp2 = 0, jdp1 = -1;
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      if (h1 < hh[j]) {
        h3 = h2, h2 = h1, h1 = hh[j];
        jh2 = jh1, jh1 = j;
      } else if (h2 < hh[j]) {
        h3 = h2, h2 = hh[j];
        jh2 = j;
      } else if (h3 < hh[j])
        h3 = hh[j];
      if (dp1 < dp[j]) {
        dp2 = dp1, dp1 = dp[j];
        jdp1 = j;
      } else if (dp2 < dp[j])
        dp2 = dp[j];
    }
  }
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      long long h1_ = j == jh1 ? h2 : h1;
      long long h2_ = j == jh1 || j == jh2 ? h3 : h2;
      long long q_ = j == jdp1 ? dp2 : dp1;
      dfs2(i, j, max(h, h1_) + aa[i],
           max(max(q, q_), h1_ + max(h, h2_) + aa[i]));
    }
  }
}
int main() {
  int n, h, i, j;
  long long ans;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &aa[i]);
  for (h = 0; h < n - 1; h++) {
    scanf("%d%d", &i, &j), i--, j--;
    ae[i] = link(ae[i], j);
    ae[j] = link(ae[j], i);
  }
  dfs1(-1, 0);
  dfs2(-1, 0, 0, 0);
  ans = 0;
  for (i = 0; i < n; i++) ans = max(ans, dp[i] + dq[i]);
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

Alice and Bob have a tree (undirected acyclic connected graph). There are ai chocolates waiting to be picked up in the i-th vertex of the tree. First, they choose two different vertices as their starting positions (Alice chooses first) and take all the chocolates contained in them.

Then, they alternate their moves, selecting one vertex at a time and collecting all chocolates from this node. To make things more interesting, they decided that one can select a vertex only if he/she selected a vertex adjacent to that one at his/her previous turn and this vertex has not been already chosen by any of them during other move.

If at any moment one of them is not able to select the node that satisfy all the rules, he/she will skip his turns and let the other person pick chocolates as long as he/she can. This goes on until both of them cannot pick chocolates any further.

Due to their greed for chocolates, they want to collect as many chocolates as possible. However, as they are friends they only care about the total number of chocolates they obtain together. What is the maximum total number of chocolates they may pick?

Input

The first line of the input contains the single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

The second line contains n integers ai (1 ≤ ai ≤ 109), i-th of these numbers stands for the number of chocolates stored at the node i.

Then follow n - 1 lines that describe the tree. Each of them contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of vertices connected by the i-th edge.

Output

Print the number of chocolates Alice and Bob can collect together if they behave optimally.

Examples

Input

9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9


Output

25


Input

2
20 10
1 2


Output

30

Note

In the first sample, Alice may start at the vertex 9 and Bob at vertex 8. Alice will select vertex 1 and Bob has no options now. Alice selects the vertex 7 and they both stop.

In the second sample, both of them will pick either of the nodes alternately.

### Response

```cpp
#include <bits/stdc++.h>
long long max(long long a, long long b) { return a > b ? a : b; }
int oo[1 + (100000 - 1) * 2], oj[1 + (100000 - 1) * 2];
int link(int o, int j) {
  static int _ = 1;
  oo[_] = o, oj[_] = j;
  return _++;
}
int ae[100000], aa[100000];
long long hh[100000], dp[100000], dq[100000];
void dfs1(int p, int i) {
  int o;
  long long h1, h2;
  h1 = h2 = 0;
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      dfs1(i, j);
      if (h1 < hh[j])
        h2 = h1, h1 = hh[j];
      else if (h2 < hh[j])
        h2 = hh[j];
      dp[i] = max(dp[i], dp[j]);
    }
  }
  hh[i] = h1 + aa[i];
  dp[i] = max(dp[i], h1 + h2 + aa[i]);
}
void dfs2(int p, int i, long long h, long long q) {
  int o, jh1, jh2, jdp1;
  long long h1, h2, h3, dp1, dp2;
  dq[i] = q;
  h1 = h2 = h3 = 0, jh1 = jh2 = -1;
  dp1 = dp2 = 0, jdp1 = -1;
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      if (h1 < hh[j]) {
        h3 = h2, h2 = h1, h1 = hh[j];
        jh2 = jh1, jh1 = j;
      } else if (h2 < hh[j]) {
        h3 = h2, h2 = hh[j];
        jh2 = j;
      } else if (h3 < hh[j])
        h3 = hh[j];
      if (dp1 < dp[j]) {
        dp2 = dp1, dp1 = dp[j];
        jdp1 = j;
      } else if (dp2 < dp[j])
        dp2 = dp[j];
    }
  }
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    if (j != p) {
      long long h1_ = j == jh1 ? h2 : h1;
      long long h2_ = j == jh1 || j == jh2 ? h3 : h2;
      long long q_ = j == jdp1 ? dp2 : dp1;
      dfs2(i, j, max(h, h1_) + aa[i],
           max(max(q, q_), h1_ + max(h, h2_) + aa[i]));
    }
  }
}
int main() {
  int n, h, i, j;
  long long ans;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &aa[i]);
  for (h = 0; h < n - 1; h++) {
    scanf("%d%d", &i, &j), i--, j--;
    ae[i] = link(ae[i], j);
    ae[j] = link(ae[j], i);
  }
  dfs1(-1, 0);
  dfs2(-1, 0, 0, 0);
  ans = 0;
  for (i = 0; i < n; i++) ans = max(ans, dp[i] + dq[i]);
  printf("%lld\n", ans);
  return 0;
}

```