题目描述

有一棵 $n$ 个节点的二叉树，$1$ 为根节点，每个节点有一个值 $w_i$。现在要选出尽量多的点。

对于任意一棵子树，都要满足：

如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值​大​；

如果在左子树选了一个点，在右子树中选的其他点要比它​小​。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $w_{i}$ , 表示每个点的极值。

接下来 $n$ 行, 每行两个整数 $a, b$ 。第 $i+2$ 行表示第 $i$ 个节点的左右儿子节点。没有为 $0$ 。 $n, a, b \leq 10^{5},-2 \times 10^{9} \leq w_{i} \leq 2 \times 10^{9}$。

输出格式

一行一个整数表示答案。

样例输入输出

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

3