|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
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: C1 C2 C3 C4. Supposed there are 3 banknotes in Felix’s wallet in the following order: W1 W2 W3, then there are four possible ways to slip the change into Felix’s wallet.
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:
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 Li banknotes which values are Wi, Wi, ..., Wi[Li] 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: Ci (1 ≤ Ci ≤ 109) representing the value of the banknotes in the change. The next M lines each begins with an integer Li (1 ≤ Li ≤ 200 000) representing the number of banknotes in the ith friend’s wallet, followed by Li integers: Wi[j] (1 ≤ Wi[j] ≤ 109) representing the value of the banknotes in the wallet. The sum of all Li 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.
3 3 5 6 7 6 2 3 4 8 9 10 2 100 99 3 5 6 7
0 1 1
For the 1st friend, by slipping the change between the 3rd and 4th 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 2nd friend, by slipping the change before the 1st 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 3rd friend, by slipping the change between the 1st and 2nd banknotes, or between the 2nd and 3rd banknotes, the inversion count of the wallet is 1. There is no way to achieve a smaller inversion count
3 2 7 6 5 6 2 3 4 8 9 10 6 10 9 8 4 3 2