아야의 책상 위에는 길이가 $n$인 진주 목걸이 $a$가 놓여 있으며, 각 진주에는 광채 값이 있습니다. 처음부터 끝까지 $i$번째 진주의 광채 값은 $a_i$입니다.
아야는 손에 빈 진주 목걸이 $b$를 들고 있습니다. 그녀는 이 목걸이에 대해 여러 번의 조작을 수행할 수 있으며, $i$번째 조작에서는 다음 두 가지 중 하나를 선택할 수 있습니다.
- 광채 값이 $i$인 진주 하나를 $b$의 끝에 꿴다.
- $b$에 있는 진주 중 임의의 진주 하나의 광채 값을 1 높인다.
아야는 진주 목걸이 $b$를 $a$와 완전히 똑같이 만들기 위해 필요한 최소 조작 횟수를 알고 싶어 합니다. 만약 $b$를 $a$와 완전히 똑같이 만들 수 없다면 -1을 출력하세요.
입력
입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^4$)가 주어집니다.
각 테스트 케이스에 대하여: 첫 번째 줄에 진주 목걸이 $a$의 길이 $n$ ($1 \le n \le 5 \times 10^5$)이 주어집니다. 두 번째 줄에 $n$개의 정수가 주어지며, $i$번째 정수는 $a$의 처음부터 끝까지 $i$번째 진주의 광채 값 $a_i$ ($1 \le a_i \le 10^{12}$)입니다.
모든 테스트 케이스의 $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인 진주를 $b$의 끝에 꿴다.
- 광채 값이 2인 진주를 $b$의 끝에 꿴다.
- 광채 값이 3인 진주를 $b$의 끝에 꿴다.
- $b$의 처음부터 끝까지 3번째 진주의 광채 값을 1 높인다.
- 광채 값이 5인 진주를 $b$의 끝에 꿴다.
- 광채 값이 6인 진주를 $b$의 끝에 꿴다.