Có \(N\) tháp dành cho mèo, được đánh số từ \(1\) đến \(N\). Tháp \(i\) (\(1 \le i \le N\)) có chiều cao \(P_i\). Chiều cao của các tháp là các số nguyên đôi một khác nhau từ \(1\) đến \(N\).

Có \(N - 1\) cặp tháp kề nhau. Với mỗi \(j\) (\(1 \le j \le N - 1\)), tháp \(A_j\) và tháp \(B_j\) kề nhau. Ban đầu, có thể đi từ bất kỳ tháp nào đến bất kỳ tháp nào khác bằng cách liên tục di chuyển sang một tháp kề.

Ban đầu, một chú mèo ở trên tháp có chiều cao \(N\).

Ta cho mèo tập thể dục bằng cách lặp lại thao tác chọn một tháp và đặt chướng ngại vật lên tháp đó. Không được đặt chướng ngại vật lên tháp đã có chướng ngại vật. Sau mỗi thao tác, các trường hợp sau xảy ra:

• Nếu mèo không ở trên tháp được chọn, không có gì xảy ra.
• Nếu mèo ở trên tháp được chọn và tất cả các tháp kề với tháp đó đều có chướng ngại vật, buổi tập kết thúc.
• Trong trường hợp còn lại, xét các tháp mà mèo có thể đi đến từ tháp hiện tại bằng cách liên tục di chuyển sang một tháp kề không có chướng ngại vật. Trong số đó, bỏ qua tháp hiện tại, mèo sẽ đi đến tháp cao nhất. Mèo chọn đường đi có số lần di chuyển sang tháp kề ít nhất.

Cho chiều cao của các tháp và các cặp tháp kề nhau, hãy tìm tổng số lần di chuyển sang tháp kề lớn nhất mà mèo có thể thực hiện nếu ta đặt các chướng ngại vật một cách phù hợp.

Dữ liệu vào

Dữ liệu vào có dạng:

N
P_1 P_2 ... P_N
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}

Dữ liệu ra

In trên một dòng tổng số lần di chuyển sang tháp kề lớn nhất mà mèo có thể thực hiện.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le P_i \le N\) (\(1 \le i \le N\)).
• \(P_i \ne P_j\) (\(1 \le i < j \le N\)).
• \(1 \le A_j < B_j \le N\) (\(1 \le j \le N - 1\)).
• Ban đầu, có thể đi từ bất kỳ tháp nào đến bất kỳ tháp nào khác bằng cách liên tục di chuyển sang một tháp kề.
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 16\).
2. \(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 300\).
3. \(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 5000\).
4. \(10\) điểm: \(N \le 5000\).
5. \(20\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\).
6. \(23\) điểm: \(A_i = \left\lfloor \frac{i + 1}{2} \right\rfloor\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\).
7. \(26\) điểm: Không có ràng buộc bổ sung.

Ở đây, \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ

4
3 4 1 2
1 2
2 3
3 4

3

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

7

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.