题目描述

在一片森林中有 $n$ 个树木，编号从 $1$ 到 $n$。每棵树都有一个高度 $h_i$。

树木之间有道路相连，形成了一棵树结构（即任意两棵树之间有且仅有一条简单路径）。

现在森林管理员想要研究火灾的蔓延规律。他发现：

• 如果一棵树着火，火势会沿着道路向相邻的树木蔓延
• 但火势只能从较高的树蔓延到较低的树（高度严格小于当前燃烧的树）

管理员可以选择任意一棵树作为初始着火点。请问：在最优选择下，最多可以有多少棵树被烧毁？

输入格式

第一行包含一个正整数 $n$，表示树木的数量。

第二行包含 $n$ 个正整数 $h_1, h_2, \dots, h_n$，代表每棵树的高度。

之后 $n-1$ 行，每行包含两个正整数 $u_i, v_i$，代表存在一条道路连接树木 $u_i$ 和 $v_i$。

输出格式

输出一个正整数，代表最多可以烧毁的树木数量。

输入输出样例 #1

输入 #1

5
6 2 3 4 5
1 2
2 3
2 5
1 4

输出 #1

3

输入输出样例 #2

输入 #2

3
10 5 8
1 2
2 3

输出 #2

2

输入输出样例 #3

输入 #3

4
100 90 80 70
1 2
2 3
3 4

输出 #3

4

数据范围

对于全部数据，保证有 $1\leq n\leq 10^5$，$1\leq h_i\leq 10^6$。

提示

• 每个节点能烧毁的树木数量 = 1（自身）+ 所有能到达的比它低的子树的烧毁数量之和
• 由于树是无向的，需要考虑从父节点蔓延过来的情况
• 注意：火势只能从高向低蔓延，不能向上蔓延