C++ :

#include <cstdio>
#include <algorithm>
using namespace std;
/*
  奖金：每次只能给某个数 +1，要求最终 n 个数两两不同，求最少加的总次数。
  做法：把序列升序排序后从左到右扫描。若 a[i] <= a[i-1]，就必须把 a[i] 抬到 a[i-1]+1，
  代价 a[i-1]-a[i]+1，并更新 a[i]。
  升序处理是最优的：让小的数先占据低位，大的数被抬高的幅度最小。
  n <= 300000，ai <= 1000000，代价总和可能达到 ~4.5e10，需用 long long。
  样例 1 1 3 2 -> 排序 1 1 2 3 -> 抬成 1 2 3 4，代价 0+1+1+1 = 3。
*/
static int a[300005];
int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    long long s = 0;
    for(int i = 1; i < n; i++){
        if(a[i] <= a[i - 1]){
            s += (long long)(a[i - 1] - a[i] + 1);
            a[i] = a[i - 1] + 1;
        }
    }
    printf("%lld\n", s);
    return 0;
}