Tối Ưu Hóa MEX Của Mảng

Bối cảnh

Bạn được cho một mảng A có độ dài N. Bạn có thể thực hiện phép toán sau bất kỳ số lần nào:

Yêu cầu

• Chọn bất kỳ chỉ số i (1 ≤ i ≤ N) và tăng A[i] lên 1 hoặc giảm A[i] xuống 1.

Tìm số lượng phép toán tối thiểu cần thực hiện để làm cho MEX của mảng đạt giá trị tối đa có thể.

MEX (Minimum Excluded) của một mảng là số nguyên không âm nhỏ nhất không xuất hiện trong mảng. Ví dụ:

• MEX của [2, 2, 1] là 0, vì 0 không xuất hiện trong mảng.
• MEX của [3, 1, 0, 1] là 2, vì 0 và 1 xuất hiện trong mảng, nhưng 2 thì không.
• MEX của [0, 3, 1, 2] là 4, vì 0, 1, 2 và 3 xuất hiện trong mảng, nhưng 4 thì không.

Input

Dòng đầu tiên chứa một số nguyên T, số lượng test cases. Mỗi test case bao gồm nhiều dòng:

• Dòng đầu tiên chứa số nguyên N — số lượng phần tử trong mảng A.
• Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách — các phần tử của mảng A.

Output

Với mỗi test case, in ra trên một dòng số lượng phép toán tối thiểu cần thực hiện để làm cho MEX của mảng đạt giá trị tối đa có thể.

Ràng buộc

• \(1 ≤ T ≤ 10^4\)
• \(1 ≤ N ≤ 2 × 10^5\)
• \(0 ≤ A[i] ≤ N\)
• Tổng số phần tử \(N\) trong tất cả các test cases không vượt quá \(2 × 10^5\).

Ví dụ 1

Input

3
4
0 0 3 3
3
2 0 1
4
4 4 1 0

Output

2
0
3

Giải thích ví dụ

Test case 1: Bạn có thể chuyển mảng A thành [0, 1, 2, 3] trong hai phép toán và đạt MEX là 4, giá trị tối đa có thể. Các phép toán có thể là:

• Chọn chỉ số 1 và tăng A[1] lên 1.
• Chọn chỉ số 2 và giảm A[2] xuống 1.

Test case 2: Không thể tăng MEX của mảng thêm nữa.

Test case 3: Bạn có thể chuyển mảng A thành [2, 3, 1, 0] trong 3 phép toán và đạt MEX là 4, giá trị tối đa có thể. Các phép toán có thể là:

• Lặp lại phép toán hai lần trên chỉ số 1 và giảm A[1] xuống 1 mỗi lần.
• Chọn chỉ số 2 và giảm A[2] xuống 1.

Thông tin học tập

• Buổi: B16
• Concepts: sorting, ordered pairing, difference sums
• Giới hạn kiến thức: B01-B16
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 25