건물 2

일본에는 $N$개의 도시가 있고, 도시들은 $N-1$개의 양방향 도로로 연결되어 있다. 어떤 도시에서든 도로를 따라 다른 모든 도시로 이동할 수 있다. 각 도시에는 관청 건물이 하나씩 있으며, 도시 $i$의 건물 높이는 $H_i$이다.

국제정보올림피아드가 일본에서 열리는 것을 맞아 세계 선수들을 환영하는 관광 투어를 계획하고 있다. 투어는 한 도시에서 출발해 도로를 따라 다른 도시로 이동하기를 반복하며, 어떤 도시에서 끝난다. 같은 도시는 두 번 이상 방문할 수 없다.

환영 분위기를 더 살리기 위해 투어 중 방문하는 일부 도시의 관청 건물을 장식하기로 했다. 디자이너는 장식에 쓰는 건물이 출발 도시에서 도착 도시로 갈수록 높아져야 한다고 했다. 장식할 도시를 $i_1, i_2, \ldots, i_k$라 하고, 투어에서 이 도시들을 이 순서대로 방문한다면 $H_{i_1} < H_{i_2} < \cdots < H_{i_k}$이어야 한다. 방문한 건물을 모두 장식할 필요는 없다.

장식을 최대한 화려하게 하려고 한다. 출발 도시, 도착 도시, 장식할 도시를 자유롭게 고를 때, 장식에 쓸 수 있는 건물 수의 최댓값을 구하는 프로그램을 작성하라.

표준 입력으로 다음 입력을 읽어라.

• 첫 줄에는 도시의 수를 나타내는 정수 $N$이 주어진다.
• 이어서 $N$개의 줄에 각 도시 관청 건물의 높이가 주어진다. $i$번째 줄에는 도시 $i$의 건물 높이 $H_i$가 적혀 있다.
• 이어서 $N-1$개의 줄에 도로 정보가 주어진다. $i$번째 줄에는 공백으로 구분된 정수 $A_i$, $B_i$ ($1 \le A_i < B_i \le N$)가 적혀 있으며, 이는 $i$번째 도로가 도시 $A_i$와 도시 $B_i$를 잇는다는 뜻이다.

표준 출력에 장식에 쓸 수 있는 건물 수의 최댓값을 정수로 출력하라.

$2 \le N \le 100000$ (도시의 수)

$1 \le H_i \le 1000000000$ (도시 $i$ 건물의 높이)