8636: Darkmoon Faire

One day, you go to the Darkmoon Faire with your friends.

You begin to play a game called "Finding the Ridiculous Partitions"!

An array is "ridiculous", if the maximum element of the array lies on an odd index, while the minimum element of the array lies on an even index.

You are given a sequence a of length n. It's guaranteed that all ai are pairwise distinct.

You can partition the sequence into several (probably one) continuous intervals, such that the intervals don't intersect and that every position belongs to exactly one interval. For every interval, we can view it as a one-based array. A partition is "ridiculous", if for each of the intervals, its corresponding array is ridiculous.

Please calculate the number of "ridiculous partitions" of the given sequence.

Since the answer can be very large, you only need to output the answer modulo 998244353.

The input consists of multiple test cases.

The first line contains an integer $T(1\le T\le 5)$ denoting the number of test cases.

For each test case, the first line contains a single integer n (1≤n≤3×105).

The second line contains n integers ai (1≤ai≤109), it's guaranteed that ai！=aj for all $i！=j$.

The sum of n over all test cases does not exceed 106.

2
5
3 2 4 1 8
10
9 1 2 4 7 3 6 8 10 5

2
5