W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Multiset is a mathematical object similar to a set, but each member of a multiset may have more than one membership. Just as with any set, the members of a multiset can be ordered in many ways. We call each such ordering a permutation of the multiset. For example, among the permutations of the multiset there are and .
We will say that one permutation of a given multiset is smaller (in lexicographic order) than another permutation, if on the first position that does not match the first permutation has a smaller element than the other one. All permutations of a given multiset can be numbered (starting from one) in an increasing order.
Write a programme that
The first line of the standard input holds two integers and (, ), separated by a single space. These denote, respectively, the cardinality of the multiset and \dots\ the number . The second line of the standard input contains positive integers (), separated by single spaces and denoting successive elements of the multiset permutation.
The first and only line of the standard output is to hold one integer, the remainder modulo of the rank of the input permutation in the lexicographic ordering.
For the input data:
4 1000 2 1 10 2
the correct result is:
5
All the permutations smaller (with respect to lexicographic order) than the one given are: , , and .
Task author: Jakub Radoszewski.