C. Красивая последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем последовательность целых чисел красивой, если выполняются следующие условия:

  • ее длина не менее $$$3$$$;
  • для каждого элемента, кроме первого, существует элемент слева, который меньше его;
  • для каждого элемента, кроме последнего, существует элемент справа, который больше его;

Например, $$$[1, 4, 2, 4, 7]$$$ и $$$[1, 2, 4, 8]$$$ являются красивыми, а $$$[1, 2]$$$, $$$[2, 2, 4]$$$ и $$$[1, 3, 5, 3]$$$ не являются.

Напомним, что подпоследовательность — это последовательность, которую можно получить из другой последовательности, удалив некоторые элементы, не меняя порядок оставшихся элементов.

Задан массив целых чисел $$$a$$$ размером $$$n$$$, в котором каждый элемент от $$$1$$$ до $$$3$$$. Ваша задача — посчитать количество красивых подпоследовательностей массива $$$a$$$. Поскольку ответ может быть большим, выведите его по модулю $$$998244353$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 3$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество красивых подпоследовательностей массива $$$a$$$ по модулю $$$998244353$$$.

Пример
Входные данные
4
7
3 2 1 2 2 1 3
4
3 1 2 2
3
1 2 3
9
1 2 3 2 1 3 2 2 3
Выходные данные
3
0
1
22
Примечание

В первом наборе входных данных примера следующие подпоследовательности являются красивыми:

  • $$$[a_3, a_4, a_7]$$$;
  • $$$[a_3, a_5, a_7]$$$;
  • $$$[a_3, a_4, a_5, a_7]$$$.