I. Di chuyển trên lưới
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Trong một tựa game do Bảo làm ra, bản đồ game là một lưới gồm $$$n$$$ cột, với cột thứ $$$i$$$ chỉ tồn tại các ô từ tọa độ $$$(1, i), (2, i), \ldots, (a_i, i)$$$. Biết rằng ô ($$$i, j$$$) ở hàng thứ $$$i$$$ tính từ trên xuống dưới và cột thứ $$$j$$$ tính từ trái sang phải.

Giả sử nhân vật của bạn đang ở trong bản đồ game, và ở ô ($$$i, j$$$). Bảo có thể thực hiện các thao tác sau:

  • Nếu tồn tại ô ở tọa độ ($$$i + 1, j$$$), di chuyển đến nó và tốn $$$1$$$ đồng.
  • Nếu tồn tại ô ở tọa độ ($$$i - 1, j$$$), di chuyển đến nó và tốn $$$1$$$ đồng.
  • Nếu tồn tại ô ở tọa độ ($$$i, j + 1$$$), di chuyển đến nó và không tốn chi phí.
  • Nếu tồn tại ô ở tọa độ ($$$i, j - 1$$$), di chuyển đến nó và không tốn chi phí.
Định nghĩa $$$f(i, j)$$$ là chi phí ít nhất để nhân vật di chuyển từ ô ($$$a_i, i$$$) đến ô ($$$a_j, j$$$) sử dụng các thao tác trên. Hãy giúp Bảo tính: $$$$$$\sum_{i = 1}^{n}\sum_{j = i + 1}^{n} f(i, j)$$$$$$
Input

Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcases.

Dòng đầu tiên của mỗi testcase gồm một số nguyên dương duy nhất $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số cột của lưới.

Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên dương $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) $$$-$$$ độ cao của mỗi cột.

Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$.

Output

Với mỗi testcase, trên một dòng, in ra kết quả của bài toán.

Example
Input
2
3
3 2 1
5
2 5 4 1 3
Output
4
30