有 $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$ $P_1 \ P_2 \ \dots \ P_N$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_{N-1} \ B_{N-1}$

输出格式

输出一行到标准输出，包含猫从一座塔移动到相邻塔的次数之和的最大值。

数据范围

• $2 \le N \le 200\,000$
• $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 = \lfloor \frac{i+1}{2} \rfloor, B_i = i + 1$ ($1 \le i \le N-1$)。这里 $\lfloor x \rfloor$ 是小于或等于 $x$ 的最大整数。
7. (26 分) 无附加限制。

样例

样例输入 1

4
3 4 1 2
1 2
2 3
3 4

样例输出 1

3

说明 1

如果我们按以下方式进行猫的练习，猫总共移动 3 次：

• 我们在塔 1 上放置障碍物。猫没有移动。
• 我们在塔 2 上放置障碍物。猫从塔 2 移动到塔 3。然后，猫从塔 3 移动到塔 4。
• 我们在塔 4 上放置障碍物。猫从塔 4 移动到塔 3。
• 我们在塔 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

样例输出 2

7

说明 2

该样例输入满足子任务 4, 6, 7 的限制。