Problem: The biggest gold mine in Berland consists of n caves, connected by n - 1 transitions. The entrance to the mine leads to the cave number 1, it is possible to go from it to any remaining cave of the mine by moving along the transitions. 

The mine is being developed by the InMine Inc., k miners work for it. Each day the corporation sorts miners into caves so that each cave has at most one miner working there. 

For each cave we know the height of its ceiling hi in meters, and for each miner we know his height sj, also in meters. If a miner's height doesn't exceed the height of the cave ceiling where he is, then he can stand there comfortably, otherwise, he has to stoop and that makes him unhappy.

Unfortunately, miners typically go on strike in Berland, so InMine makes all the possible effort to make miners happy about their work conditions. To ensure that no miner goes on strike, you need make sure that no miner has to stoop at any moment on his way from the entrance to the mine to his cave (in particular, he must be able to stand comfortably in the cave where he works). 

To reach this goal, you can choose exactly one cave and increase the height of its ceiling by several meters. However enlarging a cave is an expensive and complex procedure. That's why InMine Inc. asks you either to determine the minimum number of meters you should raise the ceiling of some cave so that it is be possible to sort the miners into the caves and keep all miners happy with their working conditions or to determine that it is impossible to achieve by raising ceiling in exactly one cave.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of caves in the mine.

Then follows a line consisting of n positive integers h1, h2, ..., hn (1 ≤ hi ≤ 109), where hi is the height of the ceiling in the i-th cave.

Next n - 1 lines contain the descriptions of transitions between the caves. Each line has the form ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the numbers of the caves connected by a path.

The next line contains integer k (1 ≤ k ≤ n).

The last line contains k integers s1, s2, ..., sk (1 ≤ sj ≤ 109), where sj is the j-th miner's height.

Output

In the single line print the minimum number of meters that you need to raise the ceiling by in some cave so that all miners could be sorted into caves and be happy about the work conditions. If it is impossible to do, print  - 1. If it is initially possible and there's no need to raise any ceiling, print 0. 

Examples

Input

6
5 8 4 6 3 12
1 2
1 3
4 2
2 5
6 3
6
7 4 2 5 3 11


Output

6


Input

7
10 14 7 12 4 50 1
1 2
2 3
2 4
5 1
6 5
1 7
6
7 3 4 8 8 10


Output

0


Input

3
4 2 8
1 2
1 3
2
17 15


Output

-1

Note

In the first sample test we should increase ceiling height in the first cave from 5 to 11. After that we can distribute miners as following (first goes index of a miner, then index of a cave): <image>.

In the second sample test there is no need to do anything since it is already possible to distribute miners as following: <image>.

In the third sample test it is impossible.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
namespace T {
void Dorzuc(int& l, int& r, int L, int R) {
  if (r < L) {
    l += L - r;
    r = R;
  } else {
    r += R - L;
  }
}
struct N {
  int c[3] = {0, 0, 0};
  N() = default;
  int l, r;
  int key;
  N(int key) : key(key), l(0), r(0) {
    if (key % 2)
      Dorzuc(l, r, 0, 1);
    else
      Dorzuc(l, r, 1, 0);
  }
  void Touch(N* left, N* right) {}
  void Update(N* left, N* right) {
    l = r = 0;
    if (left) Dorzuc(l, r, left->l, left->r);
    if (key % 2)
      Dorzuc(l, r, 0, 1);
    else
      Dorzuc(l, r, 1, 0);
    if (right) Dorzuc(l, r, right->l, right->r);
  }
  void Clear() {}
};
vector<N> d;
vector<int> fd;
template <typename... A>
int New(A&&... a) {
  if (fd.empty()) {
    d.emplace_back(forward<A>(a)...);
    return d.size();
  }
  const int i = fd.back();
  fd.pop_back();
  d[i - 1] = N(forward<A>(a)...);
  return i;
}
void ReserveAtLeast(int n) {
  while (fd.size() < n) {
    d.resize(d.size() + 1);
    fd.push_back(d.size());
  }
}
void Delete(int v) {
  d[v - 1].Clear();
  fd.push_back(v);
}
void ClearAll() {
  d.clear();
  fd.clear();
}
N* Get(int v) { return v ? &d[v - 1] : nullptr; }
int Touch(int v) {
  if (v) d[v - 1].Touch(Get(d[(v)-1].c[0]), Get(d[(v)-1].c[1]));
  return v;
}
int Update(int v) {
  if (v) d[v - 1].Update(Get(d[(v)-1].c[0]), Get(d[(v)-1].c[1]));
  return v;
}
void Rotate(int v) {
  const int p = d[(v)-1].c[2];
  const int x = (d[(d[(v)-1].c[2]) - 1].c[1] == v);
  if (d[(v)-1].c[2] = d[(p)-1].c[2])
    d[(d[(p)-1].c[2]) - 1].c[(d[(d[(p)-1].c[2]) - 1].c[1] == p)] = v;
  if (d[(p)-1].c[x] = d[(v)-1].c[x ^ 1]) d[(d[(p)-1].c[x]) - 1].c[2] = p;
  d[(d[(v)-1].c[x ^ 1] = p) - 1].c[2] = v;
  Update(p);
}
void Splay(int v) {
  if (!Touch(v)) return;
  Touch(d[(v)-1].c[0]);
  Touch(d[(v)-1].c[1]);
  while (const int p = d[(v)-1].c[2]) {
    Touch(d[(p)-1].c[(d[(d[(v)-1].c[2]) - 1].c[1] == v) ^ 1]);
    if (d[(p)-1].c[2]) {
      Touch(d[(d[(p)-1].c[2]) - 1].c[(d[(d[(p)-1].c[2]) - 1].c[1] == p) ^ 1]);
      Rotate((d[(d[(v)-1].c[2]) - 1].c[1] == v) ==
                     (d[(d[(p)-1].c[2]) - 1].c[1] == p)
                 ? p
                 : v);
    }
    Rotate(v);
  }
  Update(v);
}
bool Next(int& v, int x = 1) {
  if (!v or !d[(Touch(v)) - 1].c[x]) return false;
  v = d[(v)-1].c[x];
  while (d[(Touch(v)) - 1].c[x ^ 1]) v = d[(v)-1].c[x ^ 1];
  Splay(v);
  return true;
}
void First(int& v, int x = 0) {
  if (!v) return;
  while (d[(Touch(v)) - 1].c[x]) v = d[(v)-1].c[x];
  Splay(v);
}
int Join(int l, int r) {
  if (!l or !r) return Touch(l + r);
  First(r);
  d[(d[(l)-1].c[2] = r) - 1].c[0] = Touch(l);
  Touch(d[(r)-1].c[1]);
  return Update(r);
}
pair<int, int> Split(int v) {
  if (!v) return {0, 0};
  const int l = d[(Touch(v)) - 1].c[0];
  if (!l) return {0, v};
  d[(v)-1].c[0] = d[(l)-1].c[2] = 0;
  Touch(d[(v)-1].c[1]);
  return {Touch(l), Update(v)};
}
void DeleteRoot(int& v) {
  if (!Touch(v)) return;
  if (d[(v)-1].c[0]) d[(d[(v)-1].c[0]) - 1].c[2] = 0;
  if (d[(v)-1].c[1]) d[(d[(v)-1].c[1]) - 1].c[2] = 0;
  const int result = Join(d[(v)-1].c[0], d[(v)-1].c[1]);
  Delete(v);
  v = result;
}
void DeleteTree(int& v) {
  while (const int t = v) {
    if (v = d[(t)-1].c[0])
      d[(t)-1].c[0] = 0;
    else if (v = d[(t)-1].c[1])
      d[(t)-1].c[1] = 0;
    else
      v = d[(t)-1].c[2], Delete(t);
  }
}
template <typename F>
void GoDown(int*& v, int& p, F f) {
  p = 0;
  int tmp;
  while (Touch(*v) and (tmp = f(*Get(*v)))) {
    v = &d[(p = *v) - 1].c[tmp > 0];
  }
}
N& FindOrCreate(int& v, int key) {
  ReserveAtLeast(1);
  int p, *vptr = &v;
  GoDown(vptr, p, [key](N& n) -> int {
    if (key == n.key)
      return 0;
    else if (key < n.key)
      return -1;
    else
      return 1;
  });
  if (!*vptr) d[(*vptr = New(key)) - 1].c[2] = p;
  Splay(v = *vptr);
  return *Get(v);
}
pair<int, int> SplitByKey(int v, int a) {
  if (!v) return {0, 0};
  int p, *vptr = &v;
  GoDown(vptr, p, [a](N& n) -> int {
    if (a == n.key)
      return 0;
    else if (a < n.key)
      return -1;
    else
      return 1;
  });
  if ((v = *vptr) or Get(v = p)->key > a) {
    Splay(v);
    return Split(v);
  }
  Splay(p);
  if (Next(p)) return Split(p);
  return {p, 0};
}
template <typename F>
auto RangeF(int& v, int a, int b, F f) -> decltype(f(v)) {
  auto lm = SplitByKey(v, a);
  auto mr = SplitByKey(lm.second, b + 1);
  auto l = [&]() { v = Join(lm.first, Join(mr.first, mr.second)); };
  using Y = decltype(l);
  struct Z {
    Z(Y y) : y(y) {}
    ~Z() { y(); }
    Y y;
  } z(l);
  return f(mr.first);
}
void Dorzuc(int& d, int v) {
  auto x = SplitByKey(d, v);
  d = Join(Join(x.first, New(v)), x.second);
}
void Usun(int& d, int v) {
  auto x = SplitByKey(d, v);
  First(x.second);
  DeleteRoot(x.second);
  d = Join(x.first, x.second);
}
bool JestOk(int v) {
  if (v == 0) return true;
  return Get(v)->r == 0;
}
}  // namespace T
using ll = long long;
using ld = long double;
constexpr int nax = 1000 * 1000 + 105;
constexpr int infty = 1000 * 1000 * 1000 + 5;
constexpr int mod = 1000 * 1000 * 1000 + 7;
int n, k;
int h[nax];
vector<int> graf[nax];
vector<int> s;
void Dorzucaj(int w, int& drzewo,
              int min_pref = std::numeric_limits<int>::max()) {
  min_pref = min(min_pref, h[w]);
  T::Dorzuc(drzewo, min_pref);
  for (int v : graf[w]) {
    Dorzucaj(v, drzewo, min_pref);
  }
}
void Usuwaj(int w, int& drzewo,
            int min_pref = std::numeric_limits<int>::max()) {
  min_pref = min(min_pref, h[w]);
  T::Usun(drzewo, min_pref);
  for (int v : graf[w]) {
    Usuwaj(v, drzewo, min_pref);
  }
}
void dfs(int w, int o) {
  for (int i = 0; i < (int)graf[w].size(); i++) {
    if (graf[w][i] == o) {
      swap(graf[w][i], graf[w].back());
      graf[w].pop_back();
      i--;
      continue;
    }
    dfs(graf[w][i], w);
  }
}
struct comp {
  bool operator()(int a, int b) const {
    if (h[a] == h[b]) return a < b;
    return h[a] > h[b];
  }
};
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &h[i]);
    h[i] *= 2;
  }
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    graf[a].push_back(b);
    graf[b].push_back(a);
  }
  dfs(1, -1);
  scanf("%d", &k);
  while (k--) {
    int x;
    scanf("%d", &x);
    x = x * 2 - 1;
    s.push_back(x);
  }
  sort(s.begin(), s.end());
  set<int, comp> rooty;
  rooty.insert(1);
  while (!s.empty()) {
    const int najw = s.back();
    int v = *rooty.begin();
    if (h[v] < najw) break;
    s.pop_back();
    rooty.erase(v);
    for (int x : graf[v]) {
      rooty.insert(x);
    }
  }
  debug() << " ["
          << "rooty"
             ": "
          << (rooty) << "] ";
  debug() << " ["
          << "s"
             ": "
          << (s) << "] ";
  if (s.empty()) {
    printf("0\n");
    return 0;
  }
  int d = 0;
  for (int x : s) {
    T::Dorzuc(d, x);
  }
  for (int x : rooty) {
    Dorzucaj(x, d);
  }
  assert(!T::JestOk(d));
  for (int x : rooty) {
    Usuwaj(x, d);
    T::Usun(d, s.back());
    const int wynik = (s.back() + 1) / 2 - h[x] / 2;
    assert(wynik >= 0);
    {
      for (int v : graf[x]) {
        Dorzucaj(v, d);
      }
      if (T::JestOk(d)) {
        printf("%d\n", wynik);
        return 0;
      }
      for (int v : graf[x]) {
        Usuwaj(v, d);
      }
    }
    T::Dorzuc(d, s.back());
    Dorzucaj(x, d);
  }
  printf("-1\n");
  return 0;
}