#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int A[100010];
vector<int> e[100010];

template<typename T> using maxSet = multiset<T, greater<T>>;
template<typename T> using minSet = multiset<T>;

int mid[100010];

template<typename T>
void balance(maxSet<T> &small,minSet<T> &large){
  while(large.size() > small.size()){
    small.insert(*large.begin());
    large.erase(large.begin());
  }
  while(small.size() >= large.size() + 2){
    large.insert(*small.begin());
    small.erase(small.begin());
  }
}

template<typename T>
int dfs(int u,int f,maxSet<T> &small,minSet<T> &large, int dep){
  // 插入
  if(small.size() == 0 || *small.begin() >= A[u]){
    small.insert(A[u]);
  }else{
    large.insert(A[u]);
  }
  balance(small,large);

  int res = 0;
  if(u != 1 && e[u].size() == 1){ // leaf
    res = (small.size() == large.size()) ? (*small.begin() + *large.begin())/2 : *small.begin();
  }else{
    vector<int> vals;
    for(auto v:e[u]) if(v != f) vals.push_back(dfs(v,u,small,large,dep^1));
    res = (dep==0)? *max_element(vals.begin(),vals.end()) : *min_element(vals.begin(),vals.end());
  }
  // 删除
  auto sptr = small.find(A[u]);
  if(sptr != small.end()){
    small.erase(sptr);
  }else{
    auto lptr = large.find(A[u]);
    assert(lptr != large.end());
    large.erase(lptr);
  }
  balance(small,large);
  return res;
}

int main(){
  int n = read();
  rep(i,1,n+1) A[i] = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  maxSet<int> small ; // 前一半
  minSet<int> large ;
  printf("%d\n",dfs(1,1,small,large,0));
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll a[200010];

pair<ll,int> f(ll v){ // f(斜率) => {最大截距, 横坐标(选的个数)}
  auto dp = vector(n,vector(2,pair<ll,int>{0,0})); // dp[i][第i个 选/不选] = {最大截距,个数}
  rep(i,1,n){
    auto [y0, c0] = dp[i-1][0];
    dp[i][1] = {y0 + (a[i-1] - v), c0 + 1}; // 当前选, 则上一个不选
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]); // 当前不选, 则上一个可选可不选
  }
  return max(dp[n-1][0],dp[n-1][1]);
}

int main(){
  n = read();
  int x = read();
  x = min(x, n-x);
  rep(i,0,n-1) a[i] = read(); // [0..n-2]
  rep(i,0,n-1) a[i] += a[i+1]; // [0..n-2], 看成多了末尾多了一个0, 对最大值无影响
  ll L = 0, R = 3000'000'000; // 斜率
  // 二分, 这里可能 有多个点 让同一个斜率最大, 保证 斜率R < x <= 斜率L 即可, 注意到这这里可能 f(R).pos < f(L).pos < x, 但f(L).pos 只是斜率L上的任意一点 但只要x 斜率不大于 L即可
  while(L + 1 < R) (f((L+R)/2).second < x ? R : L) = mid;
  printf("%lld\n", f(L).first + x * L);
}

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read

int main() {
  int n = read();
  int m = read();
  vector<vector<mint>> dp(n + 1, vector<mint> (n + 1));
  dp[0][0] = 1;
  rep(i,1,n+1){
    rep(j,1,i+1) { // j-(i-1)/m >= 0
      dp[i][j] = dp[i-1][j-1];
      if(j-(i-1)/m >= 0) dp[i][j] += dp[i-1][j] * (j-(i-1)/m);
    }
  }
  rep(i,1,n+1) printf("%d\n",dp[n][i].val());
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
priority_queue<ll> ql; //大根堆,左侧, 记录斜率-1的起点,-2的起点,-3的起点,...到 -Ti的距离
priority_queue<ll> qr; //大根堆,右侧, 记录斜率 1的起点, 2的起点, 3的起点,...到  Ti的距离
 
int main() {
  int n = read();
  ll ans = 0;
  rep(i, 1, n+1) {
    ll t = read();
    ll d = read();
    ll x = read();
    // 让下凸的最小值一直是0
    if (d == 0) {
      if (x > t) { // 超出范围直接全部都加上
        ans += x - t;
        x = t;
      }
      if (qr.empty() || qr.top() <= t-x) { // 不影响右侧的
        ql.push(x + t);// 原来-1变-2, -2变-3,... , 新的-1的起点
      } else { // ... -3 -2 -1  0 ... 0 1 2 3 ... 影响右侧的,
        int pos = t - qr.top(); // 最小值的位置 右侧1斜率的起点
        qr.pop();
        ans += x - pos; // 让下凸的最小值 = 0
        ql.push(pos-(-t)); // 成为左侧新的 -1 斜率的起点
        qr.push(t - x); // 插入新的 斜率变化分割(距离右侧Ti
      }
    } else { // d = 1
      if (x < -t) { // 超出范围直接全部都加上
        ans += -t - x;
        x = -t;
      }
      if (ql.empty() || x - (-t) >= ql.top()) { // 不影响左侧
        qr.push(t - x); // 右侧最大点
      } else {
        int pos = ql.top() - t; // 最小值的位置, 左侧-1斜率的起点
        ql.pop();
        ans += pos-x;
        qr.push(t-pos);
        ql.push(x-(-t));
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

vector<array<int,3> > e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back({i+1, i, 0}); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back({a,b,d});
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back({b,a,-d});
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(i,0,N-1) for(auto [u,v,w]: e) if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  for(auto [u,v,w]: e) if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define mt make_tuple

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

// 没有tuple
struct edge{
  int u;
  int v;
  int w;
  // 结构体直接赋值也没有
  edge(int _u,int _v,int _w){
    u = _u;
    v = _v;
    w = _w;
  }
};

vector<edge> e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back(edge(i+1, i, 0)); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back(edge(a,b,d));
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back(edge(b,a,-d));
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(t,0,N-1) rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);
  }

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  }
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
 
int read(){int r;scanf("%d",&r);return r;} // read
 
const int N=200000;
int a[N+10]; // a[空白个数] = 到右侧点, 之间全是1
int r[N+10]; // 读入
int y[N+10]; // 左侧0个数
vector<int> l2i[N+10]; // 左端点到第i个区间
 
int main() {
  int n = read();
  int m = read();
  rep(i,1,m+1){
    int l = read();
    r[i] = read();
    y[i] = (r[i]-l+1) - read(); // 左侧0个数 [[....yi],1,1,1,1,1,1]
    l2i[l].push_back(i);
  }
  int cnt = 0; // 遍历过程中 (<l) 0 的个数
  rep(pos,1,n+1){ // 下标
    for(auto i:l2i[pos]) a[y[i]+cnt] = max(a[y[i]+cnt],r[i]);// [pos.....r[i]]
    printf("%d ", a[cnt] >= pos); // 这一段全是1, 1尽量向右,贪心塞0
    cnt += (a[cnt] < pos); // 计数+1
  }
  return 0;
}

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int x[2010]; // 初始位置
mint f[2010] = {1}; // f[i] = binom(n,i)
int p[(1<<10)+10]; // p[mask] = (-1)^(mask中1的个数)
mint dp[(1<<10)+10] = {1}; // 第二维滚动 f(S,pos) = f(S, pos-1) + \sum_{i=1}^{|S|} (-1)^{count(S,> i)} \binom{n}{pos-x_{s_i}} f(S\setminus\{s_i\}, pos-1).$

int main() {
  int k=read();
  int n=read();
  rep(i,0,k) x[i]=read();
  rep(i,1,n+1) f[i]=f[i-1]*(n-i+1)/i; // binom(n,i-1) -> binom(n,i)
  rep(mask,0,1<<k) p[mask] = p[mask>>1] * (mask&1?-1:1);
  rep(pos,x[0],x[k-1]+n+1){ // 第二维滚动
    per(mask,0,1<<k) { // 第一维 bitmask 注意顺序
      rep(i,0,k) if(mask&(1<<i)) { // 变成递推贡献, 要增加的bit位
        if(x[i]<=pos && pos<=x[i]+n) { // 保证 binom 不为0
          // f(S) += f(S\i) * binom(n, pos - x[S_i]) * (-1)^count(S,>i)
          dp[mask] += dp[mask^(1<<i)] * f[pos-x[i]] * p[mask>>(i+1)];
        }
      }
    }
  }
  printf("%d\n",(dp[(1<<k)-1] / ((mint)2).pow(k*n)).val()); // 频次/总次数 = 概率
  return 0;
}

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
const int MOD = 998244353;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int c[50010];
mint fac[50010] = {1};
mint invv[50010] = {0,1};
mint invfac[50010] = {1};

mint binom(int n,int m){
  if(m > n) return 0;
  return fac[n] * invfac[m] * invfac[n-m];
}

int main(){
  int n = read();
  rep(i,0,n) c[i] = read();

  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD - MOD/i) * invv[MOD%i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  sort(c,c+n);
  vector<int> sz = {1};
  rep(i,1,n){
    if(c[i] != c[i-1]){
      sz.push_back(1);
    }else{
      sz.back()++;
    }
  }
  sort(sz.begin(),sz.end());
  vector<pair<int,int>> sc; // size count
  int cnt = 0;
  rep(i,0,sz.size()){
    cnt++;
    if(i+1 == (int)sz.size() || sz[i] != sz[i+1]){
      sc.push_back({sz[i],cnt});
      cnt = 0;
    }
  }

  rep(k,1,n+1){
    mint bnk = binom(n,k);
    mint ans = bnk * sz.size() ;
    for(auto [s,t]:sc) {
      if(n-s < k) break; // n-s < k 的话, 必定出现p = 1
      ans -= binom(n-s,k) * t; // * 次数
    }
    ans /= bnk;
    printf("%d\n",ans.val());
  }
  return 0;
}

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

const ll INF = 0x3f3f3f3f; // > 1e9
const int N = 20;
const int MASK = ( 1 << N ) ;
const int M = N * 100000;

mint fac[M+10] = {1}; // 阶乘
mint ifac[M+10] ={1}; // 阶乘的逆向

int f[MASK+10]; // f[1 << i] = A[i], f[mask] = sum A
int g[MASK+10]; // g[左侧mask] = sum B , 通过sosdp 变成子集和
mint h[MASK+10]; // h(S=bitmask) S中移除 X 个的方案数,(每个恰好一个)
int cnt[MASK+10]; // mask 中1的个数
int cont[MASK+10]; // cont[mask] = 多少个父集合 是满足 最小代价为X的 在mask中移除让Hall定理触发不满足

int B[M+10]; // 读入
int adj[M+10]; // adj[右侧] = 左侧的bitmask

mint binom( int n, int m ) { return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; }

int main() {
  rep(i,1,M+1) fac[i] = fac[i - 1]*i;
  ifac[M] = fac[M].inv();
  per(i,0,M) ifac[i] = ifac[i + 1]*(i + 1);
  int n = read();
  int m = read();
  rep(i,0,n)f[1 << i]=read();//f[1 << i]=A[i]
  rep(j,0,m)B[j]=read();
  rep(i,0,n)rep(j,0,m) if(read())adj[j]|=1 << i; // 转换成mask
  rep(j,0,m)g[adj[j]] += B[j]; // g[对应左侧mask] += B[j]
  rep(mask,1,1 << n) cnt[mask] = cnt[mask >> 1] + ( mask & 1 ); // 计算1个数
  rep(mask,1,1 << n) f[mask] = f[mask&(-mask)] + f[mask&(mask-1)]; // 去掉最后一个1 和最后一个1的mask之和
  rep(pwr,0,n) rep(mask,1,1 << n) if(mask & (1 << pwr)) g[mask] += g[mask ^ (1 << pwr)]; // sosdp 高维前缀和
  rep(mask,0,1 << n) if(!g[mask]) g[mask] = -INF; // 右侧没有集合对应左侧集合是mask的子集合
  int X = INF; // 答案第一部分 删除个数
  rep(mask,1,1 << n) X = min(X,f[mask]-g[mask]+1 ); // Hall定理, min(左子集值和 - 右侧来源子集和)
  if(max(X,0) == 0) { // 本来就不合法
    printf( "0 1\n" );
    return 0;
  }
  // h'(S) = (-1)^|S| h(S) = sum (-1)^|T| binom(f[t], X) SOSDP
  rep(mask,1,1 << n) h[mask] = binom(f[mask], X) * (cnt[mask] & 1 ? -1 : 1);
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) h[mask] += h[mask ^ (1 << pwr)];
  rep(mask,0,1 << n) h[mask] = h[mask] * ((cnt[mask] & 1)?-1:1);

  // SOSDP 父集合反演(本质上还是 子集反演, 你只是把每个mask 看成mask的取反即可, 最外层是pwr顺序, mask每次之间没有链式依赖,都是两两依赖, 所以mask不需要换顺序
  rep(mask,1,1 << n) if( f[mask] - g[mask] + 1 == X ) cont[mask] = 1;
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) cont[mask ^ (1 << pwr)] += cont[mask]; // 统计父集合可行的次数

  mint ans = 0;
  rep(mask,0,1 << n) if(cont[mask]) ans += h[mask];
  printf("%d %d\n",X, ans.val());
  return 0;
}