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

Мадам Мадамант ждёт ребёнка и уже планирует династию фигуристов, в которой каждый родитель катается лучше своих детей.

Формально, у Мадамант есть $$$n$$$ пронумерованных фигуристов. У фигуриста $$$v$$$ есть целочисленный рейтинг $$$a_v$$$, и все рейтинги попарно различны. Возможная династия представляется корневым деревом на этих фигуристах.

Пусть $$$r$$$ — корень дерева. Для каждого фигуриста $$$v \ne r$$$ пусть $$$p_v$$$ — родитель $$$v$$$. Династия называется корректной, если $$$a_v \lt a_{p_v}$$$ для каждого $$$v \ne r$$$.

Счёт корректной династии равен $$$$$$ \sum_{v \ne r} (a_{p_v} - a_v). $$$$$$

Две династии различны, если различаются их корни или родитель хотя бы одного фигуриста.

Найдите сумму счетов всех корректных династий, которые может образовать Мадамант, по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — их рейтинги.

Гарантируется, что все $$$a_i$$$ попарно различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — сумму счетов всех корректных династий по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
1
10
3
1 2 3
4
4 1 3 2
2
1 1000000000
5
2 7 1 10 4
Выходные данные
0
5
27
1755646
414
Примечание

Во втором наборе входных данных фигурист с рейтингом $$$3$$$ должен быть корнем. Родителем фигуриста с рейтингом $$$2$$$ должен быть фигурист с рейтингом $$$3$$$, а фигурист с рейтингом $$$1$$$ может выбрать своим родителем любого из двух других фигуристов. Счета двух корректных династий равны $$$2$$$ и $$$3$$$, поэтому ответ равен $$$5$$$.

В четвёртом наборе входных данных существует лишь одна корректная династия. Её счёт равен $$$10^9 - 1 = 999\,999\,999$$$, а остаток от деления этого числа на $$$998\,244\,353$$$ равен $$$1\,755\,646$$$.