Nhà phê bình ẩm thực du hành đất nước

Bạn là một nhà phê bình ẩm thực vừa hoàn thành cuộc thi chọn học sinh giỏi văn hóa lớp \(12\) môn Tin học, và bạn bắt đầu du hành qua một đất nước với \(N\) thành phố. Mỗi thành phố có một nhà hàng được đánh giá bằng một số sao, cho thấy mức độ tốt của nó. Đất nước này có \(N - 1\) con đường, sao cho giữa hai thành phố bất kỳ có duy nhất một con đường đơn giản nối chúng lại với nhau.

Là một nhà phê bình ẩm thực rất nghiêm khắc, bạn chỉ ăn ở một nhà hàng mới nếu nó có số sao cao hơn nhà hàng mà bạn đã ăn lần trước. Tuy nhiên, bạn cũng rất thích ăn uống, vì vậy bạn muốn ghé thăm số lượng nhà hàng lớn nhất có thể trong hành trình của mình, tuân theo các quy tắc sau:

• Bạn có thể ăn ở nhiều nhà hàng nhất có thể trong suốt hành trình.
• Bạn không quay lại trên cùng một con đường mà bạn đã đi qua.

Bạn cần lên kế hoạch một hành trình bắt đầu từ một thành phố \(A\) và kết thúc ở một thành phố \(B\), đảm bảo rằng:

• Bạn có thể ăn ở nhiều nhà hàng nhất có thể trong hành trình.
• Bạn không quay lại trên cùng một con đường mà bạn đã đi qua.

Lưu ý rằng bạn không nhất thiết phải ăn ở mỗi thành phố mà bạn đi qua, mà chỉ cần đi qua chúng.

Bạn có thể giúp nhà phê bình tối đa hóa trải nghiệm ăn uống của mình không?

Input

• Dòng đầu tiên chứa một số nguyên \(N\), là số thành phố.
• Dòng thứ hai chứa \(N\) số nguyên, số nguyên thứ \(i\) là số sao của nhà hàng tại thành phố \(i\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\), chỉ ra một con đường giữa các thành phố \(u\) và \(v\).

Output

In ra số lượng nhà hàng tối đa mà nhà phê bình có thể ăn tại, dưới các ràng buộc đã cho.

Example

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

3

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

4

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

1

Scoring

• \(2 \leq N \leq 10^5\).
• \(1 \leq S_{i} \leq 10^5\), với \(S_{i}\) là số sao của nhà hàng tại thành phố \(i\).
• \(1 \leq u \neq v \leq N\), với mọi cặp \((u, v)\).

\(25\%\) số điểm có \(N \leq 20\).

\(25\%\) số điểm có \(20 < N \leq 100\).

\(25\%\) số điểm có \(100 < N \leq 50000\).

\(20\%\) số điểm có \(50000 < N \leq 100000\).