20691번 - 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₁ C₂ C₃ C₄. Supposed there are 3 banknotes in Felix’s wallet in the following order: W₁ W₂ W₃, then there are four possible ways to slip the change into Felix’s wallet.

1. Slip the change before the 1^st banknote. After slipping the change, the banknotes in his wallet are in the following order: C₁ C₂ C₃ C₄ W₁ W₂ W₃.
2. Slip the change between the 1^st and 2^nd banknotes. After slipping the change, the banknotes in his wallet are in the following order: W₁ C₁ C₂ C₃ C₄ W₂ W₃.
3. Slip the change between the 2^nd and 3^rd banknotes. After slipping the change, the banknotes in his wallet are in the following order: W₁ W₂ C₁ C₂ C₃ C₄ W₃.
4. Slip the change after the 3^rd banknote. After slipping the change, the banknotes in his wallet are in the following order: W₁ W₂ W₃ C₁ C₂ C₃ C₄.

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 th friend has a wallet containing L_i banknotes which values are W_i[1], W_i[2], ..., 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 ≤ N, M ≤ 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 ≤ C_i ≤ 10⁹) representing the value of the banknotes in the change. The next M lines each begins with an integer L_i (1 ≤ L_i ≤ 200 000) representing the number of banknotes in the i^th friend’s wallet, followed by L_i integers: W_i[j] (1 ≤ W_i[j] ≤ 10⁹) 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.