## A Math Contest P10 - Tricky Multisets

View as PDF

Points: 12
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types

You are given a multiset . Each element in the multiset is an integer between and (inclusive), where appears times in the multiset.

In each operation, you choose two different elements of the multiset, and , such that . Then, and will be deleted from the multiset, and will be added to the multiset twice.

Find the minimum number of operations such that every element of is equal to . The data guarantees that such a sequence of operations will exist.

#### Input Specification

The first line contains an integer, .

The next line contains integers, .

#### Output Specification

Output the minimum number of operations to set all elements to modulo .

#### Sample Input

2
1 1 1 1 1

#### Sample Output

5

#### Explanation for Sample

Let's keep track of the elements in the multiset after each operation.

Initially, the multiset has the elements within it.

1. Choose and
2. Choose and
3. Choose and
4. Choose and
5. Choose and

It can be proven that is the minimum number of operations required to set everything to .