题目背景

本题与 Maximum Version 的区别是所求最值和数据范围不同。

小 L 热衷于重排数列使之规整。

题目描述

小 L 有一个长为 $n$ 的序列 $a$，其中每一项 $a_i$ 都是一个 pair $(p_i, q_i)$。

为了让 $a$ 看起来规整一些，他钦定 $p, q$ 分别均为长为 $n$ 的排列。

为了对 $a$ 的规整程度进行量化计算，他给出了一个权值函数 $f(a) = \displaystyle\sum_{i = 1}^n ([p_i > \max_{j = 1}^{i - 1} p_j] + [q_i > \max_{j = 1}^{i - 1} q_j])$。注意 $i = 1$ 时两个方括号都能取到值，因为我们认为 $\displaystyle\max_{j = 1}^0 p_j = \displaystyle\max_{j = 1}^0 q_j = -\infty$。

为了让 $a$ 看起来更加规整，他决定分别以某种方式重排 $a$ 得到 $a'$ 使得 $f(a')$ 最小。注意重排时必须将 $a'_i = (p'_i, q'_i)$ 视为整体。

他希望你求出 $f(a')_{\min}$ 的值，以及分别有多少个 $a'$ 可以取到 $f(a')_{\min}$。

由于方案数可能很大，你只需要求出结果对 $998244353$ 取模的值。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个整数 $p_1, p_2, \cdots, p_n$；

第三行，$n$ 个整数 $q_1, q_2, \cdots, q_n$。

输出格式

一行，两个整数，表示所求的值。

5
1 5 2 4 3
1 4 2 5 3

3 48

提示

【数据范围】

$$\def\or{\operatorname{or}} %\def\arrayscretch{1.5} \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Subtask}&n\le &\textbf{Points}\cr\hline \sf1&10&10 \operatorname{pts}\cr\hline \sf2&500&20 \operatorname{pts}\cr\hline \sf3&5\times10^3&20 \operatorname{pts}\cr\hline \sf4&10^5&20 \operatorname{pts}\cr\hline \sf5&5\times10^5&30 \operatorname{pts}\cr\hline \end{array} $$

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$1 \leq p_i, q_i \leq n$，保证 $p, q$ 均为排列。