P9307 "DTOI-5" Do a Row Reordering (Maximum Version)

**The difference between this problem and the Minimum Version is the required optimum (max/min) and the Constraints.** Xiao L is keen on reordering sequences to make them look neat.

Xiao L has a sequence $a$ of length $n$, where each term $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 define $\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'$, so that $f(a')$ is maximized. **Note that during reordering, each $a'_i = (p'_i, q'_i)$ must be treated as a whole.** You need to compute the value of $f(a')_{\max}$, and also how many different $a'$ can achieve $f(a')_{\max}$. 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&50&20 \operatorname{pts}\cr\hline \sf3&500&20 \operatorname{pts}\cr\hline \sf4&2\times 10^3&20 \operatorname{pts}\cr\hline \sf5&/&30 \operatorname{pts}\cr\hline \end{array} $$ For $100\%$ of the testdata, $1 \leq n \leq 10^4$, $1 \leq p_i, q_i \leq n$, and it is guaranteed that $p$ and $q$ are both **permutations**. Translated by ChatGPT 5