Background

Ysuperman especially likes playing strategy games.

Problem Description

The game map is a rooted tree with $n$ nodes. The root node is $1$. Except for node $1$, every other node has a unique parent.

Each node has a height. The height of node $i$ is $h_i$. We say that a node $v$ is a "high ground" if and only if $v$ is the root, or its parent node $u$ is a "high ground" and $h_v \ge h_u$.

However, Ysuperman does not know the exact parent of each node. He only knows the possible interval of its parent index. For node $i$, the possible parent index range is $[l_i, r_i]$, and it is guaranteed that $1 \le l_i \le r_i < i$.

Now, Ysuperman wants to know, for all possible cases, what the total sum of the number of "high ground" nodes is.

Since the result can be very large, you only need to output the value modulo $998244353$.

Input Format

The input has $n + 1$ lines.

The first line contains a positive integer $n$.

The next line contains $n$ non-negative integers. The $i$-th integer describes $h_i$.

The next $n - 1$ lines each contain two positive integers, describing $l_2, r_2, \cdots, l_n, r_n$.

It is guaranteed that $1 \le l_i \le r_i < i$.

Output Format

One line containing one integer, which is the answer.

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

Hint

Explanation for Sample 1:

There are two cases. Case 1: the parent of $2$ is $1$, and the parent of $3$ is $1$. Then $1, 2, 3$ are all "high ground". Case 2: the parent of $2$ is $1$, and the parent of $3$ is $2$. Since $h_2 > h_3$, $3$ is not "high ground". Then $1, 2$ are "high ground".

So the sum of the numbers of "high ground" nodes over all cases is $5$.

The testdata guarantees that $h_i$ is within the maximum range representable by int, and $1 \le l_i \le r_i < i$.

The problem is not hard.

Translated by ChatGPT 5