Background

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.

Problem Description

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

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

3 48

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&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