Editorial : Non-Descending Arrays

First, observe we can normalize every index independently: if $a_i > b_i$, swap this pair so that always $a_i \le b_i$.

Why is this safe? Because for each index, “swap” / “do not swap” is just relabeled after normalization. So the number of good subsets does not change.

Now study each adjacent pair $(i, i+1)$:

• Type 1: $b_i \le a_{i+1}$.
  Then every value from index $i$ is $\le$ every value from index $i+1$, so choices at $i$ and $i+1$ are independent.

• Type 2: $b_i > a_{i+1}$.
  Then choices are forced to be equal: we must either swap both indices or swap neither. Otherwise one of the two final arrays decreases.

So type-2 edges connect indices whose swap decisions must match. If we build components of indices connected by type-2 adjacency, each component contributes exactly 2 valid choices (all swapped or all not swapped), and components are independent.

Let:

• $n$ = number of indices,
• $k$ = number of type-2 adjacent pairs, i.e. count of $i \in [1, n-1]$ such that $b_i > a_{i+1}$ (after normalization).

Initially there are $n$ singleton components; every type-2 edge merges two neighboring components, so total components are $n-k$.

Therefore the number of good subsets is: