#P18554. Guess The Sequence 2

Guess The Sequence 2

Guess The Sequence 2

Little K 有一个 1∼n1\sim n 的随机排列 p1,p2,…,pnp_1,p_2,\ldots,p_n。他准备给朋友 Little Cyan Fish 出一道猜排列的题。

Little K 可以选择排列的一个子段集合,并告诉 Little Cyan Fish 每个所选子段的最大值。

形式化地,他可以选择集合 {(l1,r1),(l2,r2),…,(lk,rk)}\{(l_1,r_1),(l_2,r_2),\ldots,(l_k,r_k)\},其中对所有 1≤i≤k1\le i\le k 都有 1≤li≤ri≤n1\le l_i\le r_i\le n。随后,Little Cyan Fish 会得到 kk 个三元组

(l1,r1,m1),(l2,r2,m2),…,(lk,rk,mk),(l_1,r_1,m_1),(l_2,r_2,m_2),\ldots,(l_k,r_k,m_k),

其中 mi=max⁡li≤j≤ripjm_i=\max_{l_i\le j\le r_i}p_j,表示第 ii 个所选子段的最大值。

Little Cyan Fish 需要猜出 Little K 的排列。作为最好的朋友,Little K 希望自己给出的信息足以使对方正确猜出排列。因此,必须恰好只有一个 1∼n1\sim n 的排列满足所提供的全部信息。

Little K 想知道,有多少个不同的子段集合能够使 Little Cyan Fish 唯一确定这个排列。请帮助他计算答案。答案可能很大,请输出它对 998244353998244353 取模后的值。

这里选择的是集合,相同子段不会重复出现,提供信息的顺序不产生新方案。

输入格式

第一行包含一个整数 nn(1≤n≤5×1051\le n\le5\times10^5)。

第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n(1≤pi≤n1\le p_i\le n),它们构成 1∼n1\sim n 的一个排列。

保证给定排列是从长度为 nn 的全部排列中等概率随机选出的。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模后的值。

原样例 1

2
1 2
6

原样例 2

4
1 4 2 3
532