문제

이더리움과 같은 블록체인 네트워크에서는 데이터를 블록 단위로 연결하여 기록한다. 그런데 네트워크 통신 지연으로 인해 하나의 블록에 여러 자식 블록이 연결되면서, 트리가 여러 갈래로 갈라지는 포크(Fork) 현상이 종종 발생한다.

이렇게 갈라진 기록을 하나로 통일하기 위해, 트리에서 가장 신뢰할 수 있는 단 하나의 경로를 골라 최종 기록으로 확정한다. 이 경로를 캐노니컬 체인(Canonical Chain)이라고 부른다.

영우가 모니터링 중인 네트워크는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 블록으로 이루어진 트리 구조이며, 루트는 최초의 블록인 $1$번 블록이다. 네트워크의 참여자들은 자신이 신뢰하는 블록에 투표를 진행하며, 이에 따라 각 블록 $i$에는 투표 가중치 $W_i$가 부여된다.

영우는 LMD-GHOST라 불리는 다음 탐색 규칙을 통해 캐노니컬 체인의 마지막 블록인 헤드를 결정한다.

1. $1$번 블록에서 탐색을 시작한다.
2. 현재 블록에 자식이 있으면, 각 자식에 대해 그 자식을 루트로 하는 서브트리에 속한 모든 블록의 투표 가중치 합을 계산한다. 이 합에는 해당 자식 블록 자신의 가중치도 포함된다.
3. 계산한 합이 가장 큰 자식으로 이동한다. 합이 가장 큰 자식이 여러 개이면, 번호가 가장 작은 자식으로 이동한다.
4. 자식이 없는 블록에 도달하면 탐색을 종료한다. 이 블록이 캐노니컬 체인의 헤드이다.

블록들의 연결 정보와 각 블록의 투표 가중치가 주어질 때, 캐노니컬 체인의 헤드 번호를 구하시오.

입력

첫째 줄에 트리를 구성하는 블록의 개수 $N$이 주어진다. $(2 \le N \le 200,000)$

둘째 줄에 $1$번 블록부터 $N$번 블록까지 각 블록의 투표 가중치 $W_i$가 공백으로 구분되어 주어진다. $(0 \le W_i \le 10^9)$

다음 $N - 1$개의 줄 중 $i$번째 줄에는 두 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다. $(1 \le u_i, v_i \le N)$

간선은 양방향으로 주어진다. 주어지는 그래프는 중복 간선과 self-loop가 없는 연결 그래프이며, 항상 트리이다. 부모-자식 관계는 $1$번 블록을 루트로 하여 결정한다.

출력

캐노니컬 체인의 헤드로 확정되는 블록의 번호를 출력한다.

예제 입력 1

7
0 10 5 2 8 20 0
1 2
1 3
2 4
2 5
3 6
3 7

예제 출력 1

6

예제 입력 2

5
0 0 5 20 15
1 2
1 3
2 4
3 5

예제 출력 2

4