题目背景

Galaxy 和 Gouk 再次升级了珍珠炮网络，是时候测试系统的稳定性了！

题目描述

请注意：本题是 传送路径 A 的困难版本，两个版本的区别仅在于数据范围不同，保证 传送路径 A 的测试数据是 传送路径 B 的子集。

这套传送系统由一台主炮和 n 门定向子炮组成，位于世界生成点的主炮能将玩家传送至任意一个子炮，而每门子炮只能与另一或两门子炮定向传送，子炮间 n - 1 条双向传送路径连接起了世界的天涯海角，直到边缘之地，世界的尽头...

由于投影和朝向的不同，每门子炮的复杂度 d_i 都不尽相同，粗心大意的 Galaxy 在测试了更为复杂的子炮之后，就会直接忽略较为简单的子炮 （这也是为什么他的代码总是犯一些低级错误）。

现在，Galaxy 将从主炮出发，传送至某一门子炮作为测试的起点，传送向其他子炮的旅途中，有选择性地测试其中的一些子炮。只有复杂度严格高于上一门被测试过的子炮，才可以被 Galaxy 测试（同样也可以选择不测试这门子炮）。

测试开始前，认为上一门被测子炮的复杂度为 0，如果不走回头路，请问 Galaxy 最多能测试多少门子炮？

形式上，给定一颗由 n 个节点和 n - 1 条双向边的无根树，每个节点有权重 d_i，任选起点和终点，遍历它的简单路径，并在路径上选择一段权重严格递增的子序列，使子序列的长度尽可能大，求子序列的最大长度。

第一行包含一个整数 n (2 \leq n \leq 10^5) - 子炮的数量。

第二行包含 n 个整数 d_i (1 \leq d_i \leq 10^5) - 每门子炮的复杂度。

接下来 n - 1 行，每行两个整数 u, v (1 \leq u \neq v \leq n) - 描述一条无向边，连接节点 u, v。

数据保证构成一棵树。

输出一个整数，表示最多有多少门子炮可以被测试

以 2 号子炮为起点，5 号子炮为终点， 可测试 2,4,5 号子炮。

或者以 3 号子炮为起点，5 号子炮为终点， 可测试 3,1,5 号子炮。

尚有其他测试方式不再列出，可证明不可能测试四台子炮。