【题目描述】

给一棵 $n$ 个点的无根树，每个点有一个点权，一条路径的权值定义为路径上点权的最大值乘上最小值。求所有路径的权值之和。两条路径不同当且仅当这两条路径所包含的点集不同。

【输入格式】

第一行一个整数 $n$，第二行有 $n$ 个正整数，$a_1,a_2,...,a_n$，表示每个点的点权。接下来 $n − 1$ 行，每行两个整数 $u$,$v$ 表示树上的一条边。

【输出格式】

共一行，为所有路径的权值之和，答案对 $998244353$ 取模。

【样例 1 输入】

3
1 2 3
1 2
1 3

【样例 1 输出】

22

【数据范围】

对于 $30%$ 的数据，$n \leq 100$

对于 $100%$ 的数据，$n \leq 1000,a_i \leq 5000$