P6655 [YsOI2020] High Ground.

Ysuperman especially likes playing strategy games.

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$.

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$.

One line containing one integer, which is the answer.

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$. | $\text{Test Point ID}$ | $n$ | $\prod_{i=2}^n(r_i-l_i+1)$ | $\text{Special Property}$ | | :--------------------: | :------: | :------------------------: | :-----------------------: | | $1 \sim 2$ | $=10$ | $\le 10^6$ | $\text{None}$ | | $3$ | $=10^5$ | $\le 10^6$ | $\text{None}$ | | $4$ | $=10^5$ | \\ | $h_i \le h_{i+1}$ | | $5$ | $=10^5$ | \\ | $h_i > h_{i+1}$ | | $6 \sim 12$ | $=10^3$ | \\ | $\text{None}$ | | $13 \sim 20$ | $=10^5$ | \\ | $\text{None}$ | 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