制高

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有一棵以结点 $1$ 为根、包含 $n$ 个结点的有根树。第 $i$ 个结点的高度为 $h_i$。

结点 $v$ 是“制高点”，当且仅当 $v=1$，或者它的父亲 $u$ 是制高点且 $h_v\ge h_u$。

对于每个 $i\ge2$，结点 $i$ 的父亲可以独立地选择为编号区间 $[l_i,r_i]$ 中的任意结点。保证 $1\le l_i\le r_i<i$，因此每种选择都会形成一棵合法有根树。

求所有可能的父亲选择方案中，制高点数量的总和。答案对 $998244353$ 取模。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个非负整数 $h_1,h_2,\ldots,h_n$。

接下来 $n-1$ 行，第 $i-1$ 行包含两个整数 $l_i,r_i$，描述结点 $i$ 的父亲编号范围。

输出格式

输出一行一个整数，表示所有方案的制高点数量之和模 $998244353$ 的结果。

样例输入 1

3
1 3 2
1 1
1 2

样例输出 1

5

样例输入 2

10
1 1 1 0 5 2 11 12 17 7
1 1
1 2
2 2
1 3
1 1
1 4
1 2
6 7
1 5

样例输出 2

4044

数据范围

对于所有数据：

• $1\le n\le10^5$；
• $0\le h_i\le 2^{31}-1$；
• $1\le l_i\le r_i<i$。

子任务

样例说明

样例一共有两种父亲选择方案。两种方案分别有三个和两个制高点，因此答案为 $5$。