숙제

린은 이제 다 커서 곧 대학에 들어간다. 하지만 입학은 그리 쉽지 않다. 그래서 린은 준비하려고 지난 해 문제들을 풀어 보기로 했다.

작년 입학 시험 문제 중 하나는 다음과 같았다. 트리가 주어지고, $i$번 정점에는 정수 $a_i$가 적혀 있다. 참가자는 다음 합을 구해야 했다.

$\sum_{i=1}^n \sum_{j=i}^n (\max(i \ldots j)-\min(i \ldots j)) \cdot len(i \ldots j)$

여기서 $\max(i \ldots j)$는 $i$에서 $j$까지 가는 경로 위에 있는 모든 정점 $k$의 $a_k$ 중 최댓값이다. $\min(i \ldots j)$는 같은 값들 중 최솟값이다. $len(i \ldots j)$는 $i$에서 $j$까지 가는 경로에 있는 정점의 개수이다.

린은 몇 시간째 이 문제를 풀고 있지만 아직 해결하지 못했다. 린을 도와주자.

첫째 줄에 트리의 정점 개수 $n$ ($1 \le n \le 5 \cdot 10^4$)이 주어진다. 둘째 줄에는 각 정점에 적힌 $n$개의 정수 $a_i$ ($0 \le a_i \le 10^5$)가 주어진다. 다음 $n-1$개 줄에는 트리의 간선을 나타내는 정수 쌍 $u, v$ ($1 \le u, v \le n$)가 한 줄에 하나씩 주어진다.

구한 합의 값을 한 줄에 출력한다.