У Аи на столе лежит цепочка из жемчужин $a$ длины $n$. Каждая жемчужина имеет значение яркости, и яркость $i$-й жемчужины от начала до конца равна $a_i$.

В руках у Аи находится цепочка из жемчужин $b$, изначально пустая. Она выполняет над этой цепочкой последовательность операций. В ходе $i$-й операции она может выбрать одно из двух действий: Добавить жемчужину с яркостью $i$ в конец цепочки $b$. Увеличить яркость любой жемчужины в $b$ на $1$.

Ая хочет узнать: какое минимальное количество операций необходимо выполнить, чтобы цепочка $b$ стала полностью идентична $a$? Если сделать цепочки $b$ и $a$ полностью одинаковыми невозможно, выведите $-1$.

Входные данные

В задаче содержится несколько наборов входных данных. В первой строке дано целое число $T$ ($1 \le T \le 10^4$), количество наборов данных.

Для каждого набора данных: Первая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^5$), длину цепочки $a$. Вторая строка содержит $n$ целых чисел, где $i$-е число $a_i$ ($1 \le a_i \le 10^{12}$) — яркость $i$-й жемчужины в $a$ от начала до конца.

Гарантируется, что сумма $n$ по всем наборам данных не превышает $5 \times 10^5$.

Выходные данные

Для каждого набора данных: Выведите одно целое число — минимальное количество операций. Если сделать цепочки $b$ и $a$ полностью одинаковыми невозможно, выведите $-1$.

Примеры

Ввод 1

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

Вывод 1

6
13
-1

Примечание

Для первого набора данных: Один из вариантов с 6 операциями: 1. Добавить жемчужину с яркостью 1 в конец $b$. 2. Добавить жемчужину с яркостью 2 в конец $b$. 3. Добавить жемчужину с яркостью 3 в конец $b$. 4. Увеличить яркость 3-й жемчужины в $b$ на 1. 5. Добавить жемчужину с яркостью 5 в конец $b$. 6. Добавить жемчужину с яркостью 6 в конец $b$.