Trong thử thách này, bạn sẽ được cung cấp một mảng B và phải xác định một mảng A.

Có một quy tắc đặc biệt: Đối với tất cả i, A[i] <= B[i] .

A[i] có thể là bất kỳ số nào bạn chọn sao cho 1 <= A[i] <= B[i].

Nhiệm vụ của bạn là chọn một loạt các giá trị đã cho sao cho tổng của sự khác biệt tuyệt đối của các cặp liên tiếp được tối đa hóa.

Phương trình có thể được viết:

            for(int i=2;i<=n;i++){
                S += | A[i] - A[i-1] |
            }

Ví dụ:

Nếu mảng B = [1,2,3], chúng ta biết rằng 1 <= A[1] <=1, 1 <= A[2] <=2 và 1 <= A[3] <=3.

Mảng đáp ứng các hướng dẫn đó là:

[ 1 , 1 , 1 ] hoặc [ 1 , 1 , 2 ] hoặc [ 1 , 1 , 3 ]

[ 1 , 2 , 1 ] hoặc [ 1 , 2 , 2 ] hoặc [ 1 , 2 , 3 ]

Tính toán của chúng tôi cho các mảng như sau:

| 1 - 1 | + | 1 - 1 | = 0 hoặc | 1 - 1 | + | 2 - 1 | = 1 hoặc | 1 - 1 | + | 3 - 1 | = 2

| 2 - 1 | + | 1 - 2 | = 2 hoặc | 2 - 1 | + | 2 -2 | = 1 hoặc | 2 - 1 | + | 3 - 2 | = 2

Giá trị tối đa thu được là: 2.

Mô tả chức năng

Hoàn thành chức năng chi phí trong trình chỉnh sửa dưới đây. Nó sẽ trả về giá trị tối đa có thể thu được.

chi phí có (các) tham số sau:

B : một mảng các số nguyên

Định dạng đầu vào:

Dòng đầu tiên chứa số nguyên t, số lượng test.

Mỗi cặp dòng tiếp theo là một trường hợp thử nghiệm trong đó:

• Dòng đầu tiên chứa một số nguyên n là độ dài của mang B

• Dòng tiếp theo chứa n các số nguyên B[i] được phân tách bằng dấu cách

Những ràng buộc:

1 <= t <=20

1 < n <= 10^5

1 <= B[i] <= 100

Định dạng đầu ra:

Đối với mỗi trường hợp thử nghiệm, hãy in tổng tối đa trên một dòng riêng biệt.

Input

1 5 10 1 10 1 10

Output

36

Giải Thích:

Tổng tối đa xảy ra khi A[1] = A[3] = A[5] = 10 and A[2] = A[4] = 1

|1 - 10| + |10 - 1| + |1 - 10| + |10 - 1| = 36