stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <string.h>

#include <vector>

#include <stdlib.h>

#include <cstdint>

#include <cmath>

#include <algorithm>

#include <float.h>

using namespace std;



#define N 100000



string s[N];



int main()

{

	int n;

	long long ans = 0;

 

	cin >> n;

	for( int i = 0; i < n; i++ ) {

		cin >> s[i];

	}



	long long nm[5] = {0};

	for( int i = 0; i < n; i++ ) {

		if( s[i][0] == 'M' ) {

			nm[0]++;

		}

		else if( s[i][0] == 'A' ) {

			nm[1]++;

		}

		else if( s[i][0] == 'R' ) {

			nm[2]++;

		}

		else if( s[i][0] == 'C' ) {

			nm[3]++;

		}

		else if( s[i][0] == 'H' ) {

			nm[4]++;

		}



	}



	ans += nm[0] * nm[1] * nm[2];

	ans += nm[0] * nm[1] * nm[3];

	ans += nm[0] * nm[1] * nm[4];

	ans += nm[0] * nm[2] * nm[3];

	ans += nm[0] * nm[2] * nm[4];

	ans += nm[0] * nm[3] * nm[4];

	ans += nm[1] * nm[2] * nm[3];

	ans += nm[1] * nm[2] * nm[4];

	ans += nm[1] * nm[3] * nm[4];

	ans += nm[2] * nm[3] * nm[4];



	cout << ans << endl;

 

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main()

{

	int N;

	cin >> N;

	vector<int> c( 5 );

	for( int i = 0; i < N; i++ ) {

		string s;

		cin >> s;

		if( s[0] == 'M' ) c[0]++;

		else if( s[0] == 'A' ) c[1]++;

		else if( s[0] == 'R' ) c[2]++;

		else if( s[0] == 'C' ) c[3]++;

		else if( s[0] == 'H' ) c[4]++;

	}



	long long ans = 0;

	int per[5] = { 0, 0, 1, 1, 1 };

	do {

		long long m = 1;

		for( int i = 0; i < 5; i++ ) {

			if( per[i] ) m *= c[i];

		}



		ans += m;

	} while( next_permutation( per, per + 5 ) );



	cout << ans << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define Int int64_t

#define dump(x) cout << (x) << endl

#define fi first

#define se second

Int mod = 1e9+7;

Int INF = 1e18;

double EPS = 0.00000001;

//Int mod = 998244353;



int main() {

    Int a, b, c;

    cin >> a >> b >> c;

    dump(c - min(a - b, c));

    return 0;

}

// Optimized solution to the same problem (faster):
    #include <stdio.h>



    int main(void){



    int a, b, c, d;



    scanf( "%d", &a);

    scanf( "%d", &b);

    scanf( "%d", &c);



    d = c + b - a;



    if( d < 0 ){



    printf( "0\n");

    }else{



    printf( "%d\n", d);

    }

        return 0;

    }

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cmath>

#include<iomanip>

using namespace std;

struct P{

	double x,y;

	double abs()

	{

		return hypot(x,y);

	}

	P operator+(P b)

	{

		return{x+b.x,y+b.y};

	}

	P operator-(P b)

	{

		return{x-b.x,y-b.y};

	}

};

P div(P a,P b)

{

	return{a.x/a.abs()+b.x/b.abs(),a.y/a.abs()+b.y/b.abs()};

}

double theta(P a,P b)

{

	double ret=atan2(b.y,b.x)-atan2(a.y,a.x);

	ret=abs(ret);

	if(ret>M_PI)ret=2*M_PI-ret;

	return ret;

}

P take(P a,P b,double x)

{

	P q=div(a,b);

	double t=theta(a,b);

	double k=x/q.abs()/sin(t/2);

	return{q.x*k,q.y*k};

}

double cross(P a,P b){return a.x*b.y-a.y*b.x;}

bool in(P a,P b,P c,P p)

{

	return cross(p-a,b-a)*cross(p-a,c-a)<=0

		&&cross(p-b,c-b)*cross(p-b,a-b)<=0

		&&cross(p-c,a-c)*cross(p-c,b-c)<=0;

}

double dis(P p,P a,P b)

{

	double t=theta(b-a,p-a);

	return sin(t)*(p-a).abs();

}

bool check(P a,P b,P c,double x)

{

	P ab=take(a-c,b-c,x)+c,bc=take(b-a,c-a,x)+a,ca=take(c-b,a-b,x)+b;

	if(!in(a,b,c,ab)||!in(a,b,c,bc)||!in(a,b,c,ca))return false;

	if(dis(ab,a,b)<x||dis(bc,b,c)<x||dis(ca,c,a)<x)return false;

	return (ab-bc).abs()>=2*x||(bc-ca).abs()>=2*x||(ca-ab).abs()>=2*x;

}

main()

{

	P a,b,c;

	cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y;

	double L=0,R=1e3;

	for(int i=0;i<100;i++)

	{

		double M=(L+R)/2;

		if(check(a,b,c,M))L=M;

		else R=M;

	}

	cout<<fixed<<setprecision(15)<<L<<endl;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cmath>

#include<iomanip>

#include<algorithm>

using namespace std;

double ax,ay,bx,by,cx,cy,a,b,c,s,r;

main()

{

	cin>>ax>>ay>>bx>>by>>cx>>cy;

	a=hypot(ax-bx,ay-by);

	b=hypot(bx-cx,by-cy);

	c=hypot(cx-ax,cy-ay);

	s=sqrt((a+b+c)*(a+b-c)*(a-b+c)*(-a+b+c)/16);

	r=2*s/(a+b+c);

	a=max({a,b,c});

	cout<<fixed<<setprecision(15)<<a/(2+a/r)<<endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<queue>

#define INF -1000000

#define F first

#define S second

using namespace std;



int N,imap[100010],MINE;

int dp[100010];

bool Init(){

  cin >> N;

  if(N == 0)return false;

  for(int i=0;i<N;i++){

    cin >> imap[i];

    dp[i] = 1<<29;

  }

  for(int i=N;i<100010;i++)dp[i] = 1<<29;

  MINE = 1<<29;

  return true;

}



int main(){

  //while(true){

  //if(!Init())break;

  Init();



  deque<int> que;

  que.push_front(0);

  dp[0] = 0;



  while(!que.empty()){

    int p = que.front();que.pop_front();

   

    if(p >= N-1){

      cout << dp[p] << endl;

      break;

    }

    if(imap[p] != 0){

      int np = p + imap[p];

      if(dp[np] <= dp[p])continue;

      dp[np] = dp[p];

      que.push_front(np);//飛ばされてきた場合を優先する

      continue;

    }

    for(int i=1;i<=6;i++){

      int np = p+i;

      if(dp[np] <= dp[p]+1)continue;

      dp[np] = dp[p]+1;

      que.push_back(np);

    }

  }

  //for(int i=1;i<N;i++)cout << "dp["<< i << "] = "  << dp[i] << endl;





  

  //}

  return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;



int N,imap[100010],MINE;

int dp[100010];

void Init(){

scanf("%d",&N);

  for(int i=0;i<N;i++){

scanf("%d",&imap[i]);

    dp[i] = 1<<29;

  }

  for(int i=N;i<N+10;i++)dp[i] = 1<<29;

  MINE = 1<<29;

}



int main(){

  Init();

  deque<int> que;

  que.push_front(0);

  dp[0] = 0;



  while(!que.empty()){

    int p = que.front();que.pop_front();

   

    if(p >= N-1){

      

printf("%d\n",dp[p]);

      break;

    }

    if(imap[p] != 0){

      int np = p + imap[p];

      if(dp[np] <= dp[p])continue;

      dp[np] = dp[p];

      que.push_front(np);//飛ばされてきた場合を優先する

      continue;

    }

    for(int i=1;i<=6;i++){

      int np = p+i;

      if(dp[np] <= dp[p]+1)continue;

      dp[np] = dp[p]+1;

      que.push_back(np);

    }

  }

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include<cstdint>

#include<cstdlib>

#include<functional>



int const MAXN = 2e5;

int const MAXNN = 1<<18;

int a[MAXN], ans[MAXN], N;

std::vector<int> G[MAXN];



template<typename T, int NN>

struct bit {

  typedef std::function<T(T,T)> OP;

  T data_[NN]; // 0-base

  OP& op_;

  T e_;

  std::stack<std::vector<std::pair<int,T>>> ul_;

  bit(OP& op, T e) : op_(op), e_(e) { std::fill_n(data_, NN, e_); }

  int lb(int i){ return i&-i; }

  T query(int i) { // 1-base

    T res = e_;

    while(i > 0) { res = op_(res, data_[i-1]); i -= lb(i); }

    return res;

  }

  void add(int i, T const& v) { // 1-base

    std::vector<std::pair<int,T>> save;

    while(i <= NN) {

      save.emplace_back(i-1, data_[i-1]);

      data_[i-1] = op_(data_[i-1], v);

      i += lb(i);

    }

    ul_.push(save);

  }

  void undo() {

    std::vector<std::pair<int,T>>& save = ul_.top();

    for(auto p: save) data_[p.first] = p.second;

    ul_.pop();

  }

};

bit<int, MAXNN>::OP op = [](int x, int y){ return std::max(x, y); };

bit<int, MAXNN> max_bit(op, 0);



void dfs(int v, int p) {

  max_bit.add(a[v], max_bit.query(a[v]-1)+1);

  ans[v] = max_bit.query(MAXN);

  for(auto c: G[v]) if(c != p) dfs(c, v);

  max_bit.undo();

}



int main() {

  std::cin >> N;

  for(int i = 0; i < N; ++i) std::cin >> a[i];

  

  // compress a[]

  std::set<int> s(a, a+N);

  std::map<int,int> m;

  int fv = 0;

  for(int v: s) m[v] = ++fv;

  for(int i = 0; i < N; ++i) a[i] = m[a[i]];

  

  for(int i = 0; i < N-1; ++i) {

    int u, v; std::cin >> u >> v; --u; --v;

    G[u].push_back(v);

    G[v].push_back(u);

  }

  dfs(0, -1);

  for(int i = 0; i < N; ++i) std::cout << ans[i] << "\n";

  return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<vector>

#include<algorithm>



int const INF = 1024102410;

int N;





int main() {

  std::cin >> N;

  

  std::vector<int> a(N);

  for(int i = 0; i < N; ++i) std::cin >> a[i];

  

  std::vector<std::vector<int>> G(N);

  for(int i = 0; i < N-1; ++i) {

    int u, v; std::cin >> u >> v; --u; --v;

    G[u].push_back(v);

    G[v].push_back(u);

  }

  

  std::vector<int> dp(N, INF), ans(N);

  auto dfs = [&](auto &&f, int v, int p)->void {

    auto pos = std::lower_bound(dp.begin(), dp.end(), a[v]);

    auto val = *pos;

    *pos = a[v];

    ans[v] = std::lower_bound(dp.begin(), dp.end(), INF) - dp.begin();

    for(auto c: G[v]) if(c != p) f(f, c, v);

    *pos = val;

  };

  

  dfs(dfs, 0, -1);

  for(auto v: ans) std::cout << v << "\n";

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int dp[200005];

vector<int> G[200005];

int n;

int a[200005];

int ans[200005];

const int inf = 0x3f3f3f3f;

void dfs(int u,int p){

	int ind = (int)(lower_bound(dp,dp+n,a[u]) - dp);

	int cnt = dp[ind];

	dp[ind] = a[u];

	ans[u] = (int)(lower_bound(dp,dp+n,inf) - dp);

	for(int i:G[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	//undo

	dp[ind] = cnt;

}

int main(){

	cin>>n;

	for(int i=0;i<n;i++){

		cin>>a[i];

	}

	for(int i=0;i<n-1;i++){

		int t1,t2;

		cin>>t1>>t2;

		t1--,t2--;

		G[t1].push_back(t2);

		G[t2].push_back(t1);

	}

	fill(dp,dp+n+2,inf);

	dfs(0,-1);

	for(int i=0;i<n;i++) cout<<ans[i]<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

int n;

int v[200005];

int dp[200005];

int f[200005];

vector<vector<int>> g;

void dfs(int p, int u) {

    int pos = lower_bound(f, f+n, v[p]) - f;

    int t = f[pos];

    f[pos] = v[p]; 

    dp[p] = lower_bound(f, f+n, inf) - f;

    for(auto i:g[p]) {

        if(i!=u)

        dfs(i, p);

    }

    f[pos] = t;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n;

    g.resize(n+1);

    for(int i=0;i<n;i++) cin>>v[i];

    fill(f,f+n+2,inf);

    for(int i=1;i<n;i++) {

        int x, y;

        cin>>x>>y;

        x--; y--;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    dfs(0, -1);

    for(int i=0;i<n;i++) cout<<dp[i]<<endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long;

using P = pair<int,int>;

 

const int MAX_N = 200005;

const int INF = 1001001001;

 

vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

 

void dfs(int v, int p=-1) {

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if (p != -1) ans[v] = max(ans[v], ans[p]);

  for (int u : to[v]) {

    if (u == p) continue;

    dfs(u, v);

  }

  dp[i] = old;

}

 

int main() {

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i,n) cin >> a[i];

  rep(i,n-1) {

    int u, v;

    cin >> u >> v;

    --u; --v;

    to[v].push_back(u);

    to[u].push_back(v);

  }

  rep(i,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  dfs(0);

  rep(i,n) cout << ans[i] << endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;



vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

void dfs(int v, int p=-1){

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if(p != -1) ans[v] = max(ans[v], ans[p]); //exclude first turn

  

  	for(int u : to[v]){

       if(u == p) continue;  //parent

       dfs(u, v);

  	}

  //roll back

  	dp[i] = old;

}



int main(){

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }



  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    --u, --v;

    to[u].push_back(v);

    to[v].push_back(u);

  }



  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

    

    

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(MAX_N);

  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

    

    

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fi first

#define se second

#define pb push_back

#define forn(i,n) for(int i=0;i<(n);i++)

#define for1(i,n) for(int i=1;i<=n;i++)

#define forr(i,n) for(int i=n;i>=0;i--)

#define all(x) x.begin(), x.end()

const int MAXN = 2e5 +5;



void fio(){

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

}



vector<LL> ar(MAXN);

vector<vector<LL> > adj(MAXN);

LL BIT[MAXN];



LL max(LL a, LL b){

	return a>b?a:b;

}



int n;

int t[2*MAXN];



void modify(int p, int value) {  

  for (t[p += n+1] = value; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);

}



int query(int l, int r) { 

  int res = 0;

  for (l += n+1, r += n+1; l < r; l >>= 1, r >>= 1) {

    if (l&1) res = max(res,t[l++]);

    if (r&1) res = max(res,t[--r]);

  }

  return res;

}



int an[MAXN];



void dfs(int u,int p){

	int old = query(ar[u], ar[u]+1);

	int	x = query(0, ar[u]); 

	int value = x + 1; 

	

	//cout<<u<<" "<<ar[u]<<" "<<x<<endl;

	modify(ar[u], max(value,old));

	an[u] = query(0,n+1);

	for(auto i:adj[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	modify(ar[u], old);

		//cout<<u<<" "<<p<<endl;

}



int main(){

  fio();

  cin>>n;

  vector<LL> v(n);

  set<LL> s;

  forn(i,n) {

  	cin>>v[i];

  	s.insert(v[i]);

  }

  int in = 0;

  map<LL,LL> mp;

  for(auto i:s){

  	mp[i] = ++in;

  }

  forn(i,n){

  	ar[i+1] = mp[v[i]];

  }

  forn(i,n-1){

  	int u, v; cin>>u>>v;

  	adj[v].pb(u);

  	adj[u].pb(v);

  }

  

  // for1(i,n) cout<<ar[i]<<" ";x

  // cout<<endl;

  

  dfs(1,0);

  for1(i,n) cout<<an[i]<<endl;



  return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fi first

#define se second

#define pb push_back

#define forn(i,n) for(int i=0;i<(n);i++)

#define for1(i,n) for(int i=1;i<=n;i++)

#define forr(i,n) for(int i=n;i>=0;i--)

#define all(x) x.begin(), x.end()

const int MAXN = 2e5 +5;



void fio(){

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

}





vector<vector<int>> adj(MAXN);



LL max(LL a, LL b){

	return a>b?a:b;

}



int n;

vector<LL> v;

int an[MAXN];

vector <int> lc;



void dfs(int u,int p){

	auto x = upper_bound(all(lc), v[u]) - lc.begin();

	int ch = -1;

	int val;

	if(x >=1 && lc[x-1]!=v[u] || x == 0){

		ch = x;

		val = lc[x];

		lc[x] = v[u];

	}

	an[u] = lower_bound(all(lc), INT_MAX) - lc.begin();

	for(auto i:adj[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	if(ch!=-1) lc[x] = val;

}



int main(){

  fio();

  cin>>n;

  set<LL> s;

  forn(i,n) {

  	int x; cin>>x;

  	v.pb(x);

  }

  lc.resize(n+1);

  forn(i,n+1) lc[i] = INT_MAX;

  forn(i,n-1){

  	int u, x; cin>>u>>x;

  	u--, x--;

  	adj[x].pb(u);

  	adj[u].pb(x);

  } 

  dfs(0,-1);

  forn(i,n) cout<<an[i]<<endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

#include <queue>

#include <set>

#include <map>



using namespace std;

typedef long long ll;

int N;

ll a[200005];

int u[200005], v[200005];



ll dp[200005];

vector<int> G[200005];

bool used[200005];

int ans[200005];



const ll INF = 2e15;



void dfs(int v, int d){

    used[v] = true;

    auto p = lower_bound(dp, dp+N+4, a[v]);

    int dif = p-dp;

    ll pre = dp[dif];

    dp[dif] = min(a[v], dp[dif]);

    ans[v] = lower_bound(dp, dp+N+4, INF)-dp;

    for(int to : G[v]){

        if(!used[to]){

            dfs(to, d+1);

        }

    }

    dp[dif] = pre;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << setprecision(10) << fixed;

    cin >> N;

    for(int i = 0; i < N; i++) cin >> a[i];

    for(int i = 0; i < N-1; i++){

        cin >> u[i] >> v[i];

        u[i]--; v[i]--;

        G[u[i]].push_back(v[i]);

        G[v[i]].push_back(u[i]);

    }

    for(int i = 0; i <= 200004; i++) dp[i] = INF+i; 

    // dp[0] = a[0];

    // ans[0] = 1;

    dfs(0, 1);

    for(int i = 0; i < N; i++) cout << ans[i] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

#include <queue>

#include <set>

#include <map>



using namespace std;

typedef long long ll;

int N;

ll a[200005];

int u[200005], v[200005];



ll dp[200005];

vector<int> G[200005];

bool used[200005];

int ans[200005];



const ll INF = 2e15;



void dfs(int v){

    used[v] = true;

    auto p = lower_bound(dp, dp+N+2, a[v]);

    int dif = p-dp;

    ll pre = dp[dif];

    dp[dif] = min(a[v], dp[dif]);

    ans[v] = lower_bound(dp, dp+N+2, INF)-dp;

    for(int to : G[v]){

        if(!used[to]){

            dfs(to);

        }

    }

    dp[dif] = pre;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << setprecision(10) << fixed;

    cin >> N;

    for(int i = 0; i < N; i++) cin >> a[i];

    for(int i = 0; i < N-1; i++){

        cin >> u[i] >> v[i];

        u[i]--; v[i]--;

        G[u[i]].push_back(v[i]);

        G[v[i]].push_back(u[i]);

    }

    for(int i = 0; i <= N+2; i++) dp[i] = INF; 

    dfs(0);

    for(int i = 0; i < N; i++) cout << ans[i] << endl;

}

// Fastest known solution for this problem: