Modular Array Equalization

Farmer John has an array a of N non‐negative integers and an integer M. In one operation, he may choose any index i and increment or decrement a[i] by 1. He would like to achieve the following: there exists an integer x such that for every index i (1 ≤ i ≤ N), a[i] − x is divisible by M (in other words, all the modified numbers are congruent modulo M). The minimum number of operations required to achieve this is called Farmer John’s boredom value.

Your task is to compute the minimum number of operations needed if Farmer John is allowed to choose x optimally. Note that an integer x may be any integer; however, the congruence condition only depends on x mod M. Hence, the answer is:

$$\min_{0\le r < M} \;\sum_{i=1}^{N} \min\Big(|(a_i \bmod M) - r|,\; M-|(a_i \bmod M)-r|\Big). $$

Input Format: The first line contains two integers N and M. The second line contains N non‐negative integers representing the array a.

Output Format: Print one integer – the minimum number of operations required so that there exists an integer x for which every a[i] - x is divisible by M.

Constraints:

• 1 ≤ N ≤ 2×10⁵
• 1 ≤ M ≤ 10⁹
• 0 ≤ a[i] (all a[i] are non-negative integers)

Example:

Input:
3 5
1 2 3
Output:
2

</p>

Explanation: The remainders of the array when divided by 5 are [1, 2, 3]. If we choose x such that x mod 5 = 2 then the adjustment cost is:

• For 1: cost = min(|1-2|, 5-|1-2|) = 1
• For 2: cost = 0
• For 3: cost = 1

Total cost = 1 + 0 + 1 = 2, which is optimal.

inputFormat

The first line contains two integers N and M. The second line contains N non-negative integers representing the array a.

Format:

N M
a[0] a[1] ... a[N-1]

outputFormat

Output one integer, the minimum number of operations needed so that there exists an integer x with the property that for every i, a[i] - x is divisible by M.

sample

3 5
1 2 3

2