Cho dãy số nguyên ~a = (a_1, a_2, \dots, a_n)~ là một hoán vị của dãy số nguyên ~(1, 2, \dots, n)~. Hai phần tử trong dãy ~a~ được gọi là cặp số đẹp nếu phần tử đứng trước nhỏ hơn phần tử đứng sau và độ đẹp của cặp số này bằng độ chênh lệch giữa hai phần tử đó. Nói cách khác với phần tử ~a_i, a_j~, trong đó ~i < j~, ta gọi độ đẹp của cặp số này là: ~max(a_j - a_i, 0)~. Độ đẹp của dãy ~a~ được định nghĩa bằng tổng độ đẹp của tất cả các cặp số ~(a_i, a_j)~ với ~1 \le i < j \le n~.

Bạn được thực hiện các phép biến đổi, mỗi phép biến đổi có quy tắc như sau:

• Tùy chọn một vị trí ~k~ từ ~1~ tới ~n~.
• Tìm đoạn dài nhất gồm các phần tử liên tiếp trong dãy ~a~ mà ~a_k~ chính là giá trị lớn nhất trong đoạn đó. Giả sử đoạn tìm được là từ vị trí ~L~ tới vị trí ~R~ (~L \le k \le R~).
• Hoán vị đoạn từ vị trí ~L~ tới trước vị trí ~k~ (~a[L \dots k-1]~) với đoạn từ sau vị trí ~k~ tới vị trí ~R~ (~a[k+1 \dots R]~), giữ nguyên thứ tự các phần tử trong mỗi đoạn (chú ý rằng một trong hai đoạn này có thể rỗng).

Yêu cầu: Hãy tìm cách để thực hiện các phép biến đổi trên dãy ~a~ để có được độ đẹp của dãy là lớn nhất.

Input

• Dòng 1 chứa số nguyên dương ~T \le 10^9~ là số test.
• ~T~ nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng tương ứng với một test:
  • Dòng 1 chứa số nguyên dương ~n \le 10^9~.
  • Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ là một hoán vị của dãy số ~1, 2, \dots, n~. (Tổng các giá trị ~n~ trong tất cả ~T~ test không vượt quá ~10^9~)

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi kết quả của một test là độ đẹp của dãy ~a~ sau khi thực hiện các phép biến đổi của bạn.

Sample Input 1

3
4
3 4 1 2
5
2 4 5 3 1
9
5 2 6 9 3 7 4 8 1

Sample Output 1

9
15
71