题目描述

译自 JOI $2023$ Final T4「キャットエクササイズ / Cat Exercise」

有 $N$ 个猫爬架，从 $1$ 到 $N$ 编号。猫爬架 $i$ $(1\le i\le N)$ 的高度为 $P_i$。猫爬架的高度是 $1$ 到 $N$ 之间（包括两端）互不相同的整数。有 $N-1$ 对相邻的猫爬架。对于每个 $j$ $(1\le j\le N-1)$，猫爬架 $A_j$ 和 $B_j$ 相邻。最初，可以从任意猫爬架开始，通过移动到与其相邻的猫爬架到达任意其他猫爬架。

在最初，一只猫处在高度为 $N$ 的猫爬架上。

然后我们训练这只猫。在训练中，我们不断选择一个猫爬架，然后在它上面放置一个障碍物。然而，我们不能把障碍物放在已经放有障碍物的猫爬架上。在这个过程中，如下事件会发生。

• 如果猫没在这个选中的猫爬架上，那么什么都不会发生。
• 如果猫处于这个选中的猫爬架上，并且所有与其相邻的猫爬架上都有障碍物，那么训练结束。
• 否则，在猫可以通过不断移动到相邻且没有障碍物的猫爬架的方式到达的所有猫爬架中，猫将选择除目前所在猫爬架以外最高的那个，并移动到那里去。在这个过程中，猫将选择最短路径移动。

给定猫爬架的高度信息和相邻的猫爬架对，写一个程序计算如果我们恰当地放置障碍物，每次操作中猫移动次数之和的最大值是多少。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

接下来 $N-1$ 行，每行两个整数 $A_j,B_j$。

输出格式

输出一行一个整数，表示每次操作中猫移动次数之和的最大值。

样例 1

输入

4
3 4 1 2
1 2
2 3
3 4

输出

3

如果我们按如下方式进行训练，那么猫总共会移动 $3$ 次。

1. 我们把障碍物放在猫爬架 $1$ 上，猫不会动。
2. 我们把障碍物放在猫爬架 $2$ 上，猫从猫爬架 $2$ 移动到 $3$。然后又从 $3$ 移动到 $4$。
3. 我们把障碍物放在猫爬架 $4$ 上，猫从猫爬架 $4$ 移动到 $3$。
4. 我们把障碍物放在猫爬架 $3$ 上，然后训练结束。

因为没有能让猫移动 $4$ 次及以上的方式，因此输出 $3$。

这组样例满足子任务 $1,2,3,4,5,7$ 的限制。

样例 2

输入

7
3 2 7 1 5 4 6
1 2
1 3
2 4
2 5
3 6
3 7

输出

7

这组样例满足子任务 $4,6,7$ 的限制。

数据范围与提示

对于全部数据，满足

• $2\le N\le 2\times 10^5$
• $1\le P_i\le N\ (1\le i\le N)$
• $P_i\neq P_j\ (1\le i<j\le N)$
• $1\le A_j<B_j\le N\ (1\le j\le N-1)$
• 最初，可以从任意猫爬架开始，通过移动到与其相邻的猫爬架到达任意其他猫爬架。

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$A_i=i,B_i=i+1\ (1\le i\le N-1),N\le 16$	$7$
2	$A_i=i,B_i=i+1\ (1\le i\le N-1),N\le 300$
3	$A_i=i,B_i=i+1\ (1\le i\le N-1),N\le 5\,000$
4	$N\le 5\,000$	$10$
5	$A_i=i,B_i=i+1\ (1\le i\le N-1)$	$20$
6	$A_i=\lfloor\frac{i+1}{2}\rfloor,B_i=i+1\ (1\le i\le N-1)$，其中 $\lfloor x\rfloor$ 是小于等于 $x$ 的最大整数	$23$
7	无附加限制	$26$