Given a weighted tree of $n$ vertices. Each vertex has weight $A_i$.
Let's denote $max(u, v)$ is the maximum weight on the simple path from $u$ to $v$. Similarly, $min(u, v)$ is the minimum weight on the simple path from $u$ to $v$.
Calculate the sum of $max(i, j) - min(i, j)$ with $1 \le i < j \le n$. In other words, calculate:
$$\sum_{i = 1}^n \sum_{j = i + 1}^n max(i, j) - min(i, j)$$
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
- The next $n - 1$ lines, each line contains 2 integer $u, v$, there is an edge between $u, v$.
### Output
- Print the result of $\sum_{i = 1}^n \sum_{j = i + 1}^n max(i, j) - min(i, j)$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le u, v \le n$.
- $1 \le A_i \le 10^5$.
### Example
Input:
```
3
6 10 10
1 2
2 3
```
Output:
```
8
```
