Description

有 $N$ 个猫塔，编号从 $1$ 到 $N$。塔 $i$ 的高度为 $P_i$（$1 \le i \le N$）。这些塔的高度是 $1$ 到 $N$ 之间的不同整数。共有 $N - 1$ 对相邻的塔。对于每个 $j$（$1 \le j \le N - 1$），塔 $A_j$ 和塔 $B_j$ 是相邻的。最开始，可以通过从一个塔移动到相邻的塔，来从一个塔到达任何其他塔。

最开始，一只猫待在高度为 $N$ 的塔上。

然后我们进行猫运动。在猫运动中，我们反复选择一个塔并在其上放置一个障碍。然而，我们不能在已经放置障碍的塔上再放置障碍。在这个过程中，将发生以下情况：

• 如果猫不在所选的塔上，什么也不会发生。
• 如果猫在所选的塔上，并且所选塔的每个相邻塔上都有障碍，猫运动将结束。
• 否则，在猫可以通过从塔移动到相邻塔而不受障碍影响到达的塔中，猫将移动到除当前塔外最高的塔。过程中，猫会选择从塔移动到相邻塔的步数最少的路线。

给定塔的高度信息和相邻塔的对，编写程序计算在适当放置障碍的情况下，猫从塔移动到相邻塔的最大可能移动次数之和。

Input Format

从标准输入读取以下数据。

$N$
$P_1$ $P_2$ $\cdots$ $P_N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

Output Format

向标准输出写入一行。输出应包含猫从塔移动到相邻塔的最大可能移动次数之和。

4
3 4 1 2
1 2
2 3
3 4

3

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

7

Hint

样例

样例 1

如果我们按以下方式进行猫运动，猫总共移动 3 次。

• 我们在塔 1 上放置一个障碍。猫不移动。
• 我们在塔 2 上放置一个障碍。猫从塔 2 移动到塔 3。然后，猫从塔 3 移动到塔 4。
• 我们在塔 4 上放置一个障碍。猫从塔 4 移动到塔 3。
• 我们在塔 3 上放置一个障碍。然后猫运动结束。

由于没有办法进行猫运动，使得猫从塔移动到相邻塔的次数大于或等于 4，因此输出 3。

此样例输入满足子任务 1、2、3、4、5、7 的约束。

样例 2

此样例输入满足子任务 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. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 16$。
2. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 300$。
3. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 5 000$。
4. (10 分) $N \le 5 000$。
5. (20 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)。
6. (23 分) $A_i =\left\lfloor\frac{i+1}2\right\rfloor, B_i = i + 1$ ($1 \le i \le N - 1$)。这里 $\lfloor x \rfloor$ 是小于或等于 $x$ 的最大整数。
7. (26 分) 无额外约束。

题面翻译由 ChatGPT-4o 提供。