题目描述

小信在学习某一个新技能的时候习惯说是“点技能点”，比如学习了 C 语言，就会说点了一下 C 语言的技能点。

我们总共有 $n$ 个可以学习的技能，每个技能都会有一个收获值 $a_i$。然后有 $n-1$ 个两两技能连接关系 $(u,v)$，保证从其中一个技能出发可以到达到其它所有的技能处。

我们从 $1$ 号技能出发，遍历所有的技能。由于精力有限，我们只能选择一条从 $1$ 号技能出发的技能链。在这条技能链上，我们能够点的技能也有限制：每一个新点的技能收获值必须大于等于前一个技能收获值。

请问我们最多能点几个技能点。

输入格式

第一行输入一个整数 $n$，表示技能个数。
第二行包含 $n$ 个整数，表示每个技能的收获值 $a_i$。
接下来 $n-1$ 行，每行两个整数 $u, v$，表示技能 $u$ 和 $v$ 相连。

输出格式

输出一个整数，表示最多能选的技能点数量。

样例

Input 1

5
3 1 2 7 9
1 2
1 3
2 4
2 5

Output 1

2

数据范围

• 对于 $10\%$ 的数据，是一条 $1 \to 2 \to 3 \to \dots \to n$ 的递增链，且每个技能的收获值单调递增。
• 对于另外 $10\%$ 的数据，是一条链，且 $n \leq 20$。
• 对于另外 $10\%$ 的数据，是一条链，且 $n \leq 5000$。
• 对于另外 $20\%$ 的数据，$n \leq 500$。
• 对于另外 $50\%$ 的数据，$1 \leq n \leq 5000$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq a_i \leq 5000$，$1 \leq u, v \leq n$。

样例解释

对于样例 1，所有从 $1$ 号技能出发的技能链有：

• $1 \to 2 \to 4$：可以选择技能 $1$ 和 $4$（收获值 $3$ 和 $7$，$3 \leq 7$），或技能 $2$ 和 $4$（收获值 $1$ 和 $7$，$1 \leq 7$）。
• $1 \to 2 \to 5$：可以选择技能 $1$ 和 $5$（收获值 $3$ 和 $9$），或技能 $2$ 和 $5$（收获值 $1$ 和 $9$）。
• $1 \to 3$：只能选择技能 $1$（收获值 $3$）或技能 $3$（收获值 $2$），但无法形成两个技能点的序列，因为 $3 \geq 2$ 不满足递增条件。

因此，最大技能点数量为 $2$。