Another Contest 9 Problem 2 - Counting Down the Days

Points: 7

Time limit: 1.0s

Memory limit: 256M

Problem type

Nick is learning how to do yoga. Over the course of the next $N$ ~N~ days, he will pick a contiguous nonempty block of days and do yoga during all of them. Each day has a score associated with it. The score of the yoga interval is equal to the product of all the scores of the days when Nick did yoga.

Compute the maximum possible score Nick can get.

Constraints

$1 \le T \le 10^5$ ~1 \le T \le 10^5~

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

The sum of $N$ ~N~ over all test cases is at most $10^6$ ~10^6~.

$|s_i| \le 2$ ~|s_i| \le 2~

Input Specification

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

Each test case starts with a line containing a single positive integer $N$ ~N~. The next line contains $N$ ~N~ space-separated integers, the $s_i$ ~s_i~ values representing the scores of the $N$ ~N~ days in order.

Output Specification

Output the answers for the $T$ ~T~ test cases in order. There should be no blank lines in your output.

The answer for the $i$ ~i~th test case should be on the $i$ ~i~th line. If $M$ ~M~ is the maximum score that Nick can attain when doing yoga, output $M$ ~M~ modulo 998244353. Note that you are trying to maximize $M$ ~M~, not $M$ ~M~ modulo 998244353.

Sample Input

2
3
2 -2 2
30
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Sample Output

2
75497471

Comments

0

yunz_qiao commented on July 11, 2022, 8:52 p.m.

will s[i] possilby be 0

0

Evanhyd commented on July 11, 2022, 9:36 p.m.

put an assertion in your code, and test it out. many languages have built-in assert(), otherwise, you can do some silly stuff like:

if(!CheckValid(x)) { while(true){} }