P9306 "DTOI-5" Reordering a Permutation (Minimum Version).

**The difference between this problem and the Maximum Version is the extremum being asked for and the constraints.** Little L is keen on reordering sequences to make them look neat.

Little L has a sequence $a$ of length $n$, where each item $a_i$ is a pair $(p_i, q_i)$. To make $a$ look neater, he specifies that $p$ and $q$ are both permutations of length $n$. To measure how neat $a$ is, he defines a weight function $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])$. **Note that when $i = 1$, both bracketed terms can take a value, because we consider $\displaystyle\max_{j = 1}^0 p_j = \displaystyle\max_{j = 1}^0 q_j = -\infty$.** To make $a$ look even neater, he decides to reorder $a$ in some way to obtain $a'$ such that $f(a')$ is minimized. **Note that during reordering, you must treat $a'_i = (p'_i, q'_i)$ as an indivisible whole.** He wants you to find the value of $f(a')_{\min}$, and how many different $a'$ can achieve $f(a')_{\min}$. Since the number of ways may be very large, you only need to output the result modulo $998244353$.

The first line contains an integer $n$. The second line contains $n$ integers $p_1, p_2, \cdots, p_n$. The third line contains $n$ integers $q_1, q_2, \cdots, q_n$.

Output one line with two integers, representing the required values.

**Constraints** $$ \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} $$ For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq p_i, q_i \leq n$, and it is guaranteed that $p$ and $q$ are both **permutations**. Translated by ChatGPT 5