题目描述

小 A 又有一棵 $n$ 个点的无根树，树上的每个点还是有一个权值 $a_i$。对于树上的两个点 $u\to v$，定义 $L(u,v)$ 为将树上 $u\to v$ 的最短路径经过的点的点权列成序列，其最长上升子序列（LIS）的长度。

现在小 A 需要删掉树上的一个点 $x$，删掉 $x$ 后这棵树会被分为若干棵子树 $S_1,\dots,S_k$。定义 $F(x)=\max_{i=1}^k (\max\limits_{u,v\in S_i} L(u,v))$，即删除点 $x$ 后森林中 LIS 最长的路径，小 A 想要你求出 $\min\limits_x F(x)$，即删除一个点使得森林中 LIS 最长的路径的 LIS 长度最小。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,\dots,a_n$ 表示点的权值。

接下来 $n-1$ 行每行两个整数 $u,v$ 表示一条边。

输出格式

输出一行一个整数表示答案，即 $\min\limits_u F(u)$。

输入样例1

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

输出样例1

2

数据范围

对于所有测试点，$1\le n\le 10^5$，$1\le a_i\le n$。