题目描述

给定一棵由 $n$ 个节点构成的以 1 为根节点的有根二叉树，每个节点都有一个权值 $val_i$。你需要计算满足以下条件的联通块的数量：

• 由联通块内每个节点的权值按照后序遍历编号的顺序组成的序列是非严格递增的。更具体地，记后序遍历中节点的编号为 $b_1, b_2, \ldots, b_k$，则有 $val_{b_1} \leq val_{b_2} \leq \cdots \leq val_{b_k}$。

由于答案可能很大，请将答案对 $998244353$ 取模后输出。

【名词解释】

对于树上的任意一点集 $S$，如果点集中的任意两点 $u, v$ 满足“$u$ 到 $v$ 的简单路径上的所有点都在点集中”，则称 $S$ 是一个连通块。特别地，单独的点也构成一个连通块。

输入

第一行输入一个整数 $n$ ($1 \leq n \leq 5 \times 10^5$)，表示二叉树的节点数量。

第二行输入 $n$ 个整数 $val_1, val_2, \ldots, val_n$ ($1 \leq val_i \leq 10^9$)，表示每个节点的权值。

此后 $n$ 行，第 $i$ 行输入两个整数 $l_i$ 和 $r_i$ ($0 \leq l_i, r_i \leq n$)，表示节点 $i$ 的左儿子和右儿子。若左/右儿子不存在，则对应值为 0。

输出

输出一个整数，表示满足条件的联通块的数量，对 $998244353$ 取模后输出。

样例

5
3 1 2 1 2
2 3
0 4
0 5
0 0
0 0

15

样例解释

这个样例的树结构如下图所示：