Another Contest 8 Problem 5 - U-Turn Finesse

View as PDF

Submit solution

Points: 15
Time limit: 0.5s
Memory limit: 64M

Problem type

Brandon likes sequences that go up and down. Given a list of N integers, compute the number of subsequences that go up and down - that is to say, there is a unique maximal integer in the subsequence, and the prefix of the subsequence ending at that integer is strictly increasing, and the suffix of the subsequence starting at that integer is strictly decreasing. The subsequence must be nonempty.

Recall that a subsequence is obtained by deleting some (possibly zero) integers from the list. Two subsequences are distinct if and only if some integer is deleted in one subsequence but not the other.


1 \le T \le 10^6

1 \le N \le 10^6

1 \le a_i \le N

The sum of all N in an input file will not exceed 10^6.

Input Specification

The first line contains a single positive integer T, the number of test cases.

T test cases follow.

Each test case starts with a line containing a single positive integer, N. The next line contains N space-separated positive integers.

Output Specification

Output T lines. On the ith line, output the number of subsequences that go up and down, modulo 998\,244\,353, for the ith test case.

Sample Input

1 3 2
1 3 2 4

Sample Output



There are no comments at the moment.