Задано два массива \(a\) и \(b\), оба длины \(n\).
Давайте определим функцию \(f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i\).
Ваша задача — переупорядочить элементы (выбрать произвольный порядок элементов) массива \(b\), чтобы минимизировать значение \(\sum\limits_{1 \le l \le r \le n} f(l, r)\). Так как ответ может быть очень большим, вам необходимо вывести его по модулю \(998244353\). Заметьте, что вы должны минимизировать ответ, а не его остаток.
Первая строка входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — количество элементов в \(a\) и \(b\).
Вторая строка входных данных содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)), где \(a_i\) равно \(i\)-му элементу \(a\).
Третья строка входных данных содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(1 \le b_j \le 10^6\)), где \(b_j\) равно \(j\)-му элементу \(b\).
Выведите одно целое число — минимально возможное значение \(\sum\limits_{1 \le l \le r \le n} f(l, r)\) после перестановки элементов массива \(b\), взятое по модулю \(998244353\). Заметьте, что вы должны минимизировать ответ, а не его остаток.
5 1 8 7 2 4 9 7 2 9 3
646
1 1000000 1000000
757402647
2 1 3 4 2
20
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач