#include <bits/stdc++.h> // #pragma GCC target ("avx2") // #pragma GCC optimize ("O3") // #pragma GCC optimize ("unroll-loops") using namespace std; #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define Int __int128 #define int long long #define dl double long #define fl float #define all(s) s.begin(), s.end() #define lall(s) ++s.begin(), s.end() #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define ins insert #define F first #define S second const int N = 100000 + 5; const int M = 1000 + 5; const int LN = 131072; const int MOD = 1e9 + 7;//998244353; const int BLOCK = 500; const int inf = 1e12; const int INF = 1e18; const double pi = 3.14159265358979323846; const vector<array<int, 2>> DS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int binpow(int a, int b) {//, int MOD) { int res = 1; a %= MOD; while (b > 0) { if (b & 1) { res = res * a; res %= MOD; } a = a * a; a %= MOD; b >>= 1; } return res; } int mdiv(int a, int b) { int ret = (a % MOD) * binpow(b, MOD - 2); ret %= MOD; return ret; } int mul(int a, int b) { int ret = (a % MOD) * (b % MOD); ret %= MOD; return ret; } int add(int a, int b) { int ret = (a % MOD) + (b % MOD); ret %= MOD; return ret; } int sub(int a, int b) { int ret = (a % MOD) - (b % MOD); ret = (ret + MOD) % MOD; return ret; } int GCD(int a, int b) { if (b == 0) { return a; } return GCD(b, a % b); } struct pqComp { bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) { return (p1.F < p2.F) || (p1.F == p2.F && p1.S < p2.S); } }; bool pCompF(pair<int, int>& p1, pair<int, int>& p2) { return p1.F < p2.F; } bool pCompS(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.S < p2.S; } bool pCompFS(pair<int, int>& p1, pair<int, int>& p2) { return (p1.S < p2.S) || (p1.S == p2.S && p1.F < p2.F); } vector<int> g[2*N]; int dfs(int v, int vv, vector<int> &path, int p = 0) { path.pub(v); if (v == vv) { return 1; } for (int u: g[v]) { if (u == p) continue; if (dfs(u, vv, path, v)) { return 1; } } path.pob(); return 0; } void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i < n; ++i) { int v, u; cin >> v >> u; vector<int> path; dfs(1, v, path); int cnt = 0; for (int j = 0; j < path.size(); ++j) { for (int k = 0; k < j; ++k) { if (a[path[k]] > a[path[j]]) { cnt++; } } } cout << cnt << '\n'; for (int j: path) { a[j] = a[u]; } g[v].pub(u); g[u].pub(v); } } signed main() { speed; int T = 1; //cin >> T; while (T--) { solve(); } } /* НЕ ЗАХОДИТ РЕШЕНИЕ? 1) ПРОВЕРЬ НА ОЧЕВИДНЫЕ ОШИБКИ В КОДЕ 2) ПРОВЕРЬ НА ПЕРЕПОЛНЕНИЯ 3) УБЕДИСЬ В ПРАВИЛЬНОСТИ АЛГОРИТМА */