题目背景

Ysuperman 特别喜欢玩战略游戏。

题目描述

游戏地图是一棵 $n$ 个点的有根树，根节点是 $1$ ，除节点 $1$ 外其他节点都有唯一的父亲节点。

每个节点有一个高度，第 $i$ 个节点的高度为 $h_i$ ，我们认为一个节点 $v$ 是“制高点”，当且仅当 $v$ 是根节点或者其父亲节点 $u$ 是“制高点”并且 $h_v\ge h_u$ 。

但是， Ysuperman 并不知道每个节点的父亲具体是哪个，只知道它的父亲编号可能在的区间，其中，节点 $i$ 的父亲可能在的编号范围为 $[l_i,r_i]$ ，保证 $1\le l_i\le r_i<i$ 。

现在， Ysuperman 想知道对于所有可能的情况，“制高点”的数量之和是多少。

因为这个结果可能会很大，所以你只需要输出结果 $\bmod \ {998244353}$ 的值即可。

输入格式

输入共 $n+1$ 行。

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

接下来一行 $n$ 个非负整数，第 $i$ 个整数描述 $h_i$ 。

接下来 $n-1$ 行，每行两个正整数，分别描述 $l_2,r_2,\cdots,l_n,r_n$ 。

保证 $1\le l_i\le r_i<i$ 。

输出格式

一行一个整数，即答案。

3
1 3 2
1 1
1 2

5

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

4044

50
1 0 0 6 2 5 0 2 16 15 14 8 20 22 23 21 7 24 27 17 1 13 39 40 31 38 40 16 25 48 2 0 15 7 0 47 58 11 22 54 11 78 30 32 31 35 44 56 59 85
1 1
2 2
1 2
2 3
3 3
1 6
2 6
3 5
5 9
3 4
1 4
3 12
1 12
5 7
5 13
1 10
7 9
4 11
12 12
16 17
3 9
8 15
15 16
1 19
9 10
10 12
8 10
4 10
6 13
10 13
11 30
11 21
2 30
13 23
4 24
32 34
8 29
4 22
2 26
29 33
28 38
18 31
19 36
15 32
8 14
15 32
4 33
30 45
8 25

904672069

提示

样例一解释：

共有两种情况，情况一： $2$ 的父亲节点是 $1$ ， $3$ 的父亲节点是 $1$ ，此时 $1,2,3$ 均是“制高点”；情况二： $2$ 的父亲节点是 $1$ ， $3$ 的父亲节点是 $2$ ，由于 $h_2>h_3$ ，所以 $3$ 不是“制高点”，此时 $1,2$ 均是“制高点”。

所以所有情况“制高点”数量的和为 $5$ 。

题目数据保证 $h_i$ 在 int 能表示的最大范围内， $1\le l_i\le r_i<i$ 。

题目并不难。