#P1165E. Two Arrays and Sum of Functions
Two Arrays and Sum of Functions
Description
You are given two arrays $a$ and $b$, both of length $n$.
Let's define a function $f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$.
Your task is to reorder the elements (choose an arbitrary order of elements) of the array $b$ to minimize the value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$. Since the answer can be very large, you have to print it modulo $998244353$. Note that you should minimize the answer but not its remainder.
The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and $b$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$.
The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \le 10^6$), where $b_j$ is the $j$-th element of $b$.
Print one integer — the minimum possible value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$ after rearranging elements of $b$, taken modulo $998244353$. Note that you should minimize the answer but not its remainder.
Input
The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and $b$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$.
The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \le 10^6$), where $b_j$ is the $j$-th element of $b$.
Output
Print one integer — the minimum possible value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$ after rearranging elements of $b$, taken modulo $998244353$. Note that you should minimize the answer but not its remainder.
Samples
5
1 8 7 2 4
9 7 2 9 3
646
1
1000000
1000000
757402647
2
1 3
4 2
20