Thảo luậnSnackDown Online Pre-elimination round A - A temple of Snakes

Bạn muốn xây một ngôi đền cho các con rắn. Ngôi đền sẽ được xây dựng trên một dãy núi, có thể gồm n khối, chiều cao của khối thứ i là hi. Đền sẽ được xây bằng các khối liên tiếp và chiều cao của nó nên bắt đầu từ 1 và mỗi lần chiều cao lại tăng thêm 1 đơn vị cho đến một độ cao nhất định và sau đó giảm mỗi chiều cao 1 lần là 1 đơn vị, tức là chiều cao liên tiếp của các khối như sau: 1, 2, 3, .. x-1, x, x-1, x-2, .., 1. Ngoài ra, chiều cao của tất cả các khối ngoài ngôi đền đều bằng 0, do đó đền thờ có thể nhìn thấy được đối với những người nhìn từ bên trái hoặc bên phải.

Để xây một ngôi đền, bạn có thể làm giảm độ cao của một số khối. Khi đó, mỗi lần bạn có thể giảm chiều cao của một khối xuống 1 đơn vị. Tìm ra số lượng tối thiểu các thao tác cần thiết để xây dựng một ngôi đền theo cách trên.

Dữ liệu vào

- Dòng đầu tiên của dữ liệu vào chứa một số nguyên T – số test. Các test được miêu tả như sau:

- Dòng dầu tiên của mỗi test chứa một số nguyên n.

- Dòng tiếp theo chứa n số nguyên, số nguyên thứ i là hi

Dữ liệu ra

- Ở mỗi test, in ra một dòng với một số nguyên là câu trả lời.

Ràng buộc

- 1 ≤ T ≤ 10

- 2 ≤ n ≤ 10^5

- 1 ≤ hi ≤ 10^9

Ví dụ

Input

3
3
1 2 1
4
1 1 2 1
5
1 2 6 2 1

Output

0
1
3

Giải thích

Ví dụ 1. Toàn bộ dãy núi đã là một ngôi đền. Vì vậy, không cần thực hiện bất kỳ hành động nào.

Ví dụ 2. Nếu bạn giảm chiều cao của khối đầu tiên xuống 0. Bạn nhận được 0 1 2 1. Các khối 1, 2, 1 tạo thành một ngôi đền. Vì vậy, câu trả lời là 1.

Ví dụ 3. Một đền có thể là 1 2 3 2 1. Cần 3 thao tác để xây dựng. Đây là số thao tác tối thiểu để xây dựng một ngôi đền.