Editorial for Tweak the Peak

Approach

Let the rearranged sequence be $b_1, b_2, \ldots, b_n$.

Because all values are distinct, each adjacent pair is either increasing or decreasing.

If a rearrangement has exactly one peak and zero valleys, then the sequence of comparison signs can change direction at most once:

• a change from increasing to decreasing creates a peak,
• a change from decreasing to increasing creates a valley.

So every valid rearrangement must increase for a while, then decrease forever after that single turn. The maximum value is therefore the unique peak.

Now look at the $n - 1$ values smaller than the maximum. Choose which of them go to the left of the maximum:

• the left side is then forced to be in increasing order,
• the right side is forced to be in decreasing order.

Every subset gives one candidate arrangement. Two subsets are invalid:

• the empty subset puts the maximum first, so it is not a peak,
• the full subset puts the maximum last, so it is not a peak.

Therefore, for $n \ge 3$, the answer is:

$2^{n-1} - 2$

modulo $998244353$.

This can be computed in $O(\log n)$ with fast modular exponentiation.

Solution (Python)

MOD = 998244353

n = int(input())
input()

if n < 3:
    print(0)
else:
    print((pow(2, n - 1, MOD) - 2) % MOD)