Summing High Ground Counts in Uncertain Tree Structures

You are given a rooted tree with n nodes, numbered from 1 to n, where node 1 is the root. Every node except the root has exactly one parent. Each node i has an integer height h_i.

A node v is called a high ground if and only if either v is the root or its parent u is a high ground and the height condition
$$h_v \ge h_u$$
holds.

However, the parent of each node is not known exactly. For every node i (with i \ge 2), you are given a range \([l_i, r_i]\) (with \(1 \le l_i \le r_i < i\)) which indicates that the parent of node i can be any node with an index in that interval.

For all possible trees constructed by choosing a valid parent for each node (node 1 has no parent), compute the sum of the number of high ground nodes over all these trees. Since the answer can be large, output it modulo $$998244353$$.

Note: The total number of possible trees is \(\prod_{i=2}^{n}(r_i-l_i+1)\).

inputFormat

The first line contains a single integer n (the number of nodes).
The second line contains n integers, where the i-th integer is h_i (the height of node i).
Then for each i from 2 to n, there is a line containing two integers l_i and r_i (the possible range for the parent of node i).

outputFormat

Output one integer: the sum of the number of high ground nodes over all possible trees, modulo $$998244353$$.

sample

3
1 2 1
1 1
1 2

5