题意

给出几个点的树，节点编号为 1 到 n，根节点为 1，每个节点有一个权值。

我们想在这棵树上找一条最长的链，使得这个链上的节点均满足 $a_{f_n} <= a_i$ 或者均满足 $a_{f_n} >= a_i$，其中 $fa_i$ 表示的父亲节点，我们假定 $fa_1 = 1$。

输出这个最长链的节点数。

输入描述

第一行输入一个整数 $n(1 \leq n \leq 10^5)$代表树上的节点个数。

第二行输入 n 个整数 $a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^5)$代表每一个节点的权值。

此后 n-1 行，每行输入两个整数 $u_i$ 和 $v_i(1 \leq u_i, v_i \leq n; u_i \neq v_i)$表示树上第 i 条边连接节点 $u_i$ 和 $v_i$。保证树是联通的，没有重边。

输出描述

在一行上输出一个整数代表最长链的节点个数。

示例

输入：

5
1 2 3 4 5
1 2
2 3
1 4
4 5

输出：

5

解释：最长的链是 3 → 2 → 1 → 4 → 5。