Trên bàn của Aya có một chuỗi ngọc trai $a$ độ dài $n$, mỗi viên ngọc có một giá trị quang thái, giá trị quang thái của viên ngọc thứ $i$ tính từ đầu đến cuối là $a_i$.

Aya đang cầm một chuỗi ngọc trai $b$, ban đầu rỗng. Cô thực hiện một số thao tác trên chuỗi ngọc này, mỗi thao tác thứ $i$ có thể chọn một trong hai loại sau: Thêm một viên ngọc có giá trị quang thái là $i$ vào cuối chuỗi $b$. Tăng giá trị quang thái của bất kỳ viên ngọc nào trong $b$ lên $1$.

Aya muốn biết: cần ít nhất bao nhiêu thao tác để chuỗi ngọc $b$ hoàn toàn giống với $a$? Nếu không thể làm cho chuỗi $b$ hoàn toàn giống với $a$, hãy trả về $-1$.

Dữ liệu vào

Bài toán có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu: Dòng đầu tiên chứa một số nguyên dương $n$ ($1 \le n \le 5 \times 10^5$), biểu thị độ dài của chuỗi ngọc $a$. Dòng thứ hai chứa $n$ số nguyên dương, số nguyên thứ $i$ là $a_i$ ($1 \le a_i \le 10^{12}$), biểu thị giá trị quang thái của viên ngọc thứ $i$ trong $a$ tính từ đầu đến cuối.

Đảm bảo tổng $n$ trong $T$ bộ dữ liệu không vượt quá $5 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu: In ra một số nguyên duy nhất trên một dòng, biểu thị số lượng thao tác tối thiểu. Nếu không thể làm cho chuỗi $b$ hoàn toàn giống với $a$, in ra $-1$.

Ví dụ

Dữ liệu vào 1

3
5
1 2 4 5 6
8
1 2 4 5 5 8 10 9
3
3 2 1

Dữ liệu ra 1

6
13
-1

Ghi chú

Đối với bộ dữ liệu đầu tiên: Phương án với 6 thao tác như sau: 1. Thêm một viên ngọc có giá trị quang thái là 1 vào cuối chuỗi $b$. 2. Thêm một viên ngọc có giá trị quang thái là 2 vào cuối chuỗi $b$. 3. Thêm một viên ngọc có giá trị quang thái là 3 vào cuối chuỗi $b$. 4. Tăng giá trị quang thái của viên ngọc thứ 3 trong $b$ lên 1. 5. Thêm một viên ngọc có giá trị quang thái là 5 vào cuối chuỗi $b$. 6. Thêm một viên ngọc có giá trị quang thái là 6 vào cuối chuỗi $b$.