|
||||||||||
Darkmoon FaireTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 307 Accepted Submission(s): 178 Problem Description $\space \space$ *Ahead of You, Down the Path* $\space \space$ *A Majestic, Magical Faire!* $\space \space$ *Ignore the Darkened, Eerie Woods* $\space \space$ *Ignore the Eyes That Blink and Stare* $\space \space$ *Fun & Games & Wondrous Sights!* $\space \space$ *Music & Fireworks to Light Up the Night!* $\space \space$ *Do Not Stop! You're Nearly There!* $\space \space$ *Behold, My Friend: THE 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 $a_i$ 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. Input The input consists of multiple test cases. The first line contains an integer $T\ (1\leq T\leq 5)$ denoting the number of test cases. For each test case, the first line contains a single integer $n\ (1 \leq n \leq 3\times 10^5)$. The second line contains $n$ integers $a_i\ (1 \leq a_i \leq 10^9)$, it's guaranteed that $a_i \neq a_j$ for all $i\neq j$. The sum of $n$ over all test cases does not exceed $10^6$. Output For each test case, output one line containing the answer modulo 998244353. Sample Input
Sample Output
Source | ||||||||||
|