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)