Problem Background

Ysuperman is particularly fond of strategic games.

Problem Description

The game map is a rooted tree with $n$ nodes, where node $1$ is the root. Each node, except for node $1$, has a unique parent node.

Each node has a height, with the height of the $i$-th node being $h_i$. We consider a node $v$ to be a "strategic high ground" if and only if $v$ is the root node or its parent node $u$ is a "strategic high ground" and $h_v \ge h_u$.

However, Ysuperman does not know the specific parent node for each node but only knows the possible range of the parent node's index. For node $i$, the parent node's index range is $[l_i, r_i]$, ensuring $1 \le l_i \le r_i < i$.

Now, Ysuperman wants to know the sum of the number of "strategic high grounds" for all possible scenarios.

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

Input Format

The input consists of $n+1$ lines.

The first line contains a positive integer $n$.

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

The following $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

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

3
1 3 2
1 1
1 2

Sample Output #1

5

Sample Input #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

Sample Output #2

4044

Sample Input #3

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

Sample Output #3

904672069

Notes

Explanation of Sample #1:

There are two scenarios:
- Scenario 1: Node $2$'s parent is node $1$, and node $3$'s parent is node $1$. In this case, nodes $1, 2, 3$ are all "strategic high grounds."
- Scenario 2: Node $2$'s parent is node $1$, and node $3$'s parent is node $2$. Since $h_2 > h_3$, node $3$ is not a "strategic high ground," but nodes $1, 2$ are.

Thus, the sum of the number of "strategic high grounds" across all scenarios is $5$.

The data 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 difficult.

见题面 Input 部分

见题面 Output 部分