题目描述

在神秘的魔法森林深处，生长着一棵由 $n$ 个水晶节点组成的二叉树。第 $i$ 个节点上镶嵌着一颗魔法水晶，其能量值为 $a_i$。保证节点 $1$ 是这棵树的根。

一位探险家计划从某个节点出发，沿着向下的树枝（即从父节点走向子节点）不断前进，并在任意时刻停下。行进途中，他可以收集途经节点上的水晶，但要求收集的水晶能量值严格递增（后收集的能量必须严格大于前一个）。他不必收集路径上的每一颗水晶，允许跳过某些节点。

请问，探险家最多能收集多少颗水晶？

输入格式

第一行一个正整数 $n$，表示节点个数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个节点的魔法能量值。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i, r_i$：

• 若 $l_i = -1$，表示第 $i$ 个节点没有左子节点；否则左子节点编号为 $l_i$。
• 若 $r_i = -1$，表示第 $i$ 个节点没有右子节点；否则右子节点编号为 $r_i$。

保证节点 $1$ 是根节点，且输入构成一棵合法的二叉树。

输出格式

输出一行一个整数，表示最多能收集的水晶数量。

样例 #1

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

3

样例解释 #1

树的结构如下：

        1(1)
       /    \
    2(3)    3(2)
    /   \
 4(4)  5(5)

括号内为能量值。最优方案之一：从节点 $1$（能量 $1$）出发，经过节点 $2$（能量 $3$），到达节点 $4$（能量 $4$），收集序列 $1 \to 3 \to 4$，长度为 $3$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 5000$，$|a_i| \le 10^9$。