该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目背景】

小 Z 最近开始学琴，每天结束机房的训练后，都会练上一会儿．

几天下来，整首曲子还没学会，开头倒是已经不用看谱了．毕竟，每次练到不熟悉的地方，他总想退回去，再从头来一遍．

【题目描述】

曲谱上依次有 $n$ 个音符，第 $i$ 个音符的音高用整数 $a_i$ 表示．数值越大，音越高．

小 Z 安排了 $n$ 轮练习．第 $i$ 轮，他会把曲谱开头的 $x_i$ 个音符按原顺序弹奏 $c_i$ 遍，每一遍都从曲谱的第一个音符开始．例如，将开头的两个音符 $(2,1)$ 弹奏两遍，得到的是 $(2,1,2,1)$．

第一轮只练习第一个音符，即 $x_1=1$．之后每一轮，可以练习与上一轮相同或更短的一段，也可以比上一轮多练一个音符，即 $x_i\le x_{i-1}+1$．每轮至少练习一个音符，且不超过曲谱长度．各轮的 $x_i,c_i$ 均已给定，练习顺序不能改变．

记录仪从练习开始就一直开着，按弹奏顺序记下了所有音符，得到序列 $s$．即使某一轮练习的片段变短，之前的记录也不会被删除．曲谱本身始终不变．

请你统计，整份记录中有多少对音符，满足前面弹出的音比后面弹出的音高．这两个音符不必相邻，也可以来自不同轮练习．

也就是说，求满足 $1\le u<v\le |s|$ 且 $s_u>s_v$ 的下标对 $(u,v)$ 的数量，对 $998244353$ 取模．音高相同的两个音符不计入答案．

【输入描述】

第一行输入一个正整数 $n$，表示曲谱上的音符数量和练习轮数．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示曲谱上各音符的音高．

接下来 $n$ 行，第 $i$ 行输入两个正整数 $x_i,c_i$，表示第 $i$ 轮练习曲谱开头的 $x_i$ 个音符，并将这一段弹奏 $c_i$ 遍．

【输出描述】

输出一个整数，表示整份记录中符合要求的音符对数量对 $998244353$ 取模后的结果．

【样例 1】

【样例 1 输入】

4
2 1 3 2
1 1
2 1
1 1
2 2

【样例 1 输出】

11

【样例 1 解释】

四轮练习分别弹奏了：

• 第一轮：$(2)$．
• 第二轮：$(2,1)$．
• 第三轮：$(2)$．
• 第四轮：$(2,1,2,1)$．

将它们依次记录下来，得到

第 $3$、$6$、$8$ 个元素均为 $1$，它们前面分别有 $2$、$4$、$5$ 个 $2$，因此答案为 $2+4+5=11$．

第三轮只练习第一个音符，但前两轮的记录仍然保留．本次练习没有弹到曲谱的第 $3$、$4$ 个音符，这是允许的．

【样例 2】

【样例 2 输入】

3
1 2 1
1 1
2 2
3 1

【样例 2 输出】

6

【样例 2 解释】

最终得到 $s=(1,1,2,1,2,1,2,1)$．三个 $2$ 的右侧分别有 $3$、$2$、$1$ 个 $1$，共构成 $6$ 个逆序对．值相等的元素之间不计贡献．

【数据规模与约定】

对于所有数据，保证：

• $1\le n\le 2\times10^5$．
• $-10^9\le a_i\le 10^9$．
• $1\le c_i\le 10^9$．
• 令 $x_0=0$，有 $1\le x_i\le \min(n,x_{i-1}+1)$．
• 所有输入均为整数．

记 $L=\sum_{i=1}^{n}c_ix_i$，即最终记录序列的长度．各子任务独立计分；通过一个子任务的全部测试点，才能获得该子任务的分数．

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 3 的附加限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 4 的附加限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 5 的附加限制．
• Data/sample6.in 与 Data/sample6.ans：该样例无特殊限制．
• Data/sample7.in 与 Data/sample7.ans：该样例无特殊限制．
• Data/sample8.in 与 Data/sample8.ans：满足子任务 1 的附加限制．
• Data/sample9.in 与 Data/sample9.ans：满足子任务 2 的附加限制．

大样例下载

点击下载本题选手目录