Dãy con MEX-chuẩn

Ký hiệu $MEX(x_1,x_2,\dots ,x_k)$ là số nguyên không âm nhỏ nhất không xuất hiện trong các số $x_1,x_2,\dots ,x_k$. Chẳng hạn $MEX(1,0,1,3)=2$ và $MEX(2,1,5)=0$.

Một dãy số nguyên $x_1,x_2,\dots ,x_k$ được gọi là MEX-chuẩn nếu với mọi $i$ ($1\le i\le k$) đều thỏa mãn

$$|x_i-MEX(x_1,x_2,\dots ,x_i)|\le 1.$$

Nói cách khác, điều kiện phải đúng tại mọi tiền tố của dãy, với MEX được tính lại trên đúng tiền tố đó.

Cho mảng $a$ gồm $n$ số nguyên không âm. Hãy đếm số dãy con khác rỗng của $a$ là dãy MEX-chuẩn. Kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho $998244353$.

Dãy con của mảng $a$ là dãy $[a_{i_1},a_{i_2},\dots ,a_{i_m}]$ với $1\le i_1<i_2<\dots <i_m\le n$. Hai dãy con được coi là khác nhau khi bộ chỉ số $[i_1,i_2,\dots ,i_m]$ của chúng khác nhau, kể cả khi chúng tạo ra cùng một dãy giá trị.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $n$: độ dài mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số dãy con MEX-chuẩn khác rỗng của mảng, lấy phần dư khi chia cho $998244353$.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n\le 5·{10}^5$
• $0\le a_i\le n$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $5·{10}^5$.

Ví dụ