Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Вам дан массив $$$[p_1, p_2, \dots, p_n]$$$, где все элементы различны.

Вы можете выполнить несколько (возможно, ни одной) операций с ним. В одной операции вы можете выбрать непрерывный подотрезок $$$p$$$ и удалить все элементы из этого подотрезка, кроме минимального элемента в этом подотрезке. Например, если $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ и вы выберете подотрезок от $$$3$$$-го элемента до $$$6$$$-го элемента, полученный массив будет $$$[3, 1, 2, 6]$$$.

Массив $$$a$$$ называется достижимым, если его можно получить из $$$p$$$ с помощью нескольких (возможно, нуля) вышеупомянутых операций. Вычислите количество достижимых массивов и выведите его по модулю $$$998244353$$$.

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

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

Каждый набор входных данных состоит из двух строк. Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). Вторая строка содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$).

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

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

Для каждого теста выведите одно целое число — количество достижимых массивов, взятое по модулю $$$998244353$$$.

Пример
Входные данные
3
2
2 1
4
2 4 1 3
5
10 2 6 3 4
Выходные данные
2
6
12