日本有 $N$ 个城市，它们之间由 $N-1$ 条双向道路连接。从任意一个城市出发，都可以通过若干条道路到达其他任何城市。每个城市都有一座市政大楼，城市 $i$ 的大楼高度为 $H_i$。

随着国际信息学奥林匹克竞赛在日本举行，为了欢迎世界各地的选手，我们计划组织一次观光旅游。观光旅游从某个城市出发，沿着道路反复移动到不同的城市，最后在某个城市结束。在此过程中，不能访问同一个城市两次以上。

为了更好地欢迎世界各地的选手，我们决定装饰观光途中经过的部分城市的市政大楼。一位著名设计师受邀进行设计，他指出，用于装饰的大楼高度必须从出发城市到到达城市呈递增趋势。也就是说，如果我们选择的装饰城市序列为 $i_1, i_2, \dots, i_k$，且在观光旅游中按 $i_1, i_2, \dots, i_k$ 的顺序访问这些城市，那么大楼高度必须满足 $H_{i_1} < H_{i_2} < \dots < H_{i_k}$。（注意，并不要求必须装饰所有经过的城市。）

题目描述

为了使装饰尽可能华丽，我们希望尽可能多地利用大楼进行装饰。在可以自由选择起始城市、结束城市以及装饰大楼的城市的情况下，请编写一个程序，计算出可以用于装饰的大楼数量的最大值。

数据范围

$2 \le N \le 100\,000$ 城市数量 $1 \le H_i \le 1\,000\,000\,000$ 城市 $i$ 的大楼高度

输入格式

从标准输入读取以下内容：

• 第 1 行包含一个整数 $N$，表示城市数量。
• 接下来的 $N$ 行提供了关于各城市市政大楼高度的信息。其中第 $i$ 行包含一个整数 $H_i$，表示城市 $i$ 的大楼高度为 $H_i$。
• 接下来的 $N-1$ 行提供了关于道路的信息。其中第 $i$ 行包含两个空格分隔的整数 $A_i, B_i$ ($1 \le A_i < B_i \le N$)，表示第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。

输出格式

将可以用于装饰的大楼数量的最大值作为一个整数输出到标准输出。

子任务

• 在测试数据中，满足 $N \le 100$ 的数据占总分值的 10%。
• 在测试数据中，满足 $N \le 2\,000$ 的数据占总分值的 30%。

样例

样例输入 1

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

样例输出 1

4