题目描述

给定一棵有根树，节点编号为 $1,2,\dots,N$，其中点 $1$ 为树的根。节点 $i$ 有权值 $V[i]$。你现在需要修改节点的权值，使得它们满足以下性质：

对任意节点 $i,j$，若节点 $i$ 为节点 $j$ 的祖先，则有 $V[i] \le V[j]$。

现在的问题是，你最少需要修改多少个节点的权值，才能满足上述性质。注意，修改后的权值需要保证为一个正整数。

输入格式

• 第一行输入一个正整数 N
• 第二行输入 N 个正整数 V[1],...,V[N]
• 接下来 N-1 行，每行两个整数，代表树上的一条边

输出格式

输出一行一个整数代表最少需要修改的节点个数。

数据范围

• 对于 30% 的数据：N <= 100
• 对于 60% 的数据：N <= 3000
• 对于 100% 的数据：N <= 200000, 1 <= V[i] <= 1e9

输入样例

输入样例 1

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

输入样例 2

14
901 453 981 721 81 171 53 903 882 465 219 101 983 901
12 4
4 2
2 11
11 13
13 3
3 1
1 8
8 7
7 5
5 14
4 6
7 9
1 10

输入样例 3

28
731 199 179 129 448 645 601 325 426 131 83 681 401 87 966 695 801 803 322 1000 357 981 585 397 601 936 330 611
4 1
1 13
13 24
24 14
14 23
23 25
13 6
23 2
4 10
25 3
4 26
4 16
2 22
14 11
16 18
1 17
25 8
18 7
24 28
7 9
4 27
18 21
2 5
25 15
26 19
7 20
4 12

输出样例

输出样例 1

3

输出样例 2

6

输出样例 3

10