Aya ma na biurku naszyjnik z pereł $a$ o długości $n$. Każda perła ma określoną wartość blasku, przy czym $i$-ta perła od początku ma wartość blasku $a_i$.

Aya trzyma w ręku naszyjnik $b$, który początkowo jest pusty. Wykonuje ona serię operacji, przy czym w $i$-tym kroku może wybrać jedną z dwóch następujących akcji:

• Dodać na koniec naszyjnika $b$ perłę o wartości blasku równej $i$.
• Zwiększyć o $1$ wartość blasku dowolnej perły znajdującej się w naszyjniku $b$.

Aya chce wiedzieć, jaka jest minimalna liczba operacji potrzebna, aby naszyjnik $b$ stał się identyczny z naszyjnikiem $a$. Jeśli uzyskanie naszyjnika $b$ identycznego z $a$ jest niemożliwe, należy odpowiedzieć $-1$.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita $T$ ($1 \le T \le 10^4$), oznaczająca liczbę zestawów danych.

Dla każdego zestawu danych: W pierwszej linii znajduje się jedna liczba całkowita $n$ ($1 \le n \le 5 \times 10^5$), oznaczająca długość naszyjnika $a$. W drugiej linii znajduje się $n$ liczb całkowitych, gdzie $i$-ta liczba to $a_i$ ($1 \le a_i \le 10^{12}$), oznaczająca wartość blasku $i$-tej perły w naszyjniku $a$ (licząc od początku).

Suma $n$ dla wszystkich zestawów danych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego zestawu danych: Wypisz w jednej linii liczbę całkowitą oznaczającą minimalną liczbę operacji. Jeśli nie da się sprawić, by naszyjnik $b$ był identyczny z $a$, wypisz $-1$.

Przykład

Wejście 1

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

Wyjście 1

6
13
-1

Uwagi

Dla pierwszego zestawu danych: Przykładowy plan operacji o łącznej liczbie 6: 1. Dodaj perłę o wartości 1 na koniec $b$. 2. Dodaj perłę o wartości 2 na koniec $b$. 3. Dodaj perłę o wartości 3 na koniec $b$. 4. Zwiększ wartość 3. perły w $b$ o 1. 5. Dodaj perłę o wartości 5 na koniec $b$. 6. Dodaj perłę o wartości 6 na koniec $b$.