Một dãy số nguyên a₁, a₂, ..., a_n, a_n+1, ..., a_2n+1 được gọi là dãy nón nếu dãy thỏa mãn điều kiện:

1. a_i+1 = a_i + 1 với 1 ≤ i ≤ n;

2. a_i+1 = a_i - 1 với n < i ≤ 2n.

Yêu cầu: Cho dãy số nguyên x₁, x₂, ..., x_m. Hãy tìm cách xóa đi ít phần tử nhất để nhận được dãy nón.

INPUT

Dòng đầu tiên ghi số nguyên dương T (T ≤ 10) là số lượng bộ dữ liệu.

Tiếp đến là T nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:

• Dòng đầu chứa một số nguyên m;
• Dòng thứ hai gồm m số x₁, x₂, ..., x_m (|x_i| ≤ 10⁹).

OUTPUT

• Gồm T dòng, mỗi dòng chứa một số là số phần tử ít nhất được xóa (ghi -1 nếu không có cách xóa thỏa mãn) tương ứng với bộ dữ liệu vào.

INPUT

2
4
1 2 3 1
4
1 2 3 4

OUTPUT

1
-1

Ràng buộc

• Có 25% số test ứng với 25% số điểm của bài có n ≤ 20.
• Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 300.
• Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 4000.
• Có 25% số test còn lại ứng với 25% số điểm của bài có n ≤ 50000.