Let's call a sequence of integers $x_1, x_2, \dots, x_k$ MEX-correct if for all $i$ ($1 \le i \le k$) $|x_i - \operatorname{MEX}(x_1, x_2, \dots, x_i)| \le 1$ holds. Where $\operatorname{MEX}(x_1, \dots, x_k)$ is the minimum non-negative integer that doesn't belong to the set $x_1, \dots, x_k$. For example, $\operatorname{MEX}(1, 0, 1, 3) = 2$ and $\operatorname{MEX}(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 $998244353$.

Note: a subsequence of an array $a$ is a sequence $[a_{i_1}, a_{i_2}, \dots, a_{i_m}]$ meeting the constraints $1 \le i_1 < i_2 < \dots < i_m \le n$. If two different ways to choose the sequence of indices $[i_1, i_2, \dots, i_m]$ yield the same subsequence, the resulting subsequence should be counted twice (i. e. two subsequences are different if their sequences of indices $[i_1, i_2, \dots, i_m]$ are not the same).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$).

The sum of $n$ over all test cases doesn't exceed $5 \cdot 10^5$.


-----Output-----

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


-----Examples-----

Input
4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3
Output
4
2
31
7


-----Note-----

In the first example, the valid subsequences are $[0]$, $[1]$, $[0,1]$ and $[0,2]$.

In the second example, the valid subsequences are $[0]$ and $[1]$.

In the third example, any non-empty subsequence is valid.

Difficulty: HARD
Tags: Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import *
import sys
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt

def ceil(a, b):
	a = -a
	k = a // b
	k = -k
	return k
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f
mod = 998244353

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		mex_1 = [0] * (n + 2)
		mex_2 = [0] * (n + 2)
		for i in range(n):
			no = arr[i]
			if no == 0:
				mex_1[1] *= 2
				mex_1[1] %= mod
				mex_2[1] *= 2
				mex_2[1] %= mod
				mex_1[1] += 1
				mex_1[1] %= mod
			elif no == 1:
				mex_1[2] *= 2
				mex_1[2] %= mod
				mex_2[2] *= 2
				mex_2[2] %= mod
				mex_1[2] += mex_1[1]
				mex_1[2] %= mod
				mex_2[0] *= 2
				mex_2[0] %= mod
				mex_2[0] += 1
				mex_2[0] %= mod
			else:
				mex_1[no + 1] *= 2
				mex_1[no + 1] %= mod
				mex_2[no + 1] *= 2
				mex_2[no + 1] %= mod
				mex_1[no + 1] += mex_1[no]
				mex_1[no + 1] %= mod
				mex_2[no - 1] *= 2
				mex_2[no - 1] %= mod
				mex_2[no - 1] += mex_1[no - 1]
				mex_2[no - 1] %= mod
		print((sum(mex_1) + sum(mex_2)) % mod)
main()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = 4294967295
md = 998244353

def solve(n, aa):
	m1 = [0] * (n + 2)
	m2 = [0] * (n + 2)
	m1[0] = 1
	ans = 0
	for a in aa:
		if a - 1 >= 0:
			ans += m1[a - 1] + m2[a - 1]
			m2[a - 1] += m1[a - 1] + m2[a - 1]
			m2[a - 1] %= md
		ans += m1[a] + m1[a + 1] + m2[a + 1]
		m1[a + 1] += m1[a] + m1[a + 1]
		m2[a + 1] *= 2
		m1[a + 1] %= md
		m2[a + 1] %= md
		ans %= md
	print(ans)

def solve2(n, aa):

	def ok(bit):
		st = set()
		for (i, a) in enumerate(aa):
			if bit >> i & 1 == 0:
				continue
			st.add(a)
			for b in range(n + 1):
				if b not in st:
					if abs(b - a) > 1:
						return False
					break
		return True
	ans = 0
	for bit in range(1, 1 << n):
		if ok(bit):
			ans += 1
			print(bin(bit)[2:].zfill(n)[::-1])
	print(ans)
for testcase in range(II()):
	n = II()
	aa = LI()
	solve(n, aa)


from collections import defaultdict
mo = 998244353

def solve(n, A):
	d_minus = defaultdict(int)
	d_all = defaultdict(int)
	d_all[-1] = 1
	cnt = 0
	for a in A:
		cnt += d_all[a]
		d_all[a] = d_all[a] * 2 % mo
		cnt += d_minus[a]
		d_minus[a] = d_minus[a] * 2 % mo
		cnt += d_all[a - 2]
		d_minus[a] = (d_minus[a] + d_all[a - 2]) % mo
		cnt += d_all[a - 1]
		d_all[a] = (d_all[a] + d_all[a - 1]) % mo
		cnt += d_minus[a + 2]
		d_minus[a + 2] = d_minus[a + 2] * 2 % mo
		cnt = cnt % mo
	return cnt

def main():
	ans = []
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().split(' ')))
		ans.append(solve(n, A))
	for a in ans:
		print(a)
main()


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	MOD = 998244353
	dp = [[1, 0]]
	for i in a:
		if i - 1 >= len(dp):
			continue
		if i > 0:
			dp[i - 1][1] = (dp[i - 1][0] + 2 * dp[i - 1][1]) % MOD
		while i + 2 >= len(dp):
			dp.append([0, 0])
		dp[i + 1][0] = (2 * dp[i + 1][0] + dp[i][0]) % MOD
		dp[i + 1][1] = 2 * dp[i + 1][1] % MOD
	r = 0
	for (u, v) in dp:
		r = (r + u + v) % MOD
	print((r - 1) % MOD)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
MOD = 998244353
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	mex_table = defaultdict(lambda : defaultdict(lambda : 0))
	for i in a:
		mtm10 = mex_table[i - 1][i]
		mtm1p1 = mex_table[i - 1][i + 1]
		mt0p1 = mex_table[i][i + 1]
		mtp1p2 = mex_table[i + 1][i + 2]
		mtp1p3 = mex_table[i + 1][i + 3]
		mex_table[i - 1][i + 1] += mtm10
		mex_table[i - 1][i + 1] += mtm1p1
		mex_table[i + 1][i + 2] += mt0p1
		mex_table[i + 1][i + 2] += mtp1p2
		mex_table[i + 1][i + 3] += mtp1p3
		mex_table[i - 1][i + 1] %= MOD
		mex_table[i - 1][i + 1] %= MOD
		mex_table[i + 1][i + 2] %= MOD
		mex_table[i + 1][i + 2] %= MOD
		mex_table[i + 1][i + 3] %= MOD
		if i == 0:
			mex_table[1][2] += 1
			mex_table[1][2] %= MOD
		elif i == 1:
			mex_table[0][2] += 1
			mex_table[0][2] %= MOD
	ans = 0
	for key in mex_table:
		for key_2 in mex_table[key]:
			ans = (ans + mex_table[key][key_2]) % MOD
	print(ans % MOD)


from sys import stdin, stdout
MOD = 998244353

def solve_test(n, elements):
	dp_increasing = [0] * (n + 1)
	dp_alternate = [0] * (n + 1)
	for x in elements:
		dp_increasing[x] = dp_increasing[x] * 2
		if x >= 1:
			dp_increasing[x] = dp_increasing[x] + dp_increasing[x - 1]
		if x == 0:
			dp_increasing[x] = dp_increasing[x] + 1
		dp_increasing[x] %= MOD
		if x >= 1:
			dp_alternate[x - 1] = dp_alternate[x - 1] * 2
		if x >= 2:
			dp_alternate[x - 1] = dp_alternate[x - 1] + dp_increasing[x - 2]
		if x + 1 < n + 1:
			dp_alternate[x + 1] = dp_alternate[x + 1] * 2 % MOD
		if x == 1:
			dp_alternate[x - 1] = dp_alternate[x - 1] + 1
		dp_alternate[x] %= MOD
	answer = [(x + y) % MOD for (x, y) in zip(dp_increasing, dp_alternate)]
	return sum(answer) % MOD

def stress_test():
	n = int(100000.0)
	elements = [i for i in range(n)]
	solve_test(n, elements)

def read_input():
	tests = int(stdin.readline())
	for test in range(tests):
		n = int(stdin.readline())
		elements = [int(x) for x in stdin.readline().split()]
		stdout.write(str(solve_test(n, elements)) + '\n')

def read_file():
	with open('input.txt') as f:
		tests = int(f.readline())
		for test in range(tests):
			n = int(f.readline())
			elements = [int(x) for x in f.readline().split()]
			print(solve_test(n, elements))
read_input()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
Mod = 998244353
tc = 1
tc = int(input())
for test_cases in range(1, tc + 1):
	n = int(input())
	a = inp()
	dp1 = [0] * (n + 5)
	dp2 = [0] * (n + 5)
	dp1[0] = 1
	for i in a:
		dp1[i + 1] = (dp1[i + 1] + dp1[i + 1]) % Mod
		dp1[i + 1] = (dp1[i + 1] + dp1[i]) % Mod
		dp2[i - 1] = (dp2[i - 1] + dp2[i - 1]) % Mod
		dp2[i - 1] = (dp2[i - 1] + dp1[i - 1]) % Mod
		dp2[i + 1] = (dp2[i + 1] + dp2[i + 1]) % Mod
	ans = 0
	for i in range(n + 3):
		ans = (ans + dp1[i]) % Mod
		ans = (ans + dp2[i]) % Mod
	print((ans - 1 + Mod) % Mod)


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
mod = 998244353
for loop in range(tt):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	dp = [[0, 0] for i in range(n + 2)]
	dp[0][0] = 1
	for i in a:
		ch = []
		ch.append((i + 1, 0, dp[i][0]))
		ch.append((i + 1, 0, dp[i + 1][0]))
		ch.append((i + 1, 1, dp[i + 1][1]))
		ch.append((i - 1, 1, dp[i - 1][0]))
		ch.append((i - 1, 1, dp[i - 1][1]))
		for (x, y, p) in ch:
			dp[x][y] += p
			dp[x][y] %= mod
	ans = 0
	for i in range(n + 2):
		ans += dp[i][0] + dp[i][1]
	ans -= 1
	ans %= mod
	ANS.append(str(ans))
print('\n'.join(ANS))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	mo = 998244353
	dp1 = [0] * (n + 2)
	dp2 = [0] * (n + 2)
	dp1[0] = 1
	for num in arr:
		dp1[num + 1] = (2 * dp1[num + 1] + dp1[num]) % mo
		dp2[num + 1] = 2 * dp2[num + 1] % mo
		if num >= 1:
			dp2[num - 1] = (dp1[num - 1] + 2 * dp2[num - 1]) % mo
	ans = (sum(dp1 + dp2) % mo - 1) % mo
	return ans
for _ in range(int(input())):
	print(solve())


mod2 = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(dp1, dp2) = ([0] * (n + 2), [0] * (n + 2))
	dp1[0] = 1
	for i in a:
		dp1[i + 1] = (dp1[i + 1] * 2 + dp1[i]) % mod2
		if i > 0:
			dp2[i - 1] = (dp2[i - 1] * 2 + dp1[i - 1]) % mod2
		dp2[i + 1] = dp2[i + 1] * 2 % mod2
	s = sum(dp1 + dp2) % mod2
	print((s - 1) % mod2)


MOD = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	plus1 = [0] * (n + 2)
	minus1 = [0] * (n + 2)
	plus1[0] = 1
	for i in a:
		plus1[i + 1] = (2 * plus1[i + 1] % MOD + plus1[i]) % MOD
		if i > 0:
			minus1[i - 1] = (2 * minus1[i - 1] % MOD + plus1[i - 1]) % MOD
		minus1[i + 1] = 2 * minus1[i + 1] % MOD
	print(((sum(plus1) + sum(minus1)) % MOD - 1 + MOD) % MOD)


import sys

def solve(arr):
	data = [[0, 0] for _ in range(len(arr) + 5)]
	for item in arr:
		data[item][0] *= 2
		data[item][1] *= 2
		data[item + 2][1] *= 2
		if item > 0:
			data[item][0] += data[item - 1][0]
		if item > 1:
			data[item][1] += data[item - 2][0]
		if item == 0:
			data[item][0] += 1
		elif item == 1:
			data[item][1] += 1
		data[item][0] %= 998244353
		data[item][1] %= 998244353
	result = 0
	for item in data:
		result = (result + item[0] + item[1]) % 998244353
	return result
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	print(solve(arr))


from sys import stdin, stdout, setrecursionlimit
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sumx = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
mod = 998244353
for _ in range(I()):
	n = I()
	dp1 = [0] * (n + 2)
	dp2 = [0] * (n + 2)
	dp1[0] = 1
	for i in R():
		dp1[i + 1] = (dp1[i + 1] << 1) % mod
		dp1[i + 1] = (dp1[i + 1] + dp1[i]) % mod
		if i > 0:
			dp2[i - 1] = (dp2[i - 1] << 1) % mod
			dp2[i - 1] = (dp2[i - 1] + dp1[i - 1]) % mod
		dp2[i + 1] = (dp2[i + 1] << 1) % mod
	ans = 0
	for i in range(n + 2):
		ans = (ans + dp1[i] + dp2[i]) % mod
	print((ans - 1) % mod)


import sys, os, io
input = sys.stdin.readline
PI = 3.141592653589793
INF = float('inf')
MOD = 998244353

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	n = ii()
	a = li()
	ans = 0
	dp1 = [0 for i in range(n + 2)]
	dp2 = [0 for i in range(n + 2)]
	dp1[0] = 1
	zeros = 1
	for i in a:
		dp1[i + 1] = mul(dp1[i + 1], 2)
		dp1[i + 1] = add(dp1[i + 1], dp1[i])
		dp2[i + 1] = mul(dp2[i + 1], 2)
		if i != 0:
			dp2[i - 1] = mul(dp2[i - 1], 2)
			dp2[i - 1] = add(dp2[i - 1], dp1[i - 1])
	for i in dp1:
		ans = add(ans, i)
	for i in dp2:
		ans = add(ans, i)
	ans = sub(ans, dp1[0])
	print(ans)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = 998244353

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		dp = [[0, 0] for i in range(n + 2)]
		dp[0][0] = 1
		for i in a:
			dp[i + 1][0] += dp[i + 1][0] % mod
			dp[i + 1][1] += dp[i + 1][1] % mod
			dp[i + 1][0] += dp[i][0]
			dp[i + 1][0] %= mod
			if i - 1 >= 0:
				dp[i - 1][1] += dp[i - 1][1] + dp[i - 1][0]
				dp[i - 1][1] %= mod
		ans = 0
		for i in range(n + 2):
			ans = (ans + dp[i][0] + dp[i][1]) % mod
		print((ans - dp[0][0] + mod) % mod)
	return
main()


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
mod = 998244353
(t,) = I()
for _ in range(t):
	(n,) = I()
	l = I()
	an = 0
	dp = dd(int)
	miss = dd(int)
	for x in range(n):
		i = l[x]
		if i == 0:
			dp[0] = (2 * dp[0] + 1) % mod
			miss[1] = 2 * miss[1] % mod
		elif i == 1:
			dp[1] = (2 * dp[1] + dp[0]) % mod
			miss[2] = 2 * miss[2] % mod
			miss[0] = (2 * miss[0] + 1) % mod
		else:
			dp[i] = (2 * dp[i] + dp[i - 1]) % mod
			miss[i + 1] = 2 * miss[i + 1] % mod
			miss[i - 1] = (2 * miss[i - 1] + dp[i - 2]) % mod
	print((sum(dp.values()) + sum(miss.values())) % mod)


import os
import sys
from io import BytesIO, IOBase
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def main():
	M = 998244353
	for _ in range(nmbr()):
		n = nmbr()
		a = lst()
		dp = [[[0 for i in range(2)] for i in range(2)] for i in range(n + 1)]
		for v in a:
			if v == 0:
				dp[v][1][0] = (2 * dp[v][1][0] + 1) % M
				if v + 2 <= n:
					dp[v][0][1] = (2 * dp[v][0][1] + dp[v + 2][0][0]) % M
			else:
				dp[v][1][0] = (2 * dp[v][1][0] + dp[v - 1][1][0]) % M
				if v == 1:
					dp[1][0][0] = (2 * dp[1][0][0] + 1) % M
				if v - 2 >= 0:
					dp[v][0][0] = (2 * dp[v][0][0] + dp[v - 2][1][0] + dp[v - 2][0][1]) % M
				if v + 2 <= n:
					dp[v][0][1] = (2 * dp[v][0][1] + dp[v + 2][0][0]) % M
		ans = 0
		for i in range(n + 1):
			for j in range(2):
				for k in range(2):
					ans += dp[i][j][k]
					ans %= M
		sys.stdout.write(str(ans) + '\n')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(1):
	main()


import io
import os
from collections import deque
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
	if FILE_INPUT_MODE == 1:
		CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
		FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
	elif FILE_INPUT_MODE == 0:
		FD = 0
	DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
	if FD != 0:
		os.close(FD)

	def input():
		return DATA.readline().decode().rstrip('\r\n')

def solve():
	p = 998244353
	n = int(input())
	a = [int(word) for word in input().strip().split()]
	mex = [[0, 0] for i in range(max(a) + 2)]
	mex[0][0] = 1
	ans = 0
	for x in a:
		if x - 1 >= 0:
			ans = (ans + mex[x - 1][0] + mex[x - 1][1]) % p
		ans = (ans + mex[x][0]) % p
		ans = (ans + mex[x + 1][0] + mex[x + 1][1]) % p
		if x - 1 >= 0:
			mex[x - 1][1] = (mex[x - 1][1] * 2 + mex[x - 1][0]) % p
		mex[x + 1][0] = (mex[x + 1][0] * 2 + mex[x][0]) % p
		mex[x + 1][1] = mex[x + 1][1] * 2 % p
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
MODULUS = 998244353
from itertools import chain, combinations, product

def subsets(iterable, low=0, high=None):
	s = list(iterable)
	if high is None:
		high = len(s)
	return chain.from_iterable((combinations(s, r) for r in range(low, high + 1)))

def mex(A):
	sA = set(A)
	for i in range(0, 200):
		if i not in sA:
			return i
	assert False

def correct(seq):
	for i in range(len(seq)):
		if not 1 >= abs(seq[i] - mex(seq[0:i + 1])):
			return False
	return True

def subsequences(S):
	ret = []
	for indices in subsets(range(len(S))):
		ret += [[S[i] for i in indices]]
	return ret
from functools import lru_cache

def ans_bottom(S):
	i = len(S)
	sz = len(S) + 9
	dp1 = [1] * sz
	dp2 = [1] * sz
	while i > 0:
		i -= 1
		dp1_add = dict()
		dp2_add = dict()
		if S[i] + 1 < sz:
			dp1_add[S[i] + 1] = dp1[S[i] + 1]
		dp1_add[S[i] - 1] = dp1[S[i] - 1]
		if S[i] + 1 < sz:
			dp2_add[S[i] + 1] = dp2[S[i] + 1]
		if S[i] + 1 < sz:
			dp2_add[S[i]] = dp2[S[i] + 1]
		dp2_add[S[i] - 1] = dp1[S[i] - 1]
		for k in dp1_add:
			dp1[k] += dp1_add[k]
			dp1[k] %= MODULUS
		for k in dp2_add:
			dp2[k] += dp2_add[k]
			dp2[k] %= MODULUS
	return (dp2[0] - 1) % MODULUS

def ans(S):

	@lru_cache(None)
	def dp(mex_before, has_top, i):
		if i == len(S):
			return 1
		if has_top:
			ret = dp(mex_before, True, i + 1)
			if S[i] in [mex_before - 1, mex_before + 1]:
				ret += dp(mex_before, True, i + 1)
			return ret % MODULUS
		else:
			ret = dp(mex_before, False, i + 1)
			if S[i] + 1 == mex_before:
				ret += dp(mex_before, False, i + 1)
			if S[i] == mex_before:
				ret += dp(mex_before + 1, False, i + 1)
			if S[i] - 1 == mex_before:
				ret += dp(mex_before, True, i + 1)
			return ret % MODULUS
	return (dp(0, False, 0) - 1) % MODULUS

def ans_slow(S):
	ret = 0
	for s in subsequences(S):
		if len(s) > 0 and correct(s):
			ret += 1
	return ret
if False:
	import random
	tc = [0 for _ in range(1000)]
	print(ans(tc))
elif False:
	for N in range(10):
		for p in product(range(10), repeat=N):
			assert ans(p) == ans_bottom(p)
		print('checked', N)
elif True:
	for _ in range(read_int()):
		input()
		tc = read_int_list()
		print(ans_bottom(tc))


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def mex_sequences(n, a):
	sequences_by_head = {(0, 1): 0, (1, 0): 0}
	heads_by_mex = {0: [(0, 1)], 1: [(1, 0)]}
	for ai in a:
		new = {}
		mexes = [ai - 1, ai, ai + 1]
		for mex_ in mexes:
			for (mex, max) in heads_by_mex.get(mex_, []):
				if mex < max:
					if ai != mex:
						new[mex, max] = new.get((mex, max), 0) + sequences_by_head[mex, max]
						if ai == 1:
							if ai == max:
								new[mex, max] += 1
				elif ai == max:
					new[mex, max] = new.get((mex, max), 0) + sequences_by_head[mex, max]
					if ai == 0:
						new[mex, max] += 1
				elif ai == mex:
					add = sequences_by_head[mex, max]
					if add == 0:
						continue
					new[mex + 1, ai] = new.get((mex + 1, ai), 0) + add
				elif ai == mex + 1:
					add = sequences_by_head[mex, max]
					if add == 0:
						continue
					new[mex, ai] = new.get((mex, ai), 0) + add
		for head in new:
			sequences_by_head[head] = (sequences_by_head.get(head, 0) + new[head]) % 998244353
			(mex, _) = head
			heads = heads_by_mex.get(mex, [])
			if head in heads:
				continue
			heads_by_mex[mex] = heads + [head]
	total = 0
	for head in sequences_by_head:
		total += sequences_by_head[head]
		total %= 998244353
	return total
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sys.stdout.write(f'{mex_sequences(n, a)}\n')


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('DEBUG') is not None
if DEBUG:
	from varname.core import argname
	from inspect import currentframe

def debug(var, *more_vars):
	if not DEBUG:
		return
	var_names = argname('var', '*more_vars', func=debug)
	values = (var, *more_vars)
	name_and_values = [f'{var_name}={value}' for (var_name, value) in zip(var_names, values)]
	prefix = f'{currentframe().f_back.f_lineno:02d}: '
	print(f"{prefix}{', '.join(name_and_values)}")
INF = float('inf')
MOD = 998244353

def solve(N, A):
	B = [0] * (N + 10)
	C = [0] * (N + 10)
	B[-1] = 1
	res = 0
	for a in A:
		add_b = B[a] + B[a - 1]
		add_c = B[a - 2] + C[a]
		add_c2 = C[a + 2]
		B[a] = (B[a] + add_b) % MOD
		C[a] = (C[a] + add_c) % MOD
		C[a + 2] = (C[a + 2] + add_c2) % MOD
		res = (res + add_b + add_c + add_c2) % MOD
	return res

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		out = solve(N, A)
		output(f'{out}\n')
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def SLI():
	return sorted([int(i) for i in input().split()])

def LI_():
	return [int(i) - 1 for i in input().split()]

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 6
	n = random.randint(1, N)
	mn = 0
	mx = n
	a = [random.randint(mn, mx) for i in range(n)]
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = a
		bb = b
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def RE(E):
	rt = [[] for i in range(len(E))]
	for i in range(len(E)):
		for (nb, d) in E[i]:
			rt[nb] += ((i, d),)
	return rt

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]
show_flg = False
show_flg = True
ans = 0
mo = 998244353

def mex(x):
	m = 0
	for i in sorted(x):
		if i == m:
			m += 1
	return m

def check(x):
	n = len(x)
	for i in range(n):
		if abs(x[i] - mex(x[:i + 1])) > 1:
			return False
	return True

def naive(n, a):
	rt = 0
	N = 1 << n
	for i in range(1, N):
		s = []
		for j in range(n):
			if i >> j & 1:
				s += (a[j],)
		if check(s):
			rt += 1
	return rt

def solve(n, a):
	d1 = [0] * (n + 3)
	d2 = [0] * (n + 3)
	for i in range(n):
		c = a[i]
		d1[c] += d1[c]
		if c - 1 >= 0:
			d1[c] += d1[c - 1]
		d1[c] %= mo
		if c - 1 >= 0:
			d2[c - 1] += d2[c - 1]
		if c - 2 >= 0:
			d2[c - 1] += d1[c - 2]
		d2[c + 1] += d2[c + 1]
		d2[c] %= mo
		if c == 0:
			d1[c] += 1
		if c == 1:
			d2[0] += 1
	return sum(d1) % mo + sum(d2) % mo
for _ in range(I()):
	ans = 0
	n = I()
	a = LI()
	d1 = [0] * (n + 3)
	d2 = [0] * (n + 3)
	for i in range(n):
		c = a[i]
		d1[c] += d1[c]
		if c - 1 >= 0:
			d1[c] += d1[c - 1]
		d1[c] %= mo
		if c - 1 >= 0:
			d2[c - 1] += d2[c - 1]
		if c - 2 >= 0:
			d2[c - 1] += d1[c - 2]
		d2[c + 1] += d2[c + 1]
		d2[c] %= mo
		if c == 0:
			d1[c] += 1
		if c == 1:
			d2[0] += 1
	ans = sum(d1) % mo + sum(d2) % mo
	print(ans % mo)


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
mi = lambda : map(int, stdin.readline().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, stdin.readline().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, stdin.readline().split())
pr = print
rg = range
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0

def f(a):
	mex = 0
	used = [0] * (n + 2)
	for i in a:
		used[i] = 1
		while used[mex] == 1:
			mex += 1
		if abs(mex - i) > 1:
			return False
	return True
import random
t = ii()
for _ in range(t):
	n = ii()
	a = li()
	dp0 = [0] * (n + 3)
	dp1 = [0] * (n + 3)
	dp2 = [0] * (n + 3)
	for i in a:
		if i == 0:
			dp0[0] += dp0[0] + 1
			dp0[0] %= Mod
			dp2[1] += dp2[1] + dp1[2]
			dp2[1] %= Mod
		else:
			dp0[i] += dp0[i] + dp0[i - 1]
			dp0[i] %= Mod
			if i == 1:
				dp1[1] *= 2
				dp1[1] += 1
			else:
				dp1[i] *= 2
				dp1[i] += dp0[i - 2]
			dp1[i] %= Mod
			dp2[i + 1] += dp2[i + 1] + dp1[i + 2]
			dp2[i - 1] += dp2[i - 1]
			dp2[i + 1] %= Mod
			dp2[i - 1] %= Mod
	print((sum(dp0) + sum(dp1) + sum(dp2)) % Mod)


import sys, math
INF = float('inf')
mod = 998244353
input = lambda : sys.stdin.readline().rstrip()
li = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	N = int(input())
	A = li()
	x = N + 5
	data = [0] * x
	data2 = [0] * x
	ans = 0
	for i in range(N):
		a = data[A[i]]
		b = data2[A[i]]
		c = data2[A[i] + 2]
		if A[i] >= 1:
			a += data[A[i] - 1]
		if A[i] >= 2:
			b += data[A[i] - 2]
		if A[i] == 0:
			a += 1
		if A[i] == 1:
			b += 1
		a %= mod
		b %= mod
		ans += a + b + c
		ans %= mod
		data[A[i]] += a
		data[A[i]] %= mod
		data2[A[i]] += b
		data2[A[i] + 2] += c
		data2[A[i]] %= mod
	print(ans % mod)


def solve(test_case_num=-1):
	t = int(input())
	for _ in range(t):
		n = int(input())
		lst = list(map(int, input().split()))
		print(solution(n, lst))
MOD = 998244353

def add_and_mod(lst, MOD=MOD):
	rst = 0
	for n in lst:
		rst += n
	return rst % MOD

def solution(n, lst, MOD=MOD):
	mem = [0] * (n + 3)
	mem_hole_right = [0] * (n + 3)
	mem_hole_left = [0] * (n + 3)
	rst = 0
	for a in lst:
		if a == 0:
			mem[0] = add_and_mod([mem[0], mem[0], 1])
		elif True:
			mem[a] = add_and_mod([mem[a], mem[a], mem[a - 1]])
		mem_hole_right[a] = add_and_mod([mem_hole_right[a], mem_hole_right[a], mem_hole_left[a + 2]])
		if a == 0:
			continue
		elif a == 1:
			mem_hole_left[1] = add_and_mod([mem_hole_left[1], mem_hole_left[1], 1])
		elif True:
			mem_hole_left[a] = add_and_mod([mem_hole_left[a], mem_hole_left[a], mem_hole_right[a - 2], mem[a - 2]])
	for m in [mem, mem_hole_left, mem_hole_right]:
		rst += add_and_mod(m)
	return rst % MOD
solve()


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
tt = 1
tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	endNext = defaultdict(int)
	endBefore = defaultdict(int)
	endBefore[0] = 1
	for el in a:
		if el:
			k1 = endBefore[el - 1]
			k2 = endNext[el - 1]
			k3 = endBefore[el]
			k5 = endBefore[el + 1]
			k6 = endNext[el + 1]
			ans += k1 + k2 + k3 + k5 + k6
			ans %= omod
			endNext[el - 1] += k1 + k2
			endBefore[el + 1] += k3 + k5
			endNext[el + 1] += k6
			endNext[el - 1] %= omod
			endBefore[el + 1] %= omod
			endNext[el + 1] %= omod
		else:
			k3 = endBefore[el]
			k5 = endBefore[el + 1]
			k6 = endNext[el + 1]
			ans += k3 + k5 + k6
			ans %= omod
			endBefore[el + 1] += k3 + k5
			endNext[el + 1] += k6
			endBefore[el + 1] %= omod
			endNext[el + 1] %= omod
	print(ans % omod)


import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
m = 998244353
t = int(inpu())
for _ in range(t):
	n = int(inpu())
	a = list(map(int, inpu().split()))
	d = {(0, -1): 1}
	for i in range(n + 1):
		d[i + 1, i] = 0
	for i in range(n):
		d[i, i + 1] = 0
	for guy in a:
		if guy > 0:
			d[guy - 1, guy] = (2 * d[guy - 1, guy] + d[guy - 1, guy - 2]) % m
		d[guy + 1, guy] = (2 * d[guy + 1, guy] + d[guy, guy - 1]) % m
		if guy < n - 1:
			d[guy + 1, guy + 2] = 2 * d[guy + 1, guy + 2] % m
	tot = sum((d[guy] for guy in d))
	prin(str((tot - 1) % m) + '\n')


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	n = I()
	a = L()
	(dp1, dp2) = ([0] * (n + 2), [0] * (n + 2))
	dp1[0] = 1
	for i in a:
		dp1[i + 1] = (dp1[i + 1] * 2 + dp1[i]) % mod2
		if i > 0:
			dp2[i - 1] = (dp2[i - 1] * 2 + dp1[i - 1]) % mod2
		dp2[i + 1] = dp2[i + 1] * 2 % mod2
	s = 0
	for i in dp1 + dp2:
		s = (s + i) % mod2
	print((s - 1) % mod2)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
LOGN = 20
INF = 10 ** 9 + 5
MOD = 998244353

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	dp1 = [0 for _ in range(n + 2)]
	dp2 = [0 for _ in range(n + 2)]
	dp1[0] = 1
	for (i, elem) in enumerate(A):
		dp1[elem + 1] += dp1[elem + 1]
		dp2[elem + 1] += dp2[elem + 1]
		dp1[elem + 1] += dp1[elem]
		if elem - 1 >= 0:
			dp2[elem - 1] += dp2[elem - 1]
			dp2[elem - 1] += dp1[elem - 1]
			dp2[elem - 1] %= MOD
		dp1[elem + 1] %= MOD
		dp2[elem + 1] %= MOD
	ans = sum(dp1) + sum(dp2) - 1
	ans %= MOD
	print(ans)
for _ in range(int(input())):
	solve()


import sys
input = lambda : sys.stdin.buffer.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = li()
	(dp1, dp2) = ([0] * (n + 10), [0] * (n + 10))
	for x in a:
		v = 1 if x == 0 else dp1[x - 1]
		dp1[x] = (dp1[x] * 2 + v) % mod
		v = 1 if x == 1 else 0 if x == 0 else dp1[x - 2]
		dp2[x] = (dp2[x] * 2 + v) % mod
		dp2[x + 2] = dp2[x + 2] * 2 % mod
	print((sum(dp1) + sum(dp2)) % mod)


def solve(n, seq):
	mod = 998244353
	dynup = [0] * (n + 3)
	dyndown = [0] * (n + 3)
	for (i, x) in enumerate(seq):
		if x == 0:
			dyndown[1] = (2 * dyndown[1] + 1) % mod
			dynup[1] = (dynup[1] + dynup[1]) % mod
		elif x == 1:
			dyndown[2] = (dyndown[2] + dyndown[2] + dyndown[1]) % mod
			dynup[2] = (dynup[2] + dynup[2]) % mod
			dynup[0] = (dynup[0] + dynup[0] + 1) % mod
		else:
			dyndown[x + 1] = (dyndown[x + 1] + dyndown[x + 1] + dyndown[x]) % mod
			dynup[x - 1] = (dynup[x - 1] + dynup[x - 1] + dyndown[x - 1]) % mod
			dynup[x + 1] = (dynup[x + 1] + dynup[x + 1]) % mod
	ans = 0
	for x in dynup:
		ans = (ans + x) % mod
	for x in dyndown:
		ans = (ans + x) % mod
	return ans
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input().decode().strip())
for t in range(T):
	n = int(input().decode().strip())
	seq = [int(x) for x in input().decode().strip().split(' ')]
	assert len(seq) == n
	res = solve(n, seq)
	print(res, flush=True)


from sys import stdin, stdout
mod = 998244353

def pow_mod(x, y):
	if y == 1:
		return x % mod
	half_res = pow_mod(x, y // 2)
	result = half_res * half_res
	if y % 2 == 1:
		result *= x
	return result % mod
t = int(stdin.readline())
for tt in range(t):
	n = int(stdin.readline())
	a = [int(s) for s in stdin.readline().split()]
	ones = 0
	mx = 0
	for i in range(n):
		if a[i] == 1:
			ones += 1
		if a[i] > mx:
			mx = a[i]
	sm = pow_mod(2, ones) - 1 if ones > 0 else 0
	ending_to = [0 for i in range(mx + 1)]
	done_to = [0 for i in range(mx + 1)]
	for i in range(n):
		ending_to[a[i]] *= 2
		if a[i] != 0:
			ending_to[a[i]] += ending_to[a[i] - 1]
		else:
			ending_to[a[i]] += 1
		ending_to[a[i]] %= mod
		if a[i] >= 2:
			done_to[a[i] - 1] *= 2
			done_to[a[i] - 1] += ending_to[a[i] - 2]
			done_to[a[i] - 1] %= mod
		if a[i] <= mx - 1 and done_to[a[i] + 1] > 0:
			done_to[a[i] + 1] *= 2
			done_to[a[i] + 1] %= mod
	for i in range(mx + 1):
		sm = (sm + ending_to[i] + done_to[i]) % mod
	sm %= mod
	stdout.write(str(sm) + '\n')