Máng trượt nước

Có $n$ cây cột xếp thành một hàng, cột thứ $i$ có chiều cao $a_i$. Ta muốn biến dãy chiều cao thành một dãy không giảm (tức $a_i\le a_{i+1}$ với mọi $i$).

Trong một thao tác, ta chọn một đoạn con liên tiếp các cột mà chiều cao của chúng đang không giảm, rồi tăng chiều cao của mỗi cột trong đoạn đó lên $1$.

Hãy tìm số thao tác ít nhất cần thực hiện để dãy chiều cao trở thành không giảm.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa số nguyên $n$ là số cột.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ là chiều cao các cột.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên là số thao tác ít nhất cần thực hiện.

Ràng buộc

• $1\le t\le 100$
• $1\le n\le 2·{10}^5$
• $0\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ test không vượt quá $2·{10}^5$.

Ví dụ