Problem Statement

A ship has n doors with locks. For the crew to board, all doors must be unlocked, which happens only when all locks have the same value. The array locks represents n locks, where locks[i] is the initial value of the i -th lock. In one operation, you can change a lock's value according to these rules: If the current value is 1 , the next value can be k or 2 . If the current value is k , the next value can be k - 1 or 1 . Otherwise, the next value can be current value - 1 or current value + 1 . Find the minimum number of operations needed to make all lock values the same. Input Format Line 1: the integer k . Line 2: the integer n . Line 3: n space-separated integers, the values locks[i] . Output Format Print a single integer (it can exceed 32 bits): the minimum number of operations required to have a common value on all locks. Constraints 2 ≤ k ≤ 10 9 1 ≤ n ≤ 10 5 1 ≤ locks[i] ≤ k Example Input 100 3 1 2 99 Output 3 Optimal strategy (making all locks have value 1): Lock