题目描述

小 S 的女神 Yuzuha 的朋友 Alice 最近不会写她的作业，于是小 S 决定帮助他的女神解决一些友情（？）问题。

给定一个长度为 $n$ 的序列，要求你回答 $m$ 组询问。每组询问会临时地将一个元素 $A_x$ 替换成 $y$，你需要回答替换后，这个序列的上升子序列数量。

---

输入格式

第一行两个自然数 $n,m$，含义如题面所述。

接下来一行 $n$ 个自然数，表示初始序列。

接下来 $m$ 行，每行两个自然数 $x,y$，表示一次临时的修改。

---

输出格式

共 $m$ 行，每行一个自然数，表示答案。由于这个数可能很大，你只需要输出它对 $998244353$ 取模的结果。

---

样例

样例 1 输入

3 3
1 3 6
1 4
2 5
3 2

样例 1 输出

5
7
5

样例 1 解释

• 对于第一组询问，将序列变为 $[4,3,6]$，有这些上升子序列：

  • $[4]$
  • $[3]$
  • $[6]$
  • $[4,6]$
  • $[3,6]$

  共 $5$ 个。

• 对于第二组询问，将序列变为 $[1,5,6]$。此时所有非空子序列都是上升子序列。

• 对于第三组询问，将序列变为 $[1,3,2]$，有这些上升子序列：

  • $[1]$
  • $[3]$
  • $[2]$
  • $[1,3]$
  • $[1,2]$

---

样例 2 输入

见下发文件中的 pre_dognus2.in。

样例 2 输出

见下发文件中的 pre_dognus2.out。

样例 2 满足测试点 $3\sim 5$ 的限制。

---

样例 3 输入

见下发文件中的 pre_dognus3.in。

样例 3 输出

见下发文件中的 pre_dognus3.out。

样例 3 满足测试点 $6\sim 8$ 的限制。

---

样例 4 输入

见下发文件中的 pre_dognus4.in。

样例 4 输出

见下发文件中的 pre_dognus4.out。

样例 4 满足测试点 $13\sim 17$ 的限制。

---

样例 5 输入

见下发文件中的 pre_dognus5.in。

样例 5 输出

见下发文件中的 pre_dognus5.out。

样例 5 满足测试点 $18\sim 20$ 的限制。

---

数据范围与提示

本题共 $20$ 个测试点。

测试点编号	$n,m$	特殊性质
$1\sim 2$	$\leq 10$	无
$3\sim 5$	$\leq 500$
$6\sim 8$	$\leq 2000$
$9\sim 12$	$\leq 2\times 10^5$	A
$13\sim 17$		B
$18\sim 20$		无

性质 A： 保证初始序列是一个 $1\sim n$ 的排列。

性质 B： 保证不同的 $x$ 不超过 $10$ 个。
（这里的“不同的 $x$”指询问中出现的下标 $x$ 的种类数不超过 $10$。）

---

对于所有测试点，保证：

• $1 \leq n,m \leq 2\times 10^5$
• $1 \leq y, A_i \leq n+m$

记每次询问的 $y$ 为 $B_i$。并且保证

$$A_1, A_2, \dots, A_n, B_1, B_2, \dots, B_m$$

是一个 $1 \sim (n+m)$ 的排列。