洗

小S有一个\(n\)个节点的二叉树。每个节点上有一个权值。节点从\(1\)开始编号。

现在，小S打算把这个二叉树改造成一个二叉排序树。二叉排序树的定义是，对于每个节点，它的权值比它左子树的权值要大，但是比右子树要小。

现在，他想要修改某些节点的权值，使得它成为一个二叉排序树。请问最小的修改次数是多少。

输入格式
第一行一个整数\(n\)。

接下来一行\(n\)个数，第\(i\)个表示\(i\)号节点的权值。

接下来 \(n?1\)行，每行两个非负整数\(f\), \(x\)，第\(i\)行描述结点\(i+1\)的父亲编号\(f\)，以及父子关系\(x\)，(\(x = 0\) 表示\(i + 1\)为左儿子，\(x = 1\)表示\(i + 1\)为右儿子)。

保证一号点一定是全树的根。

输出格式
一行一个整数，表示最小修改次数。

样例
样例一
input

3
2 2 2
1 0
1 1

output

2

约定与限制
对于\(20\%\) 的数据，满足 \(n\le10,a_i\le100\)。

对于\(40\%\) 的数据，满足 \(n\le100,a_i\le200\)。

对于\(60\%\) 的数据，满足 \(n\le2000\)。

对于\(100\%\) 的数据 ，满足 \(1\le n\le10^5,a_i<2^{31}\) 。

时间限制:1s

空间限制:512MB

二叉排序树有一个很优美的性质：他的中序遍历序列是一个严格单调递增序列。所以我们求出中序遍历序列后考虑直接在序列上做修改。问题变成了，给出一个序列，问至少要改多少个数使得序列严格单调递增。
严格单调很难处理，所以我们给每一位减去他的下标后，问题转换成至少要改多少个数使得序列不下降。，然后求出一个最长不下降序列，那么剩下的数就是要改的。