P3477 [POI 2008] PER-Permutation

A multiset is like a set, but elements may appear more than once. A permutation of a multiset is any ordering of its elements. For example, among the permutations of the multiset $\{1, 1, 2, 3, 3, 3, 7, 8\}$, there are $\{2, 3, 1, 3, 3, 7, 1, 8\}$ and $\{8, 7, 3, 3, 3, 2, 1, 1\}$. We use lexicographic order to compare two permutations: at the first position where they differ, the permutation with the smaller element is considered smaller. All permutations of a given multiset can be sorted increasingly and numbered starting from $1$ (this number is called the rank). Task: Given a permutation of a multiset of size $n$ and a positive integer $m$, compute the remainder modulo $m$ of the rank of this permutation in lexicographic order.

- The first line contains two integers $n$ and $m$ ($1 \le n \le 300000,\ 2 \le m \le 10^9$): the size of the multiset and the modulus $m$. - The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 300000$), the given permutation of the multiset.

Output a single integer: the rank of the given permutation in lexicographic order, taken modulo $m$.

Thanks to @远航之曲 for the translation. Translated by ChatGPT 5.