题解 | mex

import java.util.Arrays;
import java.util.Objects;
import java.util.Random;
import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/6
 * @description BGN62 mex
 */
public class Main {
	
  	//1.观察再开始做，一开始就直接用死算很麻烦还不一定能通过
  	//2.三种情况 
//    一：数组没0且不完全相同 -> 可能不能相等，输出-1
//    二：数组完全相同 -> 输出0
//    三：上述都不满足 -> 排序计算差分，将 diff[i] > 1的加起来就行
  //3.注意精度
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] a = new long[n], diff = new long[n + 1];

        boolean isDiff = false, having_zero = false;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
            if (a[i] == 0) having_zero = true;
            if (i > 0 && a[i] != a[i - 1]) isDiff = true;
        }

        if (!having_zero && isDiff) System.out.println(-1);
        else if (!isDiff) System.out.println(0);
        else {
            long result = 0;
            //sort(a, 0, a.length - 1, true);
            Arrays.sort(a);
            for (int i = 1; i < n; i++) {
                diff[i] = i == 0 ? a[i] : a[i] - a[i - 1];
                if (diff[i] > 1) result += diff[i] - 1;
            }
            System.out.println(result + 1);
        }
    }

    //快排
//    public static void sort(int[] a, int l, int r, boolean ascending) {
//        if (r <= l) return;
//        int pivot = partition(a, l, r, ascending);
//        sort(a, l, pivot - 1, ascending);
//        sort(a, pivot + 1, r, ascending);
//    }
//
//    public static int partition(int[] a, int l, int r, boolean ascending) {
//        int index = new Random().nextInt(r - l + 1) + l;
//        swap(a, index, r);
//
//        int p1 = l - 1, p2;
//        for (p2 = l; p2 < r; p2++) {
//            //降序
//            if (ascending ? a[p2] < a[r] : a[p2] > a[r]) {
//                swap(a, p2, ++p1);
//            }
//        }
//        swap(a, r, ++p1);
//        return p1;
//    }
//
//    public static void swap(int[] a, int i, int j) {
//        if (a[i] != a[j]) {
//            int tmp = a[i];
//            a[i] = a[j];
//            a[j] = tmp;
//        }
//    }
//
//    @Test
//    public void test() {
//        int[] a = new int[]{4, 1, 5, 6, 2, 7, 8, 3};
//        sort(a, 0, a.length - 1, true);
//        for (int j : a) {
//            System.out.println(j);
//        }
//    }
}