[Solution] MEX Sequences solution codeforces

MEX Sequences solution codeforces

Let’s call a sequence of integers 𝑥1,𝑥2,,𝑥𝑘x1,x2,…,xk MEX-correct if for all 𝑖i (1𝑖𝑘1≤i≤k|𝑥𝑖MEX(𝑥1,𝑥2,,𝑥𝑖)|1|xi−MEX⁡(x1,x2,…,xi)|≤1 holds. Where MEX(𝑥1,,𝑥𝑘)MEX⁡(x1,…,xk) is the minimum non-negative integer that doesn’t belong to the set 𝑥1,,𝑥𝑘x1,…,xk. For example, MEX(1,0,1,3)=2MEX⁡(1,0,1,3)=2 and MEX(2,1,5)=0MEX⁡(2,1,5)=0.

You are given an array 𝑎a consisting of 𝑛n non-negative integers. Calculate the number of non-empty MEX-correct subsequences of a given array. The number of subsequences can be very large, so print it modulo 998244353998244353.

Note: a subsequence of an array 𝑎a is a sequence [𝑎𝑖1,𝑎𝑖2,,𝑎𝑖𝑚][ai1,ai2,…,aim] meeting the constraints 1𝑖1<𝑖2<<𝑖𝑚𝑛1≤i1<i2<⋯<im≤n. If two different ways to choose the sequence of indices [𝑖1,𝑖2,,𝑖𝑚][i1,i2,…,im] yield the same subsequence, the resulting subsequence should be counted twice (i. e. two subsequences are different if their sequences of indices [𝑖1,𝑖2,,𝑖𝑚][i1,i2,…,im] are not the same).

Input MEX Sequences solution codeforces

The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛51051≤n≤5⋅105).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖𝑛0≤ai≤n).

The sum of 𝑛n over all test cases doesn’t exceed 51055⋅105.

Output

For each test case, print a single integer — the number of non-empty MEX-correct subsequences of a given array, taken modulo 998244353998244353.

Example

input

Copy
4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3

output MEX Sequences solution codeforces

Copy
4
2
31
7    [Solution] Long Comparison solution codeforces