Background

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.

Problem Description

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$.

Input Format

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 Format

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

5
1 5 2 4 3
1 4 2 5 3

9 2

Hint

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