E2. Смотрим на башни (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственные различия между простой и сложной версией задачи заключаются в ограничениях на $$$t$$$ и $$$n$$$.

Рассмотрим ряд из $$$m$$$ башен; высота $$$i$$$-й башни в ряду равна $$$h_i$$$.

Если вы смотрите на этот ряд башен слева, вы видите все башни, которые строго выше всех башен перед ними. Аналогично, если вы смотрите на этот ряд башен справа, вы видите все башни, которые строго выше всех башен после них. Например, если высоты башен равны $$$[3, 5, 5, 7, 4, 6, 7, 2, 4]$$$, то:

  • если вы смотрите слева, то вы видите башни с высотами $$$3$$$, $$$5$$$ и $$$7$$$;
  • если вы смотрите справа, то вы видите башни с высотами $$$7$$$ и $$$4$$$.

Обозначим $$$L(h)$$$ как множество высот, которые вы видите слева, и $$$R(h)$$$ как множество высот, которые вы видите справа, когда последовательность высот равна $$$h$$$. В приведенном выше примере $$$L(h) = \{3, 5, 7\}$$$, а $$$R(h) = \{4, 7\}$$$.

Вам дана последовательность $$$a_1, a_2, \dots, a_n$$$. Ваша задача — вычислить количество подпоследовательностей $$$a$$$, таких что $$$L(a) = L(a')$$$ и $$$R(a) = R(a')$$$, где $$$a'$$$ — это рассматриваемая вами подпоследовательность. Две подпоследовательности различны, если индексы выбранных элементов различны.

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

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

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

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

Для каждого набора входных данных выведите одно целое число — количество подпоследовательностей $$$a'$$$ данной последовательности $$$a$$$, таких что $$$L(a) = L(a')$$$ и $$$R(a) = R(a')$$$. Поскольку это число может быть огромным, выведите его по модулю $$$998244353$$$.

Пример
Входные данные
5
5
4 2 4 8 3
5
1 2 3 2 1
6
1 2 3 3 2 1
9
3 5 5 7 4 6 7 2 4
1
10
Выходные данные
5
1
3
51
1
Примечание

В первом примере $$$L(a) = \{4, 8\}$$$, $$$R(a) = \{3, 8\}$$$. Подпоследовательности, включенные в ответ, это:

  • $$$[4, 8, 3]$$$ ($$$1$$$-й, $$$4$$$-й и $$$5$$$-й элементы);
  • $$$[4, 8, 3]$$$ ($$$3$$$-й, $$$4$$$-й и $$$5$$$-й элементы);
  • $$$[4, 2, 8, 3]$$$ ($$$1$$$-й, $$$2$$$-й, $$$4$$$-й и $$$5$$$-й элементы);
  • $$$[4, 4, 8, 3]$$$ ($$$1$$$-й, $$$3$$$-й, $$$4$$$-й и $$$5$$$-й элементы);
  • $$$[4, 2, 4, 8, 3]$$$ (вся последовательность).

Во втором примере единственной допустимой подпоследовательностью является сама данная последовательность.