Minimizing Record Events in Paired Permutations

We are given an integer \(n\) and two permutations \(p\) and \(q\) of \(\{1,2,\dots,n\}\). For each index \(i\) (\(1\le i\le n\)) we define a pair \((p_i,q_i)\). Consider any reordering \(a'\) of the \(n\) pairs (an element must always be taken as a whole, i.e. the two coordinates cannot be separated).

For a sequence (after reordering) \(a'\) the weight function is defined as follows:

[ f(a')=\sum_{i=1}^n \Big( [p'i>\max{1\le j<i}p'_j] + [q'i>\max{1\le j<i}q'_j] \Big), ]

where the bracket \([\cdot]\) equals \(1\) if the condition is true and \(0\) otherwise, and by convention \[ \max_{1\le j<1} p'_j=\max_{1\le j<1} q'_j=-\infty. \]

Your task is to reorder the pairs so that \(f(a')\) is minimized. Output the minimum possible value \(f(a')_{\min}\) and the number of reorderings achieving that minimum, modulo \(998244353\).

Explanation

Note that in any reordering the first element always contributes two (one for each coordinate) since there is no previous element. For any permutation of distinct numbers, if the sequence is in strictly decreasing order then only the first element is a record. Therefore, if it is possible to order the pairs so that both \(p\) and \(q\) are in strictly decreasing order then \(f(a')=2\). In our setting the individual sequences \(p\) and \(q\) (when considered independently) can be made strictly decreasing if and only if the pair \((n,n)\) occurs among the \(n\) pairs. Thus:

• If there exists an index \(i\) with \(p_i=n\) and \(q_i=n\), then the optimum is \(f(a')_{\min}=2\). In this case the only way to achieve the optimum is to put \((n,n)\) at the first position; the remaining \(n-1\) pairs can be in any order, so the number of ways is \((n-1)!\) modulo \(998244353\).
• If no pair \((n,n)\) exists then let \(A\) be the unique pair with \(p_A=n\) and \(B\) be the unique pair with \(q_B=n\) (with \(A\neq B\)). In any reordering the first element contributes 2. To avoid extra records, the optimal strategy is to choose either \(A\) or \(B\) as the first element. Without loss of generality, suppose we choose \(A\) first (with \(q_A\lt n\)). Then the first element gives records in both coordinates and when \(B\) appears later it will yield a record in its second coordinate. Moreover, to avoid any additional record in \(q\), every element appearing between \(A\) and \(B\) must have its \(q\) value at most \(q_A\). A symmetric condition holds if we choose \(B\) first. In this case one may show that the optimum is \(f(a')_{\min}=3\) and the number of optimal reorderings is given by

[ \text{Ways} = \sum_{j=2}^{\min(n, x+1)} \Bigl(P(x-1, j-2)\cdot (n-j)!\Bigr)\quad \text{for } x=q_A \text{ (if first is } A\text{)} ]

and similarly for the case when first element is (B) (with (x=p_B)). Here, (P(n,k)=\frac{n!}{(n-k)!}) denotes the permutation function. The final answer is the sum of the counts for the two cases, modulo (998244353).

Input Format:

n
p1 p2 ... pn
q1 q2 ... qn

Output Format:

{f_min} {count}

It is guaranteed that \(p\) and \(q\) are each a permutation of \(\{1,2,\dots,n\}\).

inputFormat

The first line contains an integer \(n\) (\(1\le n\le 10^5\)).

The second line contains \(n\) integers \(p_1,p_2,\dots,p_n\), a permutation of \(\{1,2,\dots,n\}\).

The third line contains \(n\) integers \(q_1,q_2,\dots,q_n\), a permutation of \(\{1,2,\dots,n\}\).

outputFormat

Output two space‐separated integers: the minimum possible value \(f(a')_{\min}\) and the number of reorderings achieving that minimum, taken modulo \(998244353\).

sample

2
2 1
2 1

2 1

</p>