在一个雨夜，一只戴着兜帽的母马疾驰进一个空荡荡的集市，走进了一家昏暗的古玩店。她开始在店里翻找，直到点亮了一支小蜡烛。

“有什么能帮您的吗，旅行者？”店主，一匹种马，走出来问道。他走到柜台后，推测出某种强大的力量将这位顾客吸引到了他的店里；她指向货架上玻璃罩内的一枚镶嵌着深红色宝石的护身符。

“啊，您的眼光真好。这枚‘空角兽护身符’（Alicorn Amulet）是所有已知魔法护身符中最神秘、最强大的之一。呃，啊——恐怕这……太危险了。”

（母马将一大袋金币扔在柜台上。）

“您需要礼品包装吗？”

……

第二天早上，所有小马醒来时发现自己变成了排列！

小马国里有 $n!$ 只小马。邪恶的魔法将所有小马变成了长度为 $n$ 的 $n!$ 种不同的排列。

为了减少恐慌，变成了排列 $A$ 的苹果杰克（Applejack）决定尽快召集她的家人。她注意到，对于另一个排列 $P$，如果她可以通过若干次“一二三变换”（One-Two-Three-transformation）将自己变成 $P$，那么 $P$ 就是苹果家族的一员。

“一二三变换”如下：选择 3 个相邻元素 $A_i, A_{i+1}, A_{i+2}$。如果 $A_i$ 是它们的中位数，你可以将其放到 $A_{i+2}$ 之后，换句话说，将这三个元素变换为 $A_{i+1}, A_{i+2}, A_i$。如果 $A_{i+2}$ 是它们的中位数，你可以将其放到 $A_i$ 之前，换句话说，将这三个元素变换为 $A_{i+2}, A_i, A_{i+1}$。

事实上，如果一个排列可以通过“一二三变换”变成另一个排列，那么它们属于同一个家族。让我们选择每个家族中字典序最小的排列作为该家族的代表。然后，我们可以按代表的字典序对所有家族进行排序，得到家族列表 $F_1, F_2, \dots$。例如，排列 $(1, 2, \dots, n)$ 总是属于家族 $F_1$。

每只小马都应该去其家族的临时避难所。排列 $P \in F_i$ 意味着小马 $P$ 应该去避难所 $i$ 与其家人会合。

请帮助苹果杰克找到苹果家族应该去的避难所，以及苹果家族中有多少只小马。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示苹果杰克变成的排列 $A$。

输出格式

输出一行，包含一个整数。

我们已知存在唯一的 $i$ 使得 $A \in F_i$。如果 $i \le 65\,472$，输出苹果家族中小马的数量对 $998\,244\,353$ 取模的结果。否则，直接输出 $i$ 对 $998\,244\,353$ 取模的结果作为答案。

样例

输入 1

3
2 1 3

输出 1

2

说明

总共有 4 个家族：

• $F_1 = \{(1, 2, 3)\}$
• $F_2 = \{(1, 3, 2), (2, 1, 3)\}$
• $F_3 = \{(2, 3, 1), (3, 1, 2)\}$
• $F_4 = \{(3, 2, 1)\}$

因此苹果家族是 $F_2 = \{(1, 3, 2), (2, 1, 3)\}$，其代表是 $(1, 3, 2)$。所以，输出苹果家族中小马的数量，即 2。