题目描述

王乐妍是一个喜欢搬过去模拟赛题的可爱学妹。

王乐妍在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最 多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作 二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。

可惜王乐妍对于看错题了，她对二叉搜索树的定义理解出了亿点偏差，故一 切有关二叉搜索树的定义以题意为准，请仔细读题。

什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设 $k_p$ 表示结点 $p$ 上的数值。 对于其中的每个结点 $p$，若其存在左孩子 $l$，则 $k_p > k_l$ 若其存在右孩子 $r$，则 $k_p < k_r$ 注意，本题中的二叉搜索树仅需满足该节点大于左儿子，小于右儿子即可，不必满足大 于左子树中的所有节点，同样，不必满足小于右子树中的所有节点。

王乐妍与他人讨论的内容则是，现在给定一棵二叉树，可以任意修改结点的数值。修 改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且任意时刻结点的数值必须是整数（可以是负整数或 $0$），所要的最少修改次数。

输入格式

第一行一个正整数 $n$ 表示二叉树结点数。结点从 $1$ ∼ $n$ 进行编号。

第二行 $n$ 个非负整数用空格分隔开，第 $i$ 个数 $a_i$ 表示结点 $i$ 的原始数值。

此后 $n − 1$ 行每行两个非负整数 $fa, ch$，第 $i + 2$ 行描述结点 $i + 1$ 的父亲编号 $fa$， 以及父子关系 $ch$，$ch = 0$ 表示 $i + 1$ 为左儿子，$ch = 1$ 表示 $i + 1$ 为右儿子。

结点 $1$ 一定是二叉树的根。

输出格式

仅一行包含一个整数，表示最少的修改次数。

样例1

3
2 2 2
1 0
1 1

2

样例2

7
8 9 3 4 2 3 3
1 0
2 0
1 1
3 0
4 0
4 1

3

数据范围与提示

本题共有 20 个测试点，每个测试点 5 分。

每个测试点的具体限制见下表。

注意本题输入数据较大，你可能需要使用较快的读入方式。