Hints: Non-Descending Arrays

At each position $i$, you only have two choices: keep $(a_i,b_i)$ as is, or swap them.

Try to think of each index as choosing one of two “orientations”. What condition must hold between index $i-1$ and $i$ so that both final arrays stay non-decreasing?

Answer to Hint 1:
If the chosen values at index $i-1$ are $(x_{i-1}, y_{i-1})$ and at index $i$ are $(x_i, y_i)$, we need:

• $x_{i-1} \le x_i$ (for array $a$ after choices),
• $y_{i-1} \le y_i$ (for array $b$ after choices).

So compatibility is purely local between neighboring positions. This is a strong sign that a left-to-right DP can work.

Answer to Hint 2:
Use a DP with only 2 states per index:

• state 0: index $i$ is not swapped,
• state 1: index $i$ is swapped.

Let dp0 / dp1 be the number of valid ways up to current index ending in those states.

Can you write transitions from states at $i-1$ to states at $i$ by checking compatibility?

Answer to Hint 3:
Suppose at index $i$:

• state 0 means pair is $(a_i,b_i)$,
• state 1 means pair is $(b_i,a_i)$.

From previous state 0 (pair $(a_{i-1},b_{i-1})$):

• to current 0 if $a_{i-1}\le a_i$ and $b_{i-1}\le b_i$,
• to current 1 if $a_{i-1}\le b_i$ and $b_{i-1}\le a_i$.

From previous state 1 (pair $(b_{i-1},a_{i-1})$):

• to current 0 if $b_{i-1}\le a_i$ and $a_{i-1}\le b_i$,
• to current 1 if $b_{i-1}\le b_i$ and $a_{i-1}\le a_i$.

Answer to Hint 4:
Notice a simplification: the two condition sets collapse into just two checks used in the model solution:

1. “same orientation with previous” check:
   $a_{i-1}\le a_i$ and $b_{i-1}\le b_i$
2. “cross orientation with previous” check:
   $a_{i-1}\le b_i$ and $b_{i-1}\le a_i$

If check (1) holds, previous 0 -> 0 and previous 1 -> 1 are both allowed.
If check (2) holds, previous 0 -> 1 and previous 1 -> 0 are both allowed.

Answer to Hint 5:
So each step can be updated as:

• nxt0 += dp0 and nxt1 += dp1 if check (1) holds,
• nxt0 += dp1 and nxt1 += dp0 if check (2) holds.

All additions are modulo $998244353$.

What should be the base case at index $0$?

Answer to Hint 6:
At $i=0$, both choices are valid independently (swap or not), so:

• dp0 = 1,
• dp1 = 1.

Then iterate $i=1$ to $n-1$, compute nxt0, nxt1, and assign back.

Answer to Hint 7:
After processing all indices, both ending states are acceptable, so answer is:

Complexity is $O(n)$ per test case and $O(1)$ extra memory.

Quick sanity checks:

• If both arrays are already non-decreasing and every cross-check also holds, many subsets are valid.
• If at some position neither check (1) nor check (2) holds for all incoming states, that branch dies out.
• The statement guarantees at least one good subset, so final answer is never zero for valid input.

This matches the two-state DP implementation in model_sol.cpp.