Олимпиадный тренинг

Задача . D. Схлопывание массива


Вам дан массив \([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\).


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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя