P15595 [ICPC 2020 Jakarta R] Shopping Changes

Felix and his $M$ friends are having a shopping frenzy today. From a recent cash transaction, he received a change with $N$ banknotes. Felix would like to slip the banknotes he received into his wallet without changing their order. For example, let’s assume that Felix received a change with $N = 4$ banknotes in the following order: $C_1\ C_2\ C_3\ C_4$. Supposed there are $3$ banknotes in Felix’s wallet in the following order: $W_1\ W_2\ W_3$, then there are four possible ways to slip the change into Felix’s wallet. 1. Slip the change before the $1^\text{st}$ banknote. After slipping the change, the banknotes in his wallet are in the following order: $C_1\ C_2\ C_3\ C_4\ W_1\ W_2\ W_3$. 2. Slip the change between the $1^\text{st}$ and $2^\text{nd}$ banknotes. After slipping the change, the banknotes in his wallet are in the following order: $W_1\ C_1\ C_2\ C_3\ C_4\ W_2\ W_3$. 3. Slip the change between the $2^\text{nd}$ and $3^\text{rd}$ banknotes. After slipping the change, the banknotes in his wallet are in the following order: $W_1\ W_2\ C_1\ C_2\ C_3\ C_4\ W_3$. 4. Slip the change after the $3^\text{rd}$ banknote. After slipping the change, the banknotes in his wallet are in the following order: $W_1\ W_2\ W_3\ C_1\ C_2\ C_3\ C_4$. Being a tidy person, Felix would like the banknotes in his wallet to be as sorted as possible. Therefore, he would like to slip the change in a way that minimizes the **inversion count** of his wallet after the slip. The **inversion count** of a wallet is the number of pairs of banknotes $(x, y)$ in the wallet such that: - banknote $x$ is closer to the front than banknote $y$, and - banknote $x$ has strictly more value than banknote $y$. Feeling a bit generous today, instead of keeping the change, Felix would like to give them to one of his friends and slip the change into their wallet. The $i^\text{th}$ friend has a wallet containing $L_i$ banknotes which values are $W_i[1], W_i[2], \dots, W_i[L_i]$ respectively from the front-most to the back-most of the wallet. Felix would like to give the change to his friend that can minimize the inversion count of their wallet after slipping the change. Therefore, for each of his friends, Felix needs to count the minimum inversion count of their wallet if he slips the change into their wallet.

Input begins with a line containing two integers: $N\ M$ ($1 \leq N, M \leq 100\,000$) representing the number of banknotes in the change and the number of Felix’s friends, respectively. The next line contains $N$ integers: $C_i$ ($1 \leq C_i \leq 10^9$) representing the value of the banknotes in the change. The next $M$ lines each begin with an integer $L_i$ ($1 \leq L_i \leq 200\,000$) representing the number of banknotes in the $i^\text{th}$ friend’s wallet, followed by $L_i$ integers: $W_i[j]$ ($1 \leq W_i[j] \leq 10^9$) representing the value of the banknotes in the wallet. The sum of all $L_i$ is not more than $200\,000$.

For each friend in the same order as input, output in a line an integer representing the minimum inversion count of their wallet if Felix slips the change into their wallet.

#### Explanation for the sample input/output #1 For the $1^\text{st}$ friend, by slipping the change between the $3^\text{rd}$ and $4^\text{th}$ banknotes, the banknotes in the wallet are in the following order: $2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$. Therefore, the inversion count of the wallet is $0$. For the $2^\text{nd}$ friend, by slipping the change before the $1^\text{st}$ banknote, the banknotes in the wallet are in the following order: $5\ 6\ 7\ 100\ 99$. Therefore, the inversion count of the wallet is $1$. There is no way to achieve a smaller inversion count. For the $3^\text{rd}$ friend, by slipping the change between the $1^\text{st}$ and $2^\text{nd}$ banknotes, or between the $2^\text{nd}$ and $3^\text{rd}$ banknotes, the inversion count of the wallet is $1$. There is no way to achieve a smaller inversion count.